高精度加递推完美超时。。。

#include<iostream>
#include<string>
using namespace std;
string add(string sa,string sb)
{
string sc;
int a[10000],b[10000],c[10000];
int i,j,x,lena,lenb,lenc;
lena=sa.size();
for (i=0,j=lena;i<lena;i++,j--)
a[j]=int(sa[i])-48;
lenb=sb.size();
for (i=0,j=lenb;i<lenb;i++,j--)
b[j]=int(sb[i])-48;
i=1; x=0;
while (i<=lena || i<=lenb)
{
c[i]=a[i]+b[i]+x;
x=c[i]/10;
c[i]%=10;
i++;
}
if (x>0)
{
lenc=i;
c[i]=x;
}
else lenc=i-1;
for (i=lenc;i>=1;i--)
sc+=char(c[i]+48);
return sc;
}
int main()
{
ios::sync_with_stdio(false);
string s[100000];
long n,i;
cin>>n;
s[1]="1";
for (i=2;i<=n;i++)
{
if (i%2==1) s[i]=s[i-1];
else
s[i]=add(s[i-1],s[i/2]);
}
cout<<s[n];
return 0;
}

5 条评论

  • @ 2015-08-03 23:21:36

    hhh

  • @ 2015-07-13 09:49:37

    哪位大牛帮忙看看,谢谢
    var
    a:longint;
    m:array[1..3000000]of string;
    function add(a,b:string):string;
    var
    s:string;
    bp,ch,i,p,j:longint;
    ap,bk,k:array[1..50]of longint;
    begin
    fillchar(ap,sizeof(ap),0);
    fillchar(bk,sizeof(bk),0);
    fillchar(k,sizeof(k),0);
    if length(a)>length(b) then
    begin
    bp:=length(a);
    j:=length(b)+1;
    ch:=bp-length(b);
    for i:=2 to bp+1 do val(a[i-1],ap[i],p);
    for i:=bp+1 downto ch+1 do
    begin
    dec(j);
    val(b[j],bk[i],p);
    end;
    end else
    begin
    if length(a)<length(b) then
    begin
    j:=length(a)+1;
    bp:=length(b);
    ch:=bp-length(a);
    for i:=2 to bp+1 do val(b[i-1],bk[i],p);
    for i:=bp+1 downto ch+1 do
    begin
    dec(j);
    val(a[j],ap[i],p);
    end;
    end else
    begin
    bp:=length(b);
    for i:=2 to bp+1 do
    begin
    val(b[i-1],bk[i],p);
    val(a[i-1],ap[i],p);
    end;
    end;
    end;
    for i:=bp+2 downto 2 do
    begin
    k[i]:=bk[i]+ap[i];
    while k[i]>9 do
    begin
    k[i]:=k[i]-10;
    inc(k[i-1]);
    end;
    end;
    for i:=bp+1 downto 1 do
    begin
    str(k[i],s);
    add[i]:=s[1];
    end;
    if add[1]='0' then delete(add,1,1);
    end;
    function dg(n:longint):string;
    var i:longint;

    begin
    i:=0;
    if n=a then dg:='1';
    if n=1 then
    begin
    dg:='1';
    m[1]:='1';
    end else
    begin
    for i:=1 to n div 2 do
    begin
    if m[i]='0'then dg:=add(dg,dg(i))else dg:=add(dg,m[i]);
    end;
    m[n]:=dg;
    end;
    end;
    begin
    fillchar(m,sizeof(m),'0');
    m[1]:='1';
    readln(a);
    if a mod 2=1 then dec(a);
    writeln(dg(a));
    end.

  • @ 2015-04-22 12:18:15

    请正确地发布源代码

  • @ 2014-12-09 17:15:48

    ?..................

  • @ 2014-12-06 21:48:33

    请正确地发布源代码

  • 1

信息

ID
1136
难度
8
分类
递推 | 高精度 点击显示
标签
(无)
递交数
3322
已通过
500
通过率
15%
被复制
4
上传者