UVa12627 例题8-12 奇怪的气球膨胀

原文链接:UVA12627

---

题目大意：

一开始有一个红气球，每小时，一个红气球会变成3个红气球和1个蓝气球，而一个蓝气球会变成4个蓝气球（如图所示）。求经过k小时后，第A~B行一共有多少个红气球？

---

参考博客：

http://blog.csdn.net/zyq522376829/article/details/46591661

---

解题思路：

根据题目的类型，理所当然的想到需要用分治的思想。但是一直不知道应该怎么分。后来看了紫书上给的题解之后，看了递推公式之后，感觉好简单。当然要自己想出递推公式却不一定简单。

首先设f(k,i)为k小时之后，上面i行中红气球的数量。则所求气球的数量就是f(k,B) - f(k,A-1)，很容易理解。接下来就是f(k,i)怎么求得问题。根据图形可以看出：当i ≥2^(k-1) (也就是i大约等于当前图形的一半长度时)，f(k,i)包含了两个k-1时刻的图形（上半部分）和k-1时刻图形的前i-2^(k-1)行。当i<2^(k-1)时，就是k-1时刻图形的前i行包含红气球的2倍，递推公式如下（偷偷的截一张图，哈哈哈哈哈嗝）。

c(k) = 3c(k-1) = 3^k

至于c(k)表示的就是k时刻图形所有红气球的数量，由于每次变化时每个红色的气球都会分裂出三个红色的气球，所以可以知道c(k)=3^k，详细代码如下。

还有另一种递推方法，即令g(k,i)表示为k时刻图形最后i行中红气球的数目，关于g(k,i)的递推公式，我的理解跟紫书上给的有点歧义，所以就没按g的方法写。读者可以自行思考，听说按照g(k,i)写更快一点。

---

代码：

#include<iostream>
#include<cmath>

using namespace std;

long long f(int k, int r);

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T, kase = 0;
    cin >> T;
    while (T--) {
        int k, a, b;
        cin >> k >> a >> b;
        cout << "Case " << ++kase << ": " << f(k, b) - f(k, a - 1) << endl;
    }
    return 0;
}

long long f(int k, int r)
{
    if (r <= 0) return 0;
    if (k == 0) return 1;       //当k=1时，f(k,r) = 1
    int n = pow(2, k - 1);      
    //当i >= 2^(k-1),f(k,r) = f(k - 1,i - 2^(k-1)) + 2*c(k-1) ，其中c(k) = pow(3,k):每次一个红的都会变成三个
    if (r >= n) return f(k - 1, r - n) + 2 * pow(3, k - 1);
    else return 2 * f(k - 1, r);        //i < 2^(k-1) ,f(k,r) = 2 * f(k-1,r)
}