2018-2019 ICPC, NEERC, Northern Eurasia Finals

今天训练了大家的演技。

Problem A

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

题意：给出每局分数的总和，问最大的大比分，并输出小比分。（五局三胜，最后一句赛点 15，其他 25，有加时赛）。

题解：枚举胜负的可能，然后对于溢出的分数贪心的往里面加，能两边一起加更好（能加时就加时）。

zerol: 修了半天不存在（当然也没法证明那个一定对）的 bug，结果我枚举胜负写错了，搞了两个钟头，又一次抹杀了可能性。差点签到失败。

kblack: 我一起检查了，等于我也有责任？

Problem E

Solved by ultmaster. 01:27 (+)

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

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

Problem F

Solved by zerol. 00:53 (+)

题意：构造若干个分母小于 n 且是 n 的因数且的分数和恰好是 1-1/n。

题解：如果 n 是素数的幂显然无解。否则把 n 分解成两个互素的数字 a, b 之积，然后用 exgcd 构造出一组 ax+by=n-1 的解，（大概）可以证明一定存在 x, y 的正整数解。

Problem G

Solved by zerol. 00:18 (+)

温暖的签到。

Problem J

Upsolved by ultmaster. (-1)

题意：给一种词法（没有文法），要求实现一个贪心（最长匹配）的词法分析器，并且将变量名 uglify 并删除尽可能多的空白字符后，文本仍然能被词法分析器所接受。

题解：造一个自动机似乎是不可避免的。由于它只有保留字、标识符和数字，也没有必要去搞什么 DFA，直接建个 Trie，然后同时维护两个标识符和数字的状态即可。返回当前可接受状态时，注意优先级。

问题在于分析完以后如何加空格。由于时间不够 + 意识模糊搞了一堆又是贪心又是 DP 的假算法。

赛后冷静分析之后感觉是这样的：对于每个单词开头的文本后缀，我们直接放在自动机上跑，拿到自动机的第一次接受位置和第二次接受位置。第一次接受位置必然是我们想要的单词（不然没救了），接受完之后自动机状态不归零继续跑，跑到第二次接受位置（如果有的话），由于是贪心匹配的，第二次接受的位置优先级更高。所以在第二次和第一次之间必须要有一个空格空开。于是我们就知道在第几个单词和第几个单词之间一定要有个空格。把所有这样的事件都预处理出来，然后就变成了丽娃河装路灯问题。按右端点排序以后贪心扫一遍就好了。

感觉数据范围还是有点大的，但是跑得快得很。

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