UVA

UVA 12627 气球胀啊胀

Posted by Cww97 on 2016-02-17

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/50681021
题目在此

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

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

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

这里写图片描述
这里写图片描述

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

这里写图片描述
这里写图片描述
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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;
}