Central Europe Regional Contest 2018

From EOJ Wiki
Jump to navigation Jump to search

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 I

Solved by ultmaster. 00:27 (+)

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

Problem J

Solved by zerol. 00:48 (+)

Problem L

Unsolved. (-1)