2020.7 月赛题解

Xiejiadong edited 4 年，7 月前

花絮

• 很荣幸，获得了图森未来的长期赞助，接下来的月赛（并不是每月都有？），我们会为优胜的参赛选手提供丰厚的奖品
• 很欣慰，月赛命题组开始有新鲜血液的加入，离学弟们接手月赛也不远了
• 很意外，学弟们的题目似乎太简单了，下次一定加大力度

关于奖品

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

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$ 的贪心策略：

• 从左往右遍历，使每个 $b$ 与其左侧最近的自由的 $a$ 匹配（存在嵌套 $aabb$ 和分离 $abab$ 两种情况），根据条件，存在这样的 $a$ ，这一步对应操作 $2$ 。
• 接下来还有一些未被匹配的 $a$ ，它们一定能通过操作 $1$ 生成。

也就是说，$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$ 并判断大小关系。具体来说是：

• 每个前缀都有 # $a\ge$ # $b$ 。否则 Dead Fang 。
• 最后一个以 $b$ 结尾的前缀有 # $a=$ # $b$ 。否则 Sad Fang 。
• 满足上述条件即为 Happy Fang 。

时间复杂度 $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\mathrm{mod}A$ 的大小，其中 $B\mathrm{mod}A$ 表示长度为 $|B|\mathrm{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

4 年，7 月前

油条

回复 1 0

jasonleft

4 年，7 月前

标程有不

回复 0 0

Xiejiadong

4 年，7 月前

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

回复 0 0

不太会

4 年，7 月前

地铺

回复 0 0

rev_str

4 年，7 月前

板凳

回复 0 0

Once

4 年，7 月前

沙发

回复 0 0