油条
2020.7 月赛题解
Xiejiadong edited 4 年，5 月前
花絮
- 很荣幸，获得了图森未来的长期赞助，接下来的月赛（并不是每月都有？），我们会为优胜的参赛选手提供丰厚的奖品
- 很欣慰，月赛命题组开始有新鲜血液的加入，离学弟们接手月赛也不远了
- 很意外，学弟们的题目似乎太简单了，下次一定加大力度
关于奖品
为了庆祝 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$ 的贪心策略：
- 从左往右遍历，使每个 $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 \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$ 。
这样构造的思路，我们可以从格雷码中学到一些经验，用类似格雷码的方式构造就可以得到一个合法的解了。
比赛阶段所有代码，均已公开。