题解

63 条题解

  • 2
    @ 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
    @ 2020-05-15 23:13:11
    #include<bits/stdc++.h>
    using  namespace std;
    int main(){
        printf("我心态炸了\n");
        return 0;
    }
    
  • 0
    @ 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
    @ 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
    @ 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
    @ 2009-05-18 17:18:14

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

  • 0
    @ 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
    @ 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
    @ 2008-11-18 23:12:18

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

  • 0
    @ 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
    @ 2008-11-13 21:28:10

    DFS

    全零

    哈哈哈哈哈哈哈

  • 0
    @ 2008-11-13 21:13:39

    DFS秒杀!

    爽!

  • 0
    @ 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
    @ 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
    @ 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
    @ 2008-11-13 18:52:26

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

  • 0
    @ 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
    @ 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
    @ 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
    @ 2008-11-13 18:00:29

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

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

    完全背包+数组记录

信息

ID
1480
难度
7
分类
字符串 | 动态规划 | 背包 点击显示
标签
递交数
802
已通过
138
通过率
17%
被复制
5
上传者