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

  • 时间:
  • 浏览:2
  • 来源:uu快3app赚钱_uu快3大小计划注册

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

关于 i 与它下一层的对应关系:我对所有杯子从1结束了逐层从左到右编号,有时候 i 的左下为i+l, 右下为i+l+1。

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

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

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

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

思路:每个局部的两代有另另4个多杯子的流动过程是一致的,有时候还要用递归来模拟求解。

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