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

UVA 12627 气球胀啊胀

程序员文章站 2022-06-03 14:40:02
...

题目在此

题意:第0个小时有一个红气球,每过一个小时,一个红气球膨胀为3个红球和1个蓝球
一个蓝球膨胀为4个蓝球,排成下图的样子,问过了k小时,第a行到第b行有多少个红球

看下题目里的图,把每个图十字分开,就很容易发现k和k+1的关系
除了右下角全是蓝色以外,剩下都是复制

UVA 12627 气球胀啊胀
f[k][i] 表示第k个小时,前i行有多少个红球
当i在上半区(1到(1<<(k-1))行)的时候,气球是复制的k-1的状态,只需 *2即可
。。。下。。。。。。,把上半区的全加上,再加上k-1时前(i-上半区行数)行的气球
c[k]=第k个小时红色气球总数

UVA 12627 气球胀啊胀

答案输出f[k][b]-f[k][a-1]即可

UVA 12627 气球胀啊胀

#include<cstdio>
#include<iostream>
#include<algorithm>
typedef long long LL;
using namespace std;
const int N=40000;
int i,k,a,b;
LL c[40];

LL f(int k,int i){
    if (i<=0)return 0;
    if (k==0)return 1;
    if (i<=(1<<(k-1)))return f(k-1,i)<<1;
    return c[k-1]*2+f(k-1,i-(1<<(k-1)));
}

int main(){
    //freopen("fuck.in","r",stdin);
    int T;scanf("%d",&T);
    c[0]=1;for (int i=1;i<=31;i++)c[i]=c[i-1]*3;
    for (int cas=1;cas<=T;cas++){
        scanf("%d%d%d",&k,&a,&b);
        printf("Case %d: %lld\n",cas,f(k,b)-f(k,a-1));
    }
    return 0;
}