【CF 676B Pyramid of Glasses】模拟,递归

时间:2022-01-11 07:01:50

题目链接:http://codeforces.com/problemset/problem/676/B

题意:一个n层的平面酒杯金字塔,如图,每个杯子的容量相同。现在往最顶部的一个杯子倒 t 杯酒,求流动结束后有多少个杯子被装满。

【CF 676B Pyramid of Glasses】模拟,递归

思路:每个局部的两代三个杯子的流动过程是一致的,因此可以用递归来模拟求解。

具体为:设add(cur, i, l)执行“往第 i 个杯子倒cur量的酒”,附加信息: i 位于第 l 层。若执行完剩余了surplus量的酒,则往 i 的下一层左右两侧的杯子各倒surplus/2量的酒;若无剩余,则抵达递归基。

关于 i 与它下一层的对应关系:我对所有杯子从1开始逐层从左到右编号,因此 i 的左下为i+l, 右下为i+l+1。

关于surplus的值:按照CF的题解的做法,如果有n层,则把每个杯子的容量记为volume = 2 ^ n份,这样能保证即使到第n层每次的cur也都整数。

维护数组v, 其中v[i] 记录当前第 i 个杯子中已有的酒量,若有剩余,则surplus = cur - (volume - v[i])。

最后统计下所有n*(n+1)/2个杯子中v[i]==volume的个数即可。

 #include <cstdio>
#include <cmath>
using namespace std;
const int MAX_N = ; int t, n;
int num;
int v[MAX_N*(MAX_N+)/ + ];
int volume;
int cnt; void add(int cur, int i, int l){
if(l > n) return ;
if(cur + v[i] <= volume){//最多加满当前的,不会溢出
v[i] += cur;
return ;
}
int surplus = cur - (volume - v[i]);//有溢出
v[i] = volume;
add(surplus/, i+l, l+);
add(surplus/, i+l+, l+);
} int main()
{
scanf("%d%d", &n, &t);
num = n*(n+)/;
volume = pow(, n);
int cur = volume * t;
cnt = ;
add(cur, , );
for(int i=; i<=num; i++){
//printf("%d %d\n", i, v[i]);
if(v[i] == volume) cnt++;
}
printf("%d\n", cnt);
return ;
}