2020.7 月赛题解

Xiejiadong edited 2 月前

花絮

关于奖品

为了庆祝 EOJ 月赛题目第一次被大规模 AK ,我们决定为所有 AK 比赛的选手发放奖品。

# Tag Idea Developer Tester
A 贪心 文法二义性 Xiejiadong 10185102223 10185102223 Kilo_5723 yanghong bingoier changtiaoraplanqiu
B 数学 模拟 Once bingoier Kilo_5723 yanghong 10185102223 changtiaoraplanqiu
C 模拟 二维前缀和 Once yanghong Kilo_5723 10185102223 changtiaoraplanqiu bingoier
D 哈希 Once Once Kilo_5723
E 数学 构造 cs2017 Xiejiadong Kilo_5723

Problem A 打字机

First Solved:10185101281

操作 $1$ 和操作 $3$ 结合可得:可以把一个 $X$ 替换为任意个 $a$ 。

再结合操作 $2$ 可得:可以在每个 $b$ 的前面或后面添加任意个 $a$ 。

下面将 $a$ 的数量记为 # $ a$ ,将 $b$ 的数量记为 # $b$ 。

考虑到规则的特殊性,下面以字符 $b$ 为核心来讨论,不含 $b$ 的纯 $a$ 串是显然可以打出的。

由于只有操作 $2$ 可以生成 $b$ ,所以 $b$ 前面一定有一个对应的(由操作 $2$ 生成的) $a$ 。换言之,考虑 $s$ 的每一个以 $b$ 结尾的前缀,这些前缀一定满足 # $a\ge $ # $b$ ,否则就不能生成 $s$ 。

相应地,如果满足上述条件,有生成 $s$ 的贪心策略:

也就是说,$s$ 的每个前缀满足 # $a\ge $ # $b$ 是 $s$ 能被打字机打出的充要条件。

下面考虑 $a$ 的来源。因为可以在最后一个 $b$ 后面添加任意多的 $a$ ,这些 $a$ 显然都只能通过操作 $1$ 获得(否则必在其后存在 $b$ )。考虑 $s$ 的最后一个以 $b$ 末尾的前缀(去除 $s$ 末尾的一串连续的 $a$ ),可以证明,如果所有 $a$ 的归属都是唯一的,那么这个前缀中必有 # $a=$ # $b$ ,换言之,所有 $a$ (除了 $s$ 末尾的一串连续的 $a$ )都只能通过操作 $2$ 产生。证(说)明如下:

在可以打出 $s$ 的前提下,对于上述前缀,已经有 # $a\ge $ # $b$ 。假设 # $a> $ # $b$ ,根据前面构造 $s$ 时的策略知道,在某个位置会剩余一些未匹配的 $a$ ,并由操作 $1$ 补充。那么这些 $a$ 在哪里呢?构造策略是贪心的,所以这些 $a$ 一定在【与最后一个 $b$ 匹配的 $a$ 】的左边。实际上,最后一个 $b$ 既可以与贪心策略构造的原配匹配,也可以与这些未匹配的,最终由操作 $1$ 产生的 $a$ 配对。所以这些 $a$ 既可以被操作 $1$ 生成,也可以被操作 $2$ 生成。矛盾。这就说明 # $a=$ #$ b$ 。

综上,只需要在代码中记录每个前缀中的 # $a$ 、 # $b$ 并判断大小关系。具体来说是:

时间复杂度 $O(n)$ 。

Comments

Xiejiadong : 这个题目是我们《计算理论》课程的期末作业,是上下文无关文法的二义性理论的简单应用。

10185102223 : 由于原主人公是QQ小方,改成了Cuber QQ后忘记修改输出标准了,所以输出的内容看上去牛头不对马嘴。

Problem B 线上考试

First Solved:blunt_axe

$x$ 个选项的单选题最多需要 $x$ 次提交;

$x$ 个选项的多选题最多需要 $2^x-1$ 次提交(题目保证至少有一个正确选项);

每道题目都是相对独立的,因此只要对每道选择题的最大可能提交次数取个最大值即可。

Problem C OLED

First Solved:150042

分开讨论每一个像素的贡献,可能发现,单个像素可能出现的位置是屏幕上的一个矩形区域。因此,分别统计每一个像素对答案的贡献,使用二维前缀和维护。

时间复杂度 $O(n\cdot m+a \cdot b)$。

Problem D 前缀排序

First Solved:UoA_ZQC

笔者最近在研究 OI 界的东西,所以做了一些考古工作。本题的灵感来源于 1998 年 NOIP 提高组的拼数问题,后来,这道题广泛出现于各种公司面试中,也是贪心必讲的例题。初见这道题会自然猜测,按照数字的字典序排序可以得到最优解,然而当出现一个数字是另一个数字的前缀时,可以很容易构造出反例。例如 $321$ 和 $32$ 拼接的最大值是 $32321$。

这道题的经典做法是排序法,若 $a+b>b+a$,则认为 $a$ 应该排在 $b$ 之前,然后借助各种基于比较的排序方法解决。这个命题的证明留给大家思考。我们解决《前缀排序》这道题也使用了这个命题。

取两个前缀 $A$ 和 $B$,不妨设 $|A|<|B|$。考虑比较 $A+B$ 和 $B+A$ 的字典序大小,由于二者长度相同,所以任务即为找出二者第一个不同的字符。

由于 $A$ 是 $B$ 的前缀,所以令 $B=A+x$,那么 $A+B=A+A+x$,$B+A=A+x+A$。所以我们只需要比较 $x+A$ 和 $A+x$ 的大小。如果第一个不同的字符出现在 $x$ 部分,我们可以通过二分和哈希去找出。如果 $x$ 部分相同,说明 $B$ 由 $A$ 循环构成,把问题转化为比较 $A$ 和 $B \mod A$ 的大小,其中 $B \mod A$ 表示长度为 $|B| \mod |A|$ 的一个前缀,这样做的复杂度可以类比辗转相除法。单次比较的时间复杂度为 $O(\log n)$。整体再用快速排序即可。

时间复杂度 $O(n\log ^2 n)$。

Problem E

First Solved:Petrichorx

需要将所有的约数按照一定的排列,使得相邻的两个数只相差一个质因子。

倘若我们用广义 $X$ 进制编码的形式(大概可以这么命名吧?)来表示每一个因数,即将每一个因数都按照质因数分解的形式,每一位上的数分别表示包含某一个质数的个数。例如可能包含的质数有 $2,3,5,7$ ,则 $600=2^3\cdot 3\cdot 5^2$ 可以用 $(3120)_X$ 来表示。

用这样编码的好处是,我们要求“相邻的两个数只相差一个质因子”,也就是在两个数的编码中有且仅有其中的某一位相差 $1$ 。

这样构造的思路,我们可以从格雷码中学到一些经验,用类似格雷码的方式构造就可以得到一个合法的解了。

Comments

hwj

油条

jasonleft

标程有不

Xiejiadong

比赛阶段所有代码,均已公开。

不太会

地铺

rev_str

板凳

Once

沙发

你当前正在回复 博客/题目
存在问题!