![打败]( "打败")
B - Beer Pressure
- \(dp(t, p_1, p_2, p_3, p_4)\)表示总人数为\(t\)，\(p_i\)对应酒吧投票人数的概率。
- 使用滚动数组优化掉一维空间。
- 总的时间复杂度为\(O(\frac{w^n}{n!})\)
C - Cycling
- 最坏情况下（每次到light位置都停下），总的时间花费少于6000s。
- \(10 \le R_i, G_i\)，那么每个灯的周期不超过300。
- 减速的情况只有当在light位置时，否则都是加速度运动。这是为了在同等距离的情况下末速度尽可能大，意味着在下一个light位置时，有更大的初速度。
- 对于每个起点，在s-t图像上，存在一些区间，使得从当前位置一直做加速运动而不会遇到红灯情况。
D - Digital Clock
- 枚举开始时间。
- 对于每位上的显示，记录好的位置以及坏的位置，最后不能存在交集。
F - Foul Play
- 题目保存对于打败\(1\)的所有\(x\)，都存在对应的\(y\)打败\(x\)，而1打败\(y\)。同时保证1至少能打败一半的队伍。
- 对于1能的打败的队伍\(y\)，找出所有\(y\)能打败的\(x\)，让\(y\)和这些\(x\)尽可能凑成一组。这样就保证了1最后会其中一队\(y\)打决赛。
H - Hip To Be Square
- 若区间\([a, b]\)存在平方数，直接返回算术平方根即可。
- 对于区间内的数，只关心指数为奇数的质因子。若质因子只被一个数包含，那么这个数不需要考虑。若质因子只有两个数的指数为奇数，那么这两个数要捆绑在一起。因为答案只保证开方后不超long long，所以在消除这一步需要用分解质因数做。
- 经过上述操作，每个不包含的平方数的区间内最多只有40个数，涉及28个质因子，就可以用折半做。
04-26 17:52