2018 ICPC Asia-East Continent Final
Replay
ultmaster:
- 没来：没怎么看到我会做的题。这一定是因为题目太少了。（甩锅.jpg）
- 前期一直在 200 多名徘徊。
- 好像不管哪里少 20 分钟都能进顺位五啊？为什么又是这种不尴不尬的位置啊？
- 难得的单线作战。
kblack:
- 演爆了。
好像不用女装了？
zerol:
- kblack 虽然演了，但是多次阻止了惨剧发生，修复了队友。（那么修自己的 bug 容易还是修队友的 bug 容易？）
- 难得来了一次，没有遗憾。（那是假的，随便哪里少一发罚时，kblack 就女装了好吗？）
Problem A
Unsolved. (-11)
比赛还剩半小时，无事可做。
Problem C
Solved by zerol. 02:53 (+1)
题意：问一个长度为 200 的 01 串在长为 $10^9$ 的 $|\mu(i)|$ 的数列中第一次出现的位置，或者不存在。
题解：考虑素数的平方的倍数一定是 0，计算答案模 4, 9, 25, 49, 121, 169 的可能的余数，然后 CRT 求出这个数，然后从小到大判断。注意如果可能性太多肯定是无解的（比如全是 0）。
Problem D
Solved by ultmaster. 00:19 (+)
温暖的签到。（被 kblack 抢机了。
Problem F
Solved by kblack. 01:16 (+1)
小学数学题，死于式子抄漏。
Problem H
Unsolved. (-1)
配合演出。
Problem I
Solved by zerol. 01:40 (+)
题意：初始攻击 A 和攻击增长速率 D 均为 0。每一回合 A 会增加 D，然后选择以下的一种：
1. 造成 $A+a_i$ 伤害。
2. $D$ 增长 $b_i$。
3. $A$ 增长 $c_i$。
求最大能造成的总伤害。
题解：倒着 DP。两维状态，一维是之前增加 D 能对之后攻击造成的贡献次数，一维是增加 A 的贡献。复杂度 $O(n^4)$。
zerol：kblack 送我的题。
Problem J
Solved by zerol & kblack. 04:07 (+3)
题意：求 $\max_{p_i} \min_j \{ \sum_{i=1}^n p_ilcp(s_i, s_j) \}$ 其中 $\sum p_i = 1$，也就是说求一个选后缀的概率分布，使得和某一个后缀的 lcp 的期望的最小值最大。
题解：考虑后缀树，每个后缀结点往根的路径上贡献 $p_i$，然后使得后缀结点到根的路径上的和的最小值最大。后缀自动机建后缀树后树形 dp，求出每棵子树的答案。如果遇到后缀结点直接归 0，否则就是子节点的调和平均，往父节点贡献时加上边权。
zerol: 后缀自动机建后缀树没反向插入（还好被 kblack 看出来了），问题是还能过样例。
Problem L
Solved by zerol. 01:14 (+3)
题意：有两种车站，可以花费代价 1 去同一种车站，也可以花费 1 走一条边，问每个点到所有其他点的最短路之和。（保证两两可达）
题解：最大距离不超过 3，并忽略所有同一种车站之间的边。考虑每一个点，到同一种的其他车站代价都是 1。另一种的代价计算然后分两种情况
这个点有度：那么与这个点直接相邻的点代价为 1，否则为 2。
这个点没度：那么另一侧有度的点代价为 2，否则为 3。
zerol：反复确认题意才读懂的。
kblack: 罚时都是我的，自闭签到，为了不女装（逃