题解 - Vijos

2

WiFi LV 8 @ 2017-08-19 21:18:01

四平方和定理：每个正整数均可表示为4个整数的平方和

故分成的序列<=4个

所以可使用搜索

从大往小依次进行搜索，找出所需序列最少的，因为搜的顺序从大到小所以搜出来以后顺序默认就是符合题意的

搜出来之后直接输出

代码如下

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
string s;
int a[5],m,n,p=6,b[5];
void dfs(int k,int r,int ss){
    if(ss>m) return;
    if(k>=p) return;
    if(ss==m){
        p=k;
        for(int i=1;i<k;i++) b[i]=a[i];
        return;
    }
    for(int i=r;i;i--){
        a[k]=i;
        dfs(k+1,i,ss+i*i);
    }
    return;
}
int main(){
    getline(cin,s);
    m=s.size(),n=sqrt(m);
    dfs(1,n,0);
    int l=0;
    for(int i=1;i<p;i++){
        for(int j=l+1;j<=l+b[i];j++){
            for(int k=0;k<b[i];k++){
                cout<<s[j+k*b[i]-1];
            }
        }
        l+=b[i]*b[i];
    }
    return 0;
}

0

j18tm01 LV 10 @ 2020-05-15 23:13:11

#include<bits/stdc++.h>
using  namespace std;
int main(){
    printf("我心态炸了\n");
    return 0;
}

0

TGSteven LV 8 @ 2016-12-31 12:05:50

一道猥琐的背包
背时记得平方从小到大，记录转移再从后向前推
c++ #include<iostream> #include<string> #include<cstdio> using namespace std; int g[70000],dp[70000],ans[70000]; string str,out; int main() { //freopen("test.in","r",stdin); int m=0,i,j,n,s,k; getline(cin,str); n=str.length(); for(i=1;i<=n;i++) { dp[i]=1<<30; for(j=1;j*j<=i;j++) if((g[i-j*j]<=j || i==j*j) && dp[i-j*j]+1<=dp[i]) { dp[i]=dp[i-j*j]+1; g[i]=j; } } i=n; s=0; while(i>0) { s++; ans[s]=g[i]; i-=g[i]*g[i]; } for(i=1;i<=s;i++) { m+=ans[i-1]*ans[i-1]; for(j=0;j<ans[i];j++) for(k=0;k<ans[i];k++) out+=str[k*ans[i]+j+m]; } cout<<out; return 0; }

0

一方T行 LV 10 @ 2014-08-05 20:38:47

默默地秒杀了。。。
program p1480;
var a,b:array[0..70000] of longint;
t:array[0..70000] of boolean;
h,ss:array[0..200] of longint;
f:array[0..300,0..300] of char;
s:ansistring;
n,m:longint;
//
procedure init;
begin
read(s);
n:=length(s);
end;
//
procedure make(p:longint);
var i,j:longint;
begin
for i:=1 to h[p] do
for j:=1 to h[p] do
begin
f[i,j]:=s[ss[p]];inc(ss[p]);
end;
for i:=1 to h[p] do
for j:=1 to h[p] do write(f[j,i]);
end;
//
procedure main;
var i,j:longint;
begin
for i:=1 to n do
begin
a[i]:=1000000;b[i]:=1000000;
end;
t[0]:=true;
for i:=1 to n do
for j:=1 to trunc(sqrt(i)) do
if t[i-j*j] then
begin
t[i]:=true;
if a[i-j*j]+1<a[i] then
begin
a[i]:=a[i-j*j]+1;b[i]:=j;
end
else if a[i-j*j]+1=a[i] then
if j>b[i] then b[i]:=j;
end;
end;
//
procedure print;
var i,k:longint;
begin
i:=n;
while i<>0 do
begin
inc(h[0]);h[h[0]]:=b[i];i:=i-b[i]*b[i];
end;
ss[1]:=1;
for i:=2 to h[0] do ss[i]:=ss[i-1]+h[i-1]*h[i-1];
for i:=1 to h[0] do
begin
make(i);
end;
end;
//
begin
init;
main;
print;
end.

0

song19931218 LV 9 @ 2009-09-12 20:56:29

program p1480;

var

f,fh:array[1..70000] of integer;

s:ansistring;

l,k,i,j,chang,st,long:longint;

procedure print(ss:ansistring; k,start,long:longint);

var

s:ansistring;

i,j:longint;

begin

s:=copy(ss,start,long);

for i:=1 to k do

for j:=1 to k do

write(s[(j-1)*k+i]);

end;

begin

readln(s); l:=length(s);

fillchar(f,sizeof(f),0);

k:=trunc(sqrt(l));

for i:=1 to k do begin f[sqr(i)]:=1;fh[sqr(i)]:=i; end;

if sqr(trunc(sqrt(l)))=l then

begin

k:=trunc(sqrt(l));

print(s,k,1,l);

end

else

begin

for i:=1 to l do

if f[i]=0 then

begin

f[i]:=20000;

for j:=trunc(sqrt(i)) downto 1 do if f+1

0

cnnblike LV 9 @ 2009-05-18 17:18:14

写个题解……此题告诉我们……256以上的字符串要用ansistring,细节很重要……读题很重要尤其是这些……重要内容和题干分离的题目……同时……要想清楚再写……就是这样……

0

玛维-影之歌 LV 10 @ 2008-12-13 21:46:10

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

DFS都0ms...看来不用FT了...

被ANSISTRING浪费一次提交...

0

金牌选手2世 LV 3 @ 2008-12-08 13:39:39

program p2;

var

s:ansistring;

l,i,p,j,k:longint;

f:array[0..70000] of integer;

a:array[1..70000] of array[1..5] of integer;

procedure doit(k:longint);

var

i,min,j:longint;

begin

min:=2147483647;

for i:=trunc(sqrt(k)) downto trunc(sqrt(k/2)) do

if 1+f[k-sqr(i)]

0

93lrm LV 8 @ 2008-11-18 23:12:18

ac率啊，降了1%，6遍才过

0

Dark_sun LV 9 @ 2008-11-13 22:01:14

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

0

易万力 LV 3 @ 2008-11-13 21:28:10

DFS

全零

哈哈哈哈哈哈哈

0

king13 LV 8 @ 2008-11-13 21:13:39

DFS秒杀!

爽!

0

379007016 LV 4 @ 2008-11-13 20:51:17

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

只用37行...

const

maxr=65536;

var

r:ansistring;

l:array[1..maxr,1..10] of integer;

f:array[1..maxr] of integer;

min:longint;

n,i,j,k:integer;

begin

readln(r);

n:=length(r);

fillchar(l,sizeof(l),0);

fillchar(f,sizeof(f),0);

for i:=1 to n do

begin

min:=maxlongint;

for j:=trunc(sqrt(i)) downto trunc(sqrt(i/2)) do

if f+1

0

sdvsdv LV 10 @ 2008-11-13 20:43:33

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 72ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：72ms

本人不才,在背包上加了个冒泡..

0

So飞ar翔 LV 10 @ 2008-11-13 18:54:01

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

就是忘记考虑字典序了。。。。把to改成downto就没问题了啊。。。

0

laj5122 LV 3 @ 2008-11-13 18:52:26

本人贡献了无数次WA.我用EOF读的..

0

wubinxingtc LV 6 @ 2008-11-13 18:48:07

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：25ms

最后有个换行，我读的时候打了EOF，而不是EOLN，结果10分（能对一个真是奇迹）

0

dapig5566 LV 3 @ 2008-11-13 18:43:18

program MySolution ;

var

a:ansistring;

b:packed array[1..80000] of char;

i,j,k,len,q,ans,lenxx:longint;

p:array[1..10000]of longint;

procedure find(ii,lens:longint);

var i1,k1,j1,qq,ox,yy,zz,sum,lenss:longint;

begin

for i1:=ii downto 1 do

begin

　　lenss:=lens-i1*i1;

　　if (lenss>0)and(k+1

0

Cpt.Price LV 6 @ 2008-11-13 18:10:55

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

略微优化过的搜索秒杀……

0

ahbbcsq LV 4 @ 2008-11-13 18:00:29

9ms.............

差点秒杀,不过是一次AC......

完全背包+数组记录

题解

63 条题解

凯撒密码

信息

状态

开发

支持

题解

63 条题解

凯撒密码

信息

状态

开发

支持

还没有账户？

登录