94 条题解

  • 1
    @ 2018-11-23 22:17:52
    sum=[]
    sum.append(0)
    for i in range(1,1500001):
        sum.append(sum[i-1]+sum[i//2]+1)
    if __name__ == '__main__':
        while True:
            try:
                n = int(input())
                k=n//2
                print(sum[k] + 1)
            except EOFError:
                break
    
  • 1
    @ 2018-07-24 15:31:05
    #include<bits/stdc++.h>
    using namespace std;
    const int e=7,mod=100000000;
    int f[1500000+1][e+1],n;
    void s(int *a,int *b,int *o) {
        for(int i = e;i>=1;i--) {
            o[i] += a[i]+b[i];
            o[i-1] += o[i]/mod;
            o[i] %= mod;
        }
    }
    void p(int *n) {
        int i,j,l;
        for(i=0; i<=e && n[i]==0; i++);
        
        cout<<n[i];
        for(++i;i<=e;i++){
            l = 1+(int)log10(n[i]);
            for(j=8;j>l;j--)
            putchar('0');
            cout<<n[i];
        } 
        cout<<endl; 
    }
    int main() 
    {
        int n;
        f[0][e]=1;
        
        for(int i = 1;i<=1500000;i++)
        s(f[i-1],f[i/2],f[i]);
        while(cin >> n) 
            p(f[n/2]);
            
        return 0;
    }
    
  • 1
    @ 2013-08-08 17:28:58

    const py=10000;
    type dd=array[0..21] of integer;
    var
    f:array[0..1500001] of dd;
    i,j,n:longint;
    begin
    f[0][1]:=1; f[0][0]:=1;
    for i:=1 to 1500000 do
    for j:=1 to 20 do
    begin
    f[i][j]:=f[i][j]+f[i-1][j]+f[i div 2][j];
    f[i][j+1]:=f[i][j+1]+f[i,j] div py;
    f[i,j]:=f[i,j] mod py;
    end;
    while not(eof) do
    begin
    readln(n);
    n:=n shr 1;
    for i:=20 downto 1 do
    if f[n,i]<>0 then break;
    write(f[n,i]);
    for j:=i-1 downto 1 do
    begin
    if f[n,j]<1000 then write('0');
    if f[n,j]<100 then write('0');
    if f[n,j]<10 then write('0');
    write(f[n,j]);
    end;
    writeln;
    end;
    end.

    • @ 2017-08-02 20:41:58

      和我普及组时候的风格很像,存数据。。。。。。。
      不过这题比普及组前几题难多了

  • 0
    @ 2018-10-05 22:22:32

    令所求为\(ans\)

    朴素解法:

    \(ans[0..1]=1\)
    \(ans[i] = \sum_{k=1}^{\lfloor \frac i 2 \rfloor} ans[k]\)

    差分,如下:

    \(ans[i] - ans[i-1] = \left \{ \begin{array}{ll}ans\left[\frac i 2\right] & i\mod 2 == 0 \\0 & i \mod 2 == 1\end{array} \right. \)

    移项,如下:

    \(ans[i] = ans[i-1] + \left\{\begin{array}{ll} ans\left[\frac i 2\right] & i\mod 2 == 0 \\ 0 & i \mod 2 == 1 \end{array}\right. \)

    观察到奇偶项存在相同部分,以2差分:

    \(ans\left[i\right] = ans\left[i-2\right] + ans\left[\left\lfloor \frac i 2\right\rfloor\right]\)

    则对\(\left\lfloor\frac i 2\right\rfloor\),有:

    \(ans\left[\left\lfloor\frac i 2\right\rfloor\right] = ans\left[\left\lfloor\frac{i-1} 2\right\rfloor\right] +ans\left[\left\lfloor \frac {\left\lfloor \frac i 2\right\rfloor} 2\right\rfloor\right]\)

    令\(dp[i] = ans\left[\left\lfloor\frac i 2\right\rfloor\right]\)
    则:\(dp[i] = dp\left[i-1\right]+dp\left[\left\lfloor \frac i 2 \right\rfloor\right]\)

    import Data.Array
    
    dp::Array Int Integer
    dp = array (0,1500000) $ (0,1) : [(i,ans i) | i<-[1..1500000]]
        where ans i = dp!(i-1) + dp!(i`div`2)
    
    solve::Int->Integer
    solve n = dp!(n`div`2)
    
    main::IO()
    main = interact $ unlines.map (show.solve.read).words
    
  • 0
    @ 2017-11-22 23:37:07

    //f(n)=f(n-2)+f(n/2)-----n%2==0
    //f(n)=f(n-1)------------n%2==1
    //先计算1--300W保存,然后直接取出来;
    //当然这里可以优化,只保存1-150W ,最后输出的时候再运算一次也可以
    //题目对于输入输出描述的不是很清楚
    //输入包含若干组数据……一开始以为只有一组23333,因此要使用while(scanf()!=EOF)
    //输出是一个测试数据对应了一行输出
    #include<cstdio>
    #include<cstring>
    const unsigned int N=1E+9;//满10^9进位
    unsigned int brr[3000001][6];//6位int来表示长度为50的足够了
    int main(){
    memset(brr,0,sizeof(brr));
    brr[1][0]=1;//f(1)=1
    brr[2][0]=2;//f(2)=2
    int m=3000000;

    for(int i=3;i<=m;i++){
    if(i%2==1){//f(n)=f(n-1)---------n%2==1
    for(int j=0;j<6;j++)
    brr[i][j]=brr[i-1][j];
    }
    //arr[i]=arr[i-1];
    else{//f(n)=f(n-2)+f(n/2)-------n%2==0
    for(int j=0;j<6;j++){
    //j越大表示数字位(类似个十百千)越高
    brr[i][j]+=brr[i-2][j]+brr[i/2][j];
    if(brr[i][j]>=N){
    brr[i][j]%=N;
    brr[i][j+1]++;
    }
    }
    }
    }
    int n;
    while(scanf("%d",&n)!=EOF){//前面已经计算完了,这里直接取出来输出
    int flag=0;
    for(int j=5;j>=0;j--){
    if(flag)//如果之前已经输出过有效数字那么当前的9位数字都要输出
    printf("%09d",brr[n][j]);
    else{
    if(brr[n][j]){
    printf("%d",brr[n][j]);
    flag=1;
    }
    }

    }
    printf("\n");

    }
    return 0;
    }

  • 0
    @ 2016-07-12 09:44:02

    const oo=1000000000000000000;
    var n,i:longint;
    j:byte;
    a:array[0..3000000,0..4] of qword;
    st:string[20];
    procedure adding;
    begin
    a[i,0]:=a[i-1,0];
    for j:=1 to a[i,0] do
    begin
    a[i,j]:=a[i,j]+a[i-1,j]+a[i div 2,j];
    a[i,j+1]:=a[i,j] div oo;
    a[i,j]:=a[i,j] mod oo;
    end;
    if a[i,a[i,0]+1]>0 then inc(a[i,0]);
    end;
    begin
    a[0,0]:=1;
    a[0,1]:=1;
    for i:=1 to 3000000 do
    if i mod 2=1 then a[i]:=a[i-1]
    else adding;
    while not eof do
    begin
    readln(n);
    write(a[n,a[n,0]]);
    for i:=a[n,0]-1 downto 1 do
    begin
    str(a[n,i],st);
    while length(st)<18 do st:='0'+st;
    write(st);
    end;
    writeln;
    end;
    end.
    竟然要记忆化!
    超了两次!

  • 0
    @ 2016-04-04 15:29:24

    #include <stdio.h>
    #include <string.h>
    #include <math.h>
    #define END 7
    #define MOD 100000000
    int f[1500001][END+1];
    void plus(int *a, int *b, int *out){
    int i;
    for(i=END; i>=1; i--){
    out[i] += a[i]+b[i];
    out[i-1] += out[i]/MOD;
    out[i] %= MOD;
    }
    }
    void print(int *num){
    int i, j, length;
    for(i=0; i<=END && num[i]==0; i++)
    ;
    printf("%d", num[i]);
    for(++i; i<=END; i++){
    length = 1 + (int)log10(num[i]);
    for(j=8; j>length; j--)
    putchar('0');
    printf("%d", num[i]);
    }
    putchar('\n');
    }
    int main(){
    int n, i;
    memset(f, 0, sizeof(f));
    f[0][END] = 1;
    for(i=1; i<=1500000; i++)
    plus(f[i-1], f[i/2], f[i]);
    while(scanf("%d", &n) != EOF)
    print(f[n/2]);
    return 0;
    }

  • 0
    @ 2015-08-20 19:00:40

    C语言,递推,高精度压成了十位数。
    首先发现一个规律 F[n]=∑F[1...n/2]+1
    写几个出来
    F[2]=F[3]=F[1]+1
    F[4]=F[5]=F[1..2]+1=F[1]+1+F[2]=2F[2]
    F[6]=F[7]=F[1..3]+1=F[1..2]+1+F[3]=F[4]+F[3]
    F[7]=F[8]=F[1..4]+1=F[1..3]+1+F[4]=F[6]+F[4]
    规律就是
    F[n]=F[n+1]=F[n-1]+Fn/2
    F[n-1]=F[n] =F[n-2]+Fn/2
    干脆一开始n=n/2;==> 答案为 F[n]=F[n-1]+F[n/2];
    ~~~~~~~~~~~~~~~~~~~~~~~~~(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)(¯﹃¯)~~~~~~~~~~~~~~~~~~~~~~~~~
    测试数据 #0: Accepted, time = 0 ms, mem = 41532 KiB, score = 10
    测试数据 #1: Accepted, time = 140 ms, mem = 41536 KiB, score = 30
    测试数据 #2: Accepted, time = 171 ms, mem = 41536 KiB, score = 60

    #include<stdio.h>
    #define P 1000000000//10位
    int n,i,j,k,len=1;
    int F[1500001][7];
    void jia(int a[],int b[],int c[])
    {
    int i;
    for(i=0;i<len;i++) { c[i]+=a[i]+b[i];if(c[i]>=P) {c[i]-=P;c[i+1]++;} }
    if(c[len]!=0) len++;
    }
    void output(void)
    {
    int i,j,k;
    for(i=6;F[n][i]==0;i--) ;
    printf("%d",F[n][i--]);//输出最高位
    for(;i>=0;i--)
    {
    for(j=1,k=0 ;F[n][i]/j; j*=10,k++);//k位

    for(;k<9;k++)printf("0"); printf("%d",F[n][i]);//不足9位的输出0

    } printf("\n");
    }
    int main(void)
    {
    int m=0;
    while(scanf("%d",&n)==1)
    {

    if(n==0){printf("0\n");continue;}//特判
    n/=2; F[0][0]=1;
    for(i=m+1;i<=n;i++) jia(F[i-1],F[i/2],F[i]);
    if(m<n)m=n;//记录算过的最大n,下次不再算
    output();
    }
    return 0;

    }

  • 0
    @ 2015-08-05 09:03:17

    写高精度即可

  • 0
    @ 2015-02-01 22:20:25

    “包含多组测试数据”坑到我了........

    先把0到150W的答案全算好....
    递推 f[i]=f[i-1]+f[i/2];
    边界 f[0]=1;
    答案 f[n/2];
    高精只压了4位(万进制),每个点都是560ms....

  • 0
    @ 2014-03-09 16:13:08

    编译成功

    Free Pascal Compiler version 2.6.2 [2013/02/12] for i386
    Copyright (c) 1993-2012 by Florian Klaempfl and others
    Target OS: Win32 for i386
    Compiling foo.pas
    Linking foo.exe
    45 lines compiled, 0.1 sec , 29248 bytes code, 1628 bytes data
    测试数据 #0: Accepted, time = 904 ms, mem = 82932 KiB, score = 10
    测试数据 #1: Accepted, time = 858 ms, mem = 82932 KiB, score = 30
    测试数据 #2: Accepted, time = 889 ms, mem = 82932 KiB, score = 60
    Accepted, time = 2651 ms, mem = 82932 KiB, score = 100

    程序如下...
    type num=array[0..13] of longint;
    const mm=1000000000;
    var n,len,k,i:longint;
    f:array[0..1500100] of num;
    procedure add(var a,b:num);
    begin
    if a[0]>b[0] then len:=a[0]
    else len:=b[0];
    for k:=1 to len do begin
    inc(a[k],b[k]);
    inc(a[k+1],a[k]div mm);
    a[k]:=a[k] mod mm;
    end;
    if a[len+1]<>0 then inc(len);
    a[0]:=len;
    end;

    procedure pt(n:longint);
    var i:longint;
    begin
    write(f[n div 2,f[n div 2,0]]);
    for i:=f[n div 2][0]-1 downto 1 do begin
    if f[n div 2][i]<100000000 then write(0);
    if f[n div 2][i]<10000000 then write(0);
    if f[n div 2][i]<1000000 then write(0);
    if f[n div 2][i]<100000 then write(0);
    if f[n div 2][i]<10000 then write(0);
    if f[n div 2][i]<1000 then write(0);
    if f[n div 2][i]<100 then write(0);
    if f[n div 2][i]<10 then write(0);
    write(f[n div 2][i]);
    end;
    end;

    begin
    f[0][0]:=1;f[0][1]:=1;
    for i:=1 to 1500000 do begin
    add(f[i],f[i-1]);
    add(f[i],f[i div 2]);
    end;
    while not eof do begin
    readln(n);
    pt(n);
    writeln;
    end;
    end.

  • 0
    @ 2013-04-09 13:52:09

    恶心的卡内存!!

    上海红茶馆 via JudgeDaemon2/13.4.1.0 via libjudge
    编译成功

    foo.cpp:5:21: warning: missing braces around initializer for 'int [6]' [-Wmissing-braces]
    测试数据 #0: Accepted, time = 31 ms, mem = 70676 KiB, score = 10
    测试数据 #1: Accepted, time = 132 ms, mem = 70676 KiB, score = 30
    测试数据 #2: Accepted, time = 171 ms, mem = 70676 KiB, score = 60
    Summary: Accepted, time = 334 ms, mem = 70676 KiB, score = 100
    代码
    #include<iostream>
    #include<cstdio>
    using namespace std;
    const int n=1000000000;
    int f[3000000][6]={0};
    int a[50]={0};
    int maxn,k;
    void init()
    {
    int i;
    i=0;
    maxn=0;
    while(cin>>a[i])
    {
    if(maxn<a[i])maxn=a[i];
    i++;
    }
    k=i;

    }
    void pluss(int a[],int b[],int c[])
    {
    int i;
    for(i=0;i<6;i++)
    {
    c[i]+=a[i]+b[i];
    c[i+1]+=c[i]/n;
    c[i]=c[i]%n;
    }
    }
    void solve()
    {
    int i,j;
    f[0][0]=1;
    f[1][0]=1;
    for(i=2;i<=maxn;i++)
    {

    if(i%2!=0)
    {
    for(j=0;j<6;j++)
    f[i][j]=f[i-1][j];
    continue;
    }
    pluss(f[i-1],f[i/2],f[i]);
    }
    }
    void print()
    {
    int i,j,l;
    for(i=0;i<k;i++)
    {
    j=5;
    while ((f[a[i]][j]==0)&&(j>0))j--;
    cout<<f[a[i]][j];
    for(l=j-1;l>=0;l--)
    {
    if(f[a[i]][l]/100000000==0) cout<<'0';
    if(f[a[i]][l]/10000000==0) cout<<'0';
    if(f[a[i]][l]/1000000==0) cout<<'0';
    if(f[a[i]][l]/100000==0) cout<<'0';
    if(f[a[i]][l]/10000==0) cout<<'0';
    if(f[a[i]][l]/1000==0) cout<<'0';
    if(f[a[i]][l]/100==0) cout<<'0';
    if(f[a[i]][l]/10==0) cout<<'0';
    cout<<f[a[i]][l];
    }
    cout<<endl;
    }
    }
    int main()
    {
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);

    init();
    solve();
    print();
    return 0;
    }

  • 0
    @ 2012-10-14 15:59:19

    f[i]:=f[i div 2]+f;

    三个优化

    1.只记录偶数项 所以把n:=n div 2 f[i]:=f+f[i div 2];

    2.高精度压10位

    3.先算数据中最大的 比他小的就不必再算 直接输出f即可

    三个优化=秒杀

  • 0
    @ 2012-10-11 20:17:14

    高精度是个问题啊 费了不时间 好歹最后写了个简洁明了的

    贴一下

    const oo=10000;

    type arr=array[0..21] of longint;

    var f:array[0..1500000] of arr;

      a,b,c:arr;

      i,j,n,l,max:longint;

    procedure calc(var c,a,b:arr);

    var i,j:longint;

    begin

    fillchar(c,sizeof(c),0);

    for i:=1 to 20 do

    begin

      c:=c+(a[i]+b[i]) div oo;

      c[i]:=c[i]+(a[i]+b[i]) mod oo;

    end;

    end;

    procedure print;

    var i,j:longint;

    begin

    for i:=20 downto 1 do

    if f[n,i]0 then break;

    write(f[n,i]);

    dec(i);

    for j:=i downto 1 do

    begin

    if f[n,j]

  • 0
    @ 2009-11-09 16:41:01

    好猥琐的题目

  • 0
    @ 2009-11-07 11:57:13

    超级压位,看看这个吧,压了18位(如有雷同,纯属无聊)

    const maxn=3000000;

    mom=1000000000000000000;

    type atype=array[0..3]of int64;

    var i,j,k,n,max:Longint;

    sum:array[0..maxn shr 1]of atype;

    num:array[0..24]of longint;

    procedure print(a:atype);

    var i,j:Longint;

    K:int64;

    begin

    write(a[a[0]]);

    for i:=a[0]-1 downto 1 do

    begin

    k:=mom div 10;

    repeat

    write(a[i] div k mod 10);

    k:=k div 10;

    until k=0;

    end;

    end;

    procedure add(var a:atype;b:atype);

    var i,j:longint;

    k:int64;

    begin

    if a[0]0 then

    begin

    inc(a[0]);

    a[a[0]]:=k;

    end;

    end;

    begin

    fillchar(num,sizeof(num),0);

    max:=0;

    repeat

    inc(num[0]);

    readln(num[num[0]]);

    if num[num[0]]>max then max:=num[num[0]];

    until eof;

    n:=max;

    fillchar(sum[0],sizeof(sum[0]),0);

    sum[0,0]:=1;

    sum[0,1]:=1;

    for I:=1 to n shr 1 do

    begin

    sum[i]:=sum[i shr 1];

    add(sum[i],sum);

    end;

    for i:=1 to num[0] do

    begin

    print(sum[num[i] shr 1]);

    writeln;

    end;

    end.

  • 0
    @ 2009-11-04 22:01:34

    太猥琐.....

    交了7遍,,!

  • 0
    @ 2009-11-01 22:20:28

    直到不能再什么嘛……破题!

  • 0
    @ 2009-10-31 15:53:59

    超级压位~~ 256进制

    Program Vijos_P1136;

    Var

    a: Array [0..3000000] Of Array [0..22] Of Byte;

    b, c: Array [0..51] Of Byte;

    y: Array [1..1000] Of dWord;

    i, j, t, n, x, z: dWord; w: Word;

    Begin

    n:=0; z:=0;

    While Not(Eof) Do Begin

    Inc(z); ReadLn(y[z]); y[z]:=y[z] Shr 1;

    If y[z]>n Then n:=y[z]

    End;

    FillByte(a[0], 23, 0);

    a[0][0]:=1; a[0][1]:=1;

    For i:=1 To n Do Begin

    FillByte(a[i], 23, 0);

    t:=i Shr 1; w:=0; a[i][0]:=a[0];

    For j:=1 To a[i][0]+1 Do Begin

    Inc(w, a[j]+a[t][j]);

    a[i][j]:=Lo(w); w:=Hi(w)

    End;

    If a[i][a[i][0]+1]>0 Then Inc(a[i][0])

    End;

    For x:=1 To z Do Begin

    n:=y[x];

    FillByte(b, 52, 0); FillByte(c, 52, 0);

    b[0]:=1; b[1]:=1;

    For i:=1 To a[n][0] Do Begin

    w:=0;

    For j:=1 To b[0]+3 Do Begin

    Inc(w, a[n][i]*b[j]);

    Inc(c[j], w Mod 10);

    Inc(c[j+1], c[j] Div 10); c[j]:=c[j] Mod 10;

    w:=w Div 10

    End;

    w:=0;

    For j:=1 To b[0]+3 Do Begin

    Inc(w, b[j] Shl 8);

    b[j]:=w Mod 10;

    w:=w Div 10

    End;

    Inc(b[0], 3); While b[b[0]]=0 Do Dec(b[0])

    End;

    c[0]:=51; While c[c[0]]=0 Do Dec(c[0]);

    For j:=c[0] DownTo 1 Do Write(c[j]);

    WriteLn

    End

    End.

  • 0
    @ 2009-10-28 21:12:40

    我敢肯定,数据超过了50位,为此我花了一天多啊

信息

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