UVA 12627 Erratic Expansion

ゝ一世哀愁。 2022-05-16 10:10 81阅读 0赞

## 题目大致意思为 告诉你一个红球为0时状态，已知一个红球每过一个时间会变为文档所示图中的3红1蓝，而蓝球每过一个时间则会变为4个蓝球。问在某一时刻，h1与h2之间的红球有几个。 ##

RT,这一题刚看到的时候毫无思路，仔细观察图后发现，发现肯定是递归。然后找递归公式。先说说我的想法历程，不想看的可以直接到后面看结论。

*i*表示时间，*j*表示第*j*行，*h*\[*i*\]\[*j*\]表示*i*时,*j*行的红色气球  i 表 示 时 间 ， j 表 示 第 j 行 ， h \[ i \] \[ j \] 表 示 i 时 , j 行 的 红 色 气 球   
*h*\[*i*\]\[*j*\]=*h*\[*i*−1\]\[*j*>2*i*−1?*j*−2*i*−1:*j*\]∗2  h \[ i \] \[ j \] = h \[ i − 1 \] \[ j > 2 i − 1 ? j − 2 i − 1 : j \] ∗ 2

于是，我认为直接从开始的地方加到结束即可。

当然妥妥的超时。。。。。。

于是想维护前缀和，发现也不容易。突然发现行的递归能写，多半和的递归也能写。

找了一段时间的规律后，得出

*i**f*(*j*>2*i*−1)  i f ( j > 2 i − 1 )   
*s*\[*i*\]\[*j*\]=*s*\[*i*\]\[2*i*−1\]\+*s*\[*i*−1\]\[*j*−2*i*−1\]  s \[ i \] \[ j \] = s \[ i \] \[ 2 i − 1 \] + s \[ i − 1 \] \[ j − 2 i − 1 \]   
*e**l**s**e*  e l s e   
*s*\[*i*\]\[*j*\]=*s*\[*i*−1\]\[*j*\]∗2  s \[ i \] \[ j \] = s \[ i − 1 \] \[ j \] ∗ 2   
  
合并一下第一行,得到  
  
*s*\[*i*\]\[*j*\]=*s*\[*i*−1\]\[2*i*−1\]∗2\+*s*\[*i*−1\]\[*j*−2*i*−1\]  s \[ i \] \[ j \] = s \[ i − 1 \] \[ 2 i − 1 \] ∗ 2 + s \[ i − 1 \] \[ j − 2 i − 1 \]   
又 发现  
*b**e**c**a**u**s**e**s*\[*i*\]\[2*i*−1\]=3*i*−1∗2  b e c a u s e s \[ i \] \[ 2 i − 1 \] = 3 i − 1 ∗ 2   
故得出代码

#include <stdio.h>
    #define LL long long
    LL QWQ[31];
    LL QOQ[31];
    LL QAQ(int i,int j){
        if(j==0)
            return 0;
        if(i==0&&j==1)
            return 1;
        if(j>QWQ[i-1])
            return (QOQ[i-1]<<1)+QAQ(i-1,j-QWQ[i-1]);
        else
            return QAQ(i-1,j)<<1;
    }
    int main(){
        //a[i][j]=a[i-1][j>2^(i-1)?j-2^(i-1):j]*2
        /*
         *
         * if(j>2^(i-1))
         *    a[i][j]=a[i-1][j-2^(i-1)]
         * else
         *    a[i][j]=a[i-1][j]*2
         * a[i][j]=a[i-1][]
         jmax=2^i;
    
    
    
    
         if(j>2^(i-1))
             s[i][j]=s[i][2^(i-1)]+s[i-1][j-2^(i-1)]
        else
            s[i][j]=s[i-1][j]*2
    
        s[i][j]=s[i-1][2^(i-1)]*2+s[i-1][j-2^(i-1)]
        because s[i][2^(i-1)]=3^(i-1)*2
    
    
         */
        //freopen("data.txt","r",stdin);
        //freopen("datas.txt","w",stdout);
        QWQ[0]=1;QOQ[0]=1;
        for(int i=1;i<31;i++)
            QWQ[i]=QWQ[i-1]*2;
        for(int i=1;i<31;i++)
            QOQ[i]=QOQ[i-1]*3;
        int T;
        scanf("%d",&T);
        int times=0;
        while(T--){
            times++;
            int k,a,b;
            LL sum=0;
            scanf("%d %d %d",&k,&a,&b);
            sum=QAQ(k,b)-QAQ(k,a-1);
            printf("Case %d: ",times);
            printf("%lld\n",sum);
        }
    
    }