2012-2013 Northwestern European Regional Contest (NWERC 2012)

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个质因子，就可以用折半做。