首页 > 代码库 > Uva 12627 Erratic Expansion（递归）
Uva 12627 Erratic Expansion（递归）
这道题大体意思是利用一种递归规则生成不同的气球，问在某两行之间有多少个红气球。
我拿到这个题，一开始想的是递归求解，但在如何递归求解的思路上我的方法是错误的。在研读了例题上给出的提示后豁然开朗（顺便吐槽一下算法竞赛第二版在这这道题目上（P246）提示写的有问题，g(k,i)=2g(k-1,i-2^(k-1))+c(k-1) ，他把c(k-1)写成了c(k)...我纠结这个纠结了好久）
根据题目提示，这道题可以用f(k,i)表示k小时后最上边i行的红气球总数
那么我们的答案就可以表示为f(k,b)-f(k,a-1)
如何求f(k,i)?
这里我们通过观察，在k小时后所分成的四部分气球中，最右下角区域的气球是跟其他区域气球不相同的。因此我们可以分成两种情况（i在上半部分和i在下半部分）。
当i<2^(k-1),f(k,i)=2*f(k-1,i)
当i>=2^(k-1),f(k,i)=c(k-1)+f(k-1,i-2^(k-1))
其中c(k-1)代表完整的那部分的红气球数，也就是k-1小时后的红气球数。
由气球构造方式可得递推式：c(k)=3c(k-1),c(0)=1，可知这是个等比数列，求得c(k)=3^k
至此我们就可以得到我们想要的答案了。
同理，我们也可以利用g(k,i)表示k小时后最下边i行的红气球总数，把我们的答案用g(k,i)表示出来，这里不再叙述。
以下是完整代码：
1 #include <cstdio> 2 using namespace std; 3 long long c(int k){ 4 long long sum = 1; 5 while(k--)sum*=3; 6 return sum; 7 } 8 long long g(int k, int i) { 9 if(i == 0) return 0;10 if(k == 0) return 1;11 12 int k2 = 1 << (k-1);13 if(i >= k2) return 2*g(k-1, i-k2) + c(k-1);14 else return g(k-1,i);15 }16 long long f(int k,int i){17 if(i==0)return 0;//注意这两处边界的处理18 if(k==0)return 1;19 int t = 1 << (k-1);20 if(i<t)return 2*f(k-1,i); 21 else return 2*c(k-1) + f(k-1,i-t);22 }23 int main(){24 int T, k, a, b;25 scanf("%d",&T);26 for(int kase = 1; kase <= T; kase++) {27 scanf("%d%d%d",&k,&a,&b);28 printf("Case %d: %lld\n",kase,f(k, b) - f(k, a-1));29 //int t =1 << k;30 //printf("Case %d: %lld\n",kase,g(k, t-a+1) - g(k,t- b));31 }32 return 0;33 }
1 long long c(int i) { return i == 0 ? 1 : c(i-1)*3; }
另外代码仓库中c的求法比较简洁，值得学习。
Uva 12627 Erratic Expansion（递归）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。