UVA 12627 - Erratic Expansion

一个红球能够分裂为3个红球和一个蓝球。

一个蓝球能够分裂为4个蓝球。

分裂过程下图所看到的:

设当前状态为k。下一状态为k。

k的第x行红球个数 * 2 ⇒ k第2*x行的红球个数。

k的第x行红球个数 ⇒ k第2*x+1行的红球个数。

特殊处理一下上下边界。递归求解就能够搞定了。

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <stdlib.h>

#include <algorithm>

#include <ctype.h>

#include <iostream>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <assert.h>

#include <time.h>

#include <sstream>

typedef long long LL;

const int INF = 500000001;

const double EPS = 1e-9;

const double PI = acos(-1.0);

using namespace std;

long long gao(int k, int a, int b)

{

    if(a > b) return 0;

    if(k == 0)

    {

        return 1;

    }

    int left = 0, right = 0;

    if(a % 2 == 0)

    {

        left = a;

        a++;

    }

    if(b % 2 == 1)

    {

        right = b;

        b--;

    }

    long long ans = gao(k-1, (a + 1) / 2, b / 2) * 2 + gao(k - 1, (a + 1) / 2, b / 2);

    if(left) ans += gao(k-1, left / 2,  left / 2);

    if(right) ans += gao(k-1, (right + 1) / 2,  (right + 1) / 2) * 2;

    return ans;

}

int main()

{

    #ifdef _Te3st

        freopen("test0.in", "r", stdin);

        freopen("test0.out", "w", stdout);

        srand(time(NULL));

    #endif

    int T, k, a, b;

    scanf("%d", &T);

    for(int i = 1; i <= T; i++)

    {

        scanf("%d %d %d", &k, &a, &b);

        printf("Case %d: %lld\n", i, gao(k, a, b));

    }

    return 0;

}