2018 ICPC Asia-East Continent Final

From EOJ Wiki
Revision as of 10:24, 16 December 2018 by Zerol (talk | contribs) (→‎Problem J)
Jump to navigation Jump to search

Replay

ultmaster:

  • 没来。
  • 待更。

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:反复确认题意才读懂的。