Difference between revisions of "Central Europe Regional Contest 2018"

From EOJ Wiki
Jump to navigation Jump to search
Line 32: Line 32:
  
 
$\sqrt{-10^{-12}} = nan$
 
$\sqrt{-10^{-12}} = nan$
 +
 +
== Problem G ==
 +
 +
Upsolved by kblack.
 +
 +
题意:50x100000 的格子,矩形挖空,维护方格连通性。
 +
 +
题解:比较 naive 的想法是用 50 个 set 去维护每行已经挖掉的区间,然后搞个并查集去合并格子;然而值域不大的时候挖掉的区间也是可以用并查集维护的(已经挖掉的向右合并),最大的坑是自己到自己也要求挖过洞。
  
 
== Problem I ==
 
== Problem I ==

Revision as of 06:29, 29 March 2019

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.

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

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

Problem I

Solved by ultmaster. 00:27 (+)

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

Problem J

Solved by zerol. 00:48 (+)

温暖的签到。

Problem L

Unsolved. (-1)