Central Europe Regional Contest 2018

Problem A

Solved by ultmaster. 02:03 (+)

题意：有一个词库，每种单词有无限个。有一个长串，每次操作从词库里挑一个单词把它贴在长串能匹配的位置上。问最少次数覆盖完整个串。

题解：考虑 f[i] 表示 i 的前缀的答案。显然要找到最小的串使得 s[k...i] 在词库中找得到，那么答案就是 f[k-1], f[k], ..., f[i-1] 中最小的。这一部分用个线段树维护就可以。找 k 的过程可以考虑哈希，由于字符串总长有保证，不同的长度不会太多，所以可以按照长度枚举，在 set 中查找，复杂度是 $O(n \sqrt{n} \log n)$。比题解里最慢的方法还要慢。

Problem B

Solved by zerol. 03:57 (+)

题意 & 题解：很裸的动态图连通性，可以离线。参考这个。

Problem C

Solved by ultmaster. 01:06 (+1)

题意：给一个长度为 40 的 01 串，每次操作是选一个 k 将这个串和其本身右移 k 位位或。求最少几次变成全 1。

题解：第二签到的题。注意到最坏情况下也只要 6 次。不妨迭代加深。事实上，$40^6$ 是不大的，而且根本跑不满。

Problem D

Solved by kblack. 04:39 (+4)

题意：👦🚮🍽，🐶🏉，⌚。

题解：分为两种情况：盘子掉在地上了，🐶捡起来再回来，时间好算的；🐶跳起来接到某个高度的盘子（同时决定了时间和距离），高度可以二分，然后判断两个坐标的时间是否来得及（全速奔跑和满速起跳）。

这🐶的速度和🍽的速度竟然不一致，伽利略的棺材板压不住了。

$\sqrt{-10^{-12}} = nan$

Problem G

Upsolved by kblack & zerol.

题意：50x100000 的格子，矩形挖空，维护方格连通性。

题解：比较 naive 的想法是用 50 个 set 去维护每行已经挖掉的区间，然后搞个并查集去合并格子；然而值域不大的时候挖掉的区间也是可以用并查集维护的（已经挖掉的向右合并），最大的坑是自己到自己也要求挖过洞。

Problem I

Solved by ultmaster. 00:27 (+)

拿到题目的时候比赛已经快过去半个小时了。

Problem J

Solved by zerol. 00:48 (+)

温暖的签到。

Problem L

Unsolved. (-1)