題意：一開始有1個紅氣球，每小時一個紅氣球都會變成3個紅氣球和1個藍氣球，1個藍氣球會變成4個藍氣球，問k個小時后a行到b行的紅氣球的數量。

思路：遞推。a為偶數時，計算a+1到b以及a本行的紅氣球數。b為奇數時，計算a到b-1以及b本行的紅氣球數。剩下情況的都是從上一次的氣球數*3得到的。

code：

#include <bits/stdc++.h> using namespace std; typedef long long ll; int k,a,b; ll sol(int k,int a,int b) {if (a>b) return 0;if (k==0) return 1;if (!(a&1)) return sol(k,a+1,b)+sol(k-1,a/2,a/2);if (b&1) return sol(k,a,b-1)+2*sol(k-1,(b+1)/2,(b+1)/2);return 3*sol(k-1,(a+1)/2,b/2); } int main() {int T;scanf("%d",&T);for (int ca=1;ca<=T;ca++){scanf("%d %d %d",&k,&a,&b);printf("Case %d: %lld\n",ca,sol(k,a,b));} }

總結

以上是生活随笔為你收集整理的uva 12627——Erratic Expansion的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。