首页 > 代码库 > UVa12627 Erratic Expansion (分治)

UVa12627 Erratic Expansion (分治)

2024-08-14 07:48:54   218人阅读

链接：http://vjudge.net/problem/UVA-12627

 

分析：看图找规律，然后推式子。我们用f(k,i)表示k小时之后前i行红气球总数（i从1开始数）。容易看出k小时后，图分成四块，右下部分是没有红气球的，其它三部分相同。因此容易得到，

当i>(1<<(k-1))的时候，上半部分红气球总数为c(k-1)*2,下半部分红气球总数为f(k-1,i-(1<<(k-1)))，所以总的红气球总数为c(k-1)*2+f(k-1,i-(1<<(k-1)))个；当i<=(1<<(k-1))时，此时的k小时后前i行红气球总数相当于k-1小时后，前i行红气球总数的两倍f(k-1,i)*2,边界条件是先检查f(k,0)=0然后检查f(0,i)=1。

 1 #include <cstdio> 2  3 int k, a, b; 4 long long c[35]; 5  6 long long f(int k, int i) { 7     if (!i) return 0; 8     if (!k) return 1; 9     if (i <= (1<<(k-1))) return f(k-1, i) * 2;10     if (i > (1<<(k-1))) return 2 * c[k-1] + f(k-1, i-(1<<(k-1)));11 }12 13 int main() {14     c[0] = 1;15     for (int i = 1; i < 30; i++) c[i] = c[i-1] * 3;16     int T;17     scanf("%d", &T);18     for (int kase = 1; kase <= T; kase++) {19         printf("Case %d: ", kase);20         scanf("%d%d%d", &k, &a, &b);21         long long ans = f(k, b) - f(k, a-1);22         printf("%lld\n", ans);23     }24     return 0;25 }

 

UVa12627 Erratic Expansion (分治)


联系
我们