NOI2009 题解
本文将介绍 NOI2009 中各题的标准解法以及得分很高的替代算法。
Problem 1 变换序列
标准算法：二分图匹配+验证
难度：3
期望得分：100
分析：这道题目很容易对应一个二分图匹配模型：将数的位置看作点集 V1，将每个位置上
数的取值看作点集 V2，如果一个位置上可以放置某一个数，就在相应的两点之间连上一条
边。题目要求我们求出这个二分图的字典序最小的完美匹配，或者声明二分图不存在完美匹
配。
不难看出，每一个位置上最多只有两种取值，因此这个二分图的边数与点数同阶。使用匈
牙利算法可以在 O(n
2
)的时间内求出二分图的一个完美匹配或者发现二分图不存在完美匹配。
接下来我们需要求出二分图中字典序最小的完美匹配。我们逐一枚举取值，对于某一个取
值 iDi 来说，如果当前匹配具有这条边，则显然这个取值时可行的；否则，强制在二分图
中联入这条边，这个动作必将导致另一个节点失配，我们从哪个失配的节点开始，试图找到
一条增广路径，并且该增广路径不应该通过已经确定下来的匹配边。如果能够找到这样的增
广路径，则说明 iDi 可行，否则说明 iDi 不可行。
每一次找增广路径的时间是 O(n)，所以算法的总时间复杂度为 O(n
2
)，为本题的标程算法。
另外，从图的特殊性入手，还有一个 O(n)的构造算法，这里不再涉及。
替代算法：2-SAT
难度：3
期望得分：90
分析：这道题目的另一个模型是 2-SAT，不过经过我分析你会发现这实在是一个吃力不讨好
的模型。
由于每一个位置上的数只有两种取值，非此即彼，这是很强烈的 2-SAT 气息。如果两个
不同位置上的某两个取值相同，显然这两个取值不能同时存在，这就是 2-SAT 中的约束条
件。题目要求我们求出这个 2-SAT 问题的字典序最小解，或者指出该问题无解。
这个模型有这样几个麻烦之处：
1、 有可能某一位置上两种取值相同。此时必须先加以特判。
2、 这个 2-SAT 问题的边数有可能达到 O(n
2
)，这是制约该模型的最关键的因素。不过如
果我们认为有解情形下边数不会太多，那还是可以接受的。
3、 要求我们求出字典需最小的 2-SAT 解。这非常麻烦。考试时我反复思考 2-SAT 标准
算法发现无论如何修改也无法满足这一要求。最后我只能采用 2-SAT 朴素算法。
对于 2-SAT 朴素算法来说，其思想是对于每一个变量的某一个取值，判断该取值是否会
产生矛盾。产生矛盾又两种情况：与已经确定的变量的取值产生矛盾，或者自相矛盾。
通过一次 DFS 可以完成矛盾判断工作，因此这个算法的时间复杂度为 O(nm)，其中 m 是
2-SAT 的约束传播图中的边数。这个算法可以得到 90 分。
Problem 2 诗人小 G
