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)

题意:给出每局分数的总和,问最大的大比分,并输出小比分。(五局三胜,最后一句赛点 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$ 个点,对于原图的每一条边,用一个沟道在第三层进行单向沟通,没了。