[UVa12627]Erratic Expansion
算法入门经典第8章8-12(P245)
题目大意:起初有一个红球,每一次红球会分成三红一蓝,蓝球会分成四蓝(如图顺序),问K时的时候A~B行中有几个红色。
试题分析:很容易注意到,按照此种规律,矩形的左上角、右上角、左下角总是与上一个时刻的图形一样,这是我们分治的基础。
那么,既然得到了上面的,利用前缀和的思想,设f(k,i)表示k时刻从1到i行的红色数量,则答案为f(k,B)-f(k,A-1)
我们知道,第i个时刻的正方形边长为2^k,那么当i小于等于2^k时,就是上一个同样行的红色的数量*2(因为拓展了)
那么如果i大于2^k时,我们要怎么办呢?
首先,最显而易见的是左上角与右上角都是上一个时刻的图形,那么k时刻的红色总和为3^k,所以左上角右上角加起来就是2*(3^(k-1))。
那么剩下的那些也就是同上面的一样计算,也就是f(k-1,i-2^(k-1))了。
代码:
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;#define LL long longinline LL read(){
LL x=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const LL INF=9999999;
const LL MAXN=100000;
LL T; LL C[MAXN+1];
LL Case;
LL K,N,M;
LL F(LL k,LL p){
if(p==0) return 0;
if(k==0) return 1;
if(p>=(1<<(k-1))) return F(k-1,p-(1<<(k-1)))+2*C[k-1];
else return 2*F(k-1,p);
}int main(){
T=read();C[0]=1;
for(LL i=1;i<=31;i++) C[i]=C[i-1]*3;
while(T--){
++Case;
K=read(),N=read(),M=read();
printf("Case %d: %lld\n",Case,F(K,M)-F(K,N-1));
}
return 0;
}