2016弱校联盟十一专场10.5
传送门
A. As Easy As Possible
- 假设固定左端点，那么每次都是贪心的匹配\(easy\)这个单词。
- 从\(l\)开始匹配的单词，将\(y\)的位置标记成有效位置，用主席树维护。
- 如果\(s_l\ne e\)，那么\(l\)与\(l+1\)的匹配结果一致；否则从\(l\)开始匹配到某个位置\(p\)完成单词匹配，我们从\(p+1\)的有效位置继承过来，然后再将\(p\)标记成有效位置即可。
B. Be Friends
- 在二进制下，从高位开始考虑，显然高位相同的分成一组，高位不同的需要每组选一个人，使得异或和最小。
- 在字典树下，显然高位不同的情况下会分成两个分支，所以当出现分支的情况，维护下最小花费即可。
D. Drawing Hell
- 游戏结束时是一个三角剖分，显然任意一种剖分都不会影响结果，所以只需要计算三角剖分的线段数。
- 首先求凸包（假设有\(m\)个点），凸包上的边必然是在三角剖分里面的。
- 凸包里增加第一个点，此时线段数增加\(m\)条。
- 此后每增加一个点，线段数+3。
- 简要证明：若点不落在边上，说明落在一个三角形内部，此时边数+3；若落在线段上，则原线段数被一分为二，同时原线段为两个三角形的边，所以当前点分别与两个顶点连边，所以线段数还是+3。
- 至此可以统计出最后的线段数的奇偶性，即可判断胜负。
- 当所有点构不成凸包时，需要特判。
F. Fibonacci of Fibonacci
H. Hash Collision
- \(f(i,j)\)表示长为\(i\)，哈希值为\(j\)的方案数，然后倍增求即可。
- 但是这题用简单的FFT会爆精度，所以找到了上交的FFT板子支持一定范围内的取模而不爆精度。
I. Increasing or Decreasing