凹语言凹语言中文版NOIP 2024真题详解第1题
- 时间：2025-11-12
- 撰稿：凹语言开发组
- 转载请注明原文链接：https://wa-lang.org/smalltalk/st0094.html
NOIP 是全国青少年信息学奥林匹克联赛的英文缩写，是面向中小学生的信息学竞赛。由中国计算机学会主办，是国内信息学领域权威的普及性竞赛。主要考察编程能力和算法思维，核心语言包括 C++（主流）、C、Pascal（部分组别）。参赛对象为小学、初中、高中学生，分提高组、普及组等组别。成绩优秀者可获得高校自主招生、综合评价等相关优惠，是信息学特长升学的重要参考。
作为中国乃至面向世界的赛事，NOIP 比赛使用的全部是国外的编程语言。本文尝试通过凹语言来讲解答，通过不同的视角体会算法问题和工程问题的差异。
1. NOIP 2024 第1题
如果暂时不考虑性能（即 $O(n^2)$ 甚至更慢的复杂度也没关系），我们能找到一个更直观、更容易理解的算法，这个算法被称为最大流/最小费用最大流模型，或者用更简单的语言描述：最大二分图匹配的变形。
但是，因为这个题目的特殊性质（只有 '0' 和 '1' 两种字符，且操作是相邻交换），我们可以避开复杂的图论模型，直接使用纯粹的贪心和计数，这是最容易理解且最高效的方法。
2. 💡 最易理解的算法：纯粹的贪心与计数
这个算法的思路是：将问题分解为独立的两部分，并分别用贪心法解决。
2.1. 核心洞察：字符的分类与自由度
所有的字符和位置都可以根据它们能否被交换，被分成四种类型：
| $s_1$ 的状态 ($t_{1,i}$) | $s_2$ 的状态 ($t_{2,i}$) | 位置 $i$ 的自由度 | 决策：匹配 $s_{1,i}$ 和 $s_{2,i}$ |
|---|---|---|---|
| 0 (固定) | 0 (固定) | 0 | 固定匹配/不匹配。 $s_{1,i}$ 必须对 $s_{2,i}$。 |
| 0 (固定) | 1 (可换) | 1 | $s_{1,i}$ 确定。用 $s_2$ 的可换字符池去匹配它。 |
| 1 (可换) | 0 (固定) | 1 | $s_{2,i}$ 确定。用 $s_1$ 的可换字符池去匹配它。 |
| 1 (可换) | 1 (可换) | 2 | 完全自由。 用 $s_1, s_2$ 剩余的字符池进行自由组合。 |
2.2. 算法核心：两个独立的池子
因为相邻交换的特性（只要没有 $t_{i}=0$ 的障碍物，可换字符可以在其区间内任意排列），我们可以把所有 $t_{1,i}=1$ 的字符想象成一个大池子 $C_1$，所有 $t_{2,i}=1$ 的字符想象成一个大池子 $C_2$。
目标： 最大化从 $C_1$ 和 $C_2$ 中取出相同字符进行匹配的次数。
2.3. 三步贪心策略
我们将匹配过程分为三步，每一步都采用贪心策略，因为一旦完成了匹配，这个字符就不能再被使用了（即：先用先得）。
步骤 1：处理双固定的位置（类型 0）
- 操作： 遍历所有 $i$，如果 $t_{1,i}=0$ 且 $t_{2,i}=0$。
- 贪心： 如果 $s_{1,i} = s_{2,i}$，这是一个确定无疑的匹配。
- 效果： 答案 $+1$。
步骤 2：处理一固一换的位置（类型 1）
- 操作： 遍历所有 $i$ 属于类型 1 的位置（$t_{1,i} \neq t_{2,i}$）。
- 贪心： 在这类位置上，我们必须用 $s_1$ 或 $s_2$ 中固定的字符去锁定匹配目标，然后消耗掉另一个字符串的字符池中的一个对应字符。
- 例： $t_{1,i}=0, t_{2,i}=1$ 且 $s_{1,i} = '0'$。如果 $C_2$ 池子中还有 '0'，我们必须用 $C_2$ 中的一个 '0' 来匹配这个固定的 $s_{1,i}$，从而锁定这个匹配。
- 效果：
- 如果匹配成功，答案 $+1$。
- 相应地，从 $C_1$ 或 $C_2$ 中减少对应字符的计数。
为什么先处理这个？ 因为这些固定字符是必须要匹配的（如果可能），它们消耗了 $C_1$ 或 $C_2$ 的资源，限制了接下来的自由组合。
步骤 3：处理双可换的位置（类型 2）
- 操作： 此时 $C_1$ 和 $C_2$ 池子中还剩下一些字符，以及一些 $t_{1,i}=1, t_{2,i}=1$ 的空闲位置。
- 贪心： 由于这些空闲位置是完全自由的，我们可以用 $C_1$ 中剩余的字符和 $C_2$ 中剩余的字符进行最大化匹配。
- 匹配 '0'： 我们可以组成 $\min(\text{剩余 '0' in } C_1, \text{剩余 '0' in } C_2)$ 对。
- 匹配 '1'： 我们可以组成 $\min(\text{剩余 '1' in } C_1, \text{剩余 '1' in } C_2)$ 对。
- 效果： 答案加上这些匹配的总和。
3. 开始解决正题
这个算法把一个复杂的排列问题，简化成了资源分配问题：
- 确定不需要资源的匹配。
- 贪心分配资源（$C_1$ 和 $C_2$）给那些半固定的需求。
- 最大化利用剩余的资源进行自由组合。
由于我们总是在可能的情况下优先匹配（贪心），且我们没有丢失任何字符（$C_1$ 和 $C_2$ 中包含了所有可换字符），这个策略是正确的。
凹语言中文编程的代码片段如下：
完整的代码：https://gitcode.com/wa-lang/wa/blob/master/waroot/examples/noip2024/edit.wz
4. 结语：在实战中打磨中文编程
之前我们已经通过凹语言中文编程展示了CSP-J题目的解法，今天我们更进一步给出了NOIP题目的解法。正如我国回归联合国的过程充满了曲折，中文编程想走向世界的道路也注定不会平坦。最终的结果是汉语成了联合国的官方工作语言之一，中文编程也必将在世界上占有一席之地。