欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVa12674 Erratic Expansion (递归+规律)

程序员文章站 2022-03-11 23:47:38
...

题目链接:https://vjudge.net/problem/UVA-12627

题目大意:告诉你膨胀气球的规则,让你求出第i行到第j行红气球的个数

膨胀规则如下:

UVa12674 Erratic Expansion (递归+规律)

我们不难发现其中存在的规律,然后递归求解就可以了

注意:数据要用long long存,注意特殊情况,在代码中有标注。熟悉递归的用法

代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll solve(int k,int a,int b)//注意long long
{
    if(a>b) return 0;
    if(k==0) return 1;
    int l=0,r=0;
    if(a%2==0){ //存在一个a不是奇数行的时候,拿出来特殊计算奇数行,a++
        l=a;
        a++;
    }
    if(b%2==1){//b同理
        r=b;
        b--;
    }
    ll ans=solve(k-1,(a+1)/2,b/2)*2+solve(k-1,(a+1)/2,b/2);
    if(l) ans+=solve(k-1,l/2,l/2);
    if(r) ans+=solve(k-1,(r+1)/2,(r+1)/2)*2;

    return ans;
}
int main()
{
    int T;while(~scanf("%d",&T)){
        int k,a,b;
        for(int i=1;i<=T;i++){
            scanf("%d%d%d",&k,&a,&b);
            printf("Case %d: %lld\n",i,solve(k,a,b));
        }
    }
}