UVa12627 Erratic Expansion(递归/找规律)
程序员文章站
2022-03-04 21:08:04
...
题目链接
1.初始有一个红气球,每过一个小时,一个红气球会变成3个红气球和1个蓝气球,一个蓝气球会变成4个蓝气球,如图所示。初始有一个红气球,求经过k个小时以后,第A行到第B行一共有多少个红气球
2.一看就是找规律的题目嘛,本来想到的是记录每行红气球的变化,确实有规律,但是必须由前一个状态求得,而且要用数组记录,但是看了一下k的范围,最大是30的话是1e9,显然数组开不了那么大。看了一下LRJ的分析,是按照前i行的红气球总数来找规律的,类似于前缀和区间[L,R],即f( R )-f(L-1)。那么这样找一下规律后:
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;
}
上一篇: php如何设置日志输出