2018-2019 ICPC, NEERC, Northern Eurasia Finals

今天训练了大家的演技。

Problem A

Solved by zerol & kblack. 04:31 (+5)

Problem E

Solved by ultmaster. 01:27 (+)

题意：🚜 2。要求在棋盘上横平竖直地跳，不能跳到已经跳到过的点，恰好要走 $n$ 步。构造方案。

题解：乱绕一下就好了。可以确定乱绕的路径的一些关键点，然后往里面填一些点。实现起来有些（诡异地）麻烦。在 a1 的问题上 WA 了一次，不过没算罚时。。。

Problem F

Solved by zerol. 00:53 (+)

Problem G

Solved by zerol. 00:18 (+)

Problem J

Unsolved. (-1)

Problem K

Solved by kblack. 02:42 (+3)

题意：维护一个队伍，其中某个会在 $a_i$ 时间到达，并独占 $b_i$ 的时间，动态增加减少，求在 $t$ 时间到达的话，要挂起多久才能安排上。

题解：脑补一下被卡的情况，每个人完事的时间 $t_i = Max_{j \leq i}(a_j+\sum_{k=j}^{i}b_k)$，线段树维护一下就没了。

kblack: 天天写错线段树，还写错离散化，也差不多是时候退役了。

Problem L

Solved by ultmaster. 00:25 (+)

题意：又是熟悉的调度问题。具体题意省略。

题解：好像调度问题不是贪心就是 DP。有反例吗？

Problem M

Solved by kblack. 00:48 (+)

题意：要你造一个简单 MC 地图，使得若干点对之间的可达性与指定图相同。

题解：使用 $(3n-2) \times 3$ 的截面，底部挖 $n$ 个相距洞代表 $n$ 个点，对于原图的每一条边，用一个沟道在第三层进行单向沟通，没了。