CSU-ACM2017暑期训练3-递推与递归 Erratic Expansion

Erratic Expansion

由题可看出，第 n 小时的扩张，都保留第 n−1 小时的状态，并将其复制两遍，分别置于新的大方块的右上侧和左下侧；右下侧则填充蓝气球。
利用这样的性质，可以利用第 A 行及其以下的所有红气球数量减去第 B 行及其以下所有的红气球数量来得到结果。
为此，设计函数 c(k)=3k 和函数 g(k,i)，分别表示第 k 小时的红气球数量，以及第 k 小时的第 i 行及其以下所有的红气球的数目。
容易看出，如果 i≤2k−1，红气球的数量就等于上一小时的第 i 行及其以下所有红气球的数目乘2，再加上上一小时红气球的总数。
如果 i>2k−1，红气球的数量就相当于上一小时中的第 i−2k−1 行及其以下所有红气球的数目。简单地说，就是把第 i 小时的左下侧看做上一小时的状态，红气球数就试它所对应的下侧若干行的红气球数。
这样一来，就可以使用表达式 g(k,A)−g(k,B+1) 求出答案了。

#include <iostream>
#include <cstdio>
using namespace std;
long long c(int k){
    long long ans = 1;
    for(int i = 1; i <= k; i++)
        ans *= 3;
    return ans;
}
long long g(int k, int i){
    if(k==0 && i == 1)
        return 1;
    else if(k == 0)
        return 0;
    if(i == ((1<<k) + 1)){
        return 0;
    }
    if(i > (1<<(k - 1))){
        return g(k - 1, i - (1<<(k - 1)));//返回
    }
    else{
        return g(k - 1, i) * 2 + c(k - 1);
    }
}
int main(){

    int t;
    while(cin >> t){
        for(int i = 1; i <= t; i++){
            int k, a, b;
            scanf("%d%d%d", &k, &a, &b);
            printf("Case %d: %lld\n", i, g(k,a) - g(k,b+1));
        }
    }

    return 0;
}