2018-2019 ICPC, NEERC, Northern Eurasia Finals

From EOJ Wiki
Jump to navigation Jump to search

今天训练了大家的演技。

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$ 个点,对于原图的每一条边,用一个沟道在第三层进行单向沟通,没了。