欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVa12627 Erratic Expansion(递归/找规律)

程序员文章站 2022-03-04 21:08:04
...

题目链接
UVa12627 Erratic Expansion(递归/找规律)
1.初始有一个红气球,每过一个小时,一个红气球会变成3个红气球和1个蓝气球,一个蓝气球会变成4个蓝气球,如图所示。初始有一个红气球,求经过k个小时以后,第A行到第B行一共有多少个红气球

2.一看就是找规律的题目嘛,本来想到的是记录每行红气球的变化,确实有规律,但是必须由前一个状态求得,而且要用数组记录,但是看了一下k的范围,最大是30的话是1e9,显然数组开不了那么大。看了一下LRJ的分析,是按照前i行的红气球总数来找规律的,类似于前缀和区间[L,R],即f( R )-f(L-1)。那么这样找一下规律后:
UVa12627 Erratic Expansion(递归/找规律)
3.设f(k,i)表示k小时后,第i行之前的红气球个数之和。那么我们不难得到:
当i<=2k-1时,f(k,i)=2*f(k-1,i)
当i>2k-1时,f(k,i)=f(k,2k-1)+f(k-1,i-2k-1)
注意到当i为0时直接返回0,当k为0时返回1

4.但是这样写却超时了!因为下面f(k,2k-1)相当于每个数都算了两遍,因此得想办法更快的,注意到f(k,2k-1)=2*f(k-1,2k-1),且都是上个状态的最后一个数,那么不难发现1,3,9,27…,则最后一行可以直接由3k推导得到,最后再乘2即可

#include <iostream>
using namespace std;
typedef long long ll;

ll quick_pow(ll x,ll n){
    ll ans=1;
    while(n){
        if(n&1) ans*=x;
        x*=x;
        n>>=1;
    }
    return ans;
}

ll f(int k,int i){
    if(i==0) return 0;
    if(k==0) return 1;
    ll x=1<<(k-1);
    if(i<=x) return 2*f(k-1,i);
    else return 2*quick_pow(3,k-1)+f(k-1,i-x);
    //else return f(k,x)+f(k-1,i-x);
}

int main()
{
    int t,k,a,b,kase=0;
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>k>>a>>b;
        cout<<"Case "<<++kase<<": "<<f(k,b)-f(k,a-1)<<endl;
    }
    return 0;
}