题解 P3750 【[六省联考2017]分手是祝愿】

· · 题解

在Flandre_495的题解通过后这题应该就已经有五篇题解了。所以我也不太想说这题的具体思路，其他题解说的已经很明白了。

Flandre_495说的rainy就是我

这里我们来考虑一些比较特殊的事情：

我们如何证明一个局面的最优解是从后往前扫一遍能关就关？

实际上我们只能知道从后往前扫一遍必然是一个合法的解法，也就是说它是一个可行解，但我们想要证明它是唯一解。

我们可以认为一个合法的解法是一个可重集合S，其包含的所有数即为此解法需要按下的所有按钮的位置，也就是所有的操作。

例如对于\{1,0,1\}，有S=\{3\}。

定义为可重集合是因为S=\{1,1,3\}同样也是上述局面的一个解。

我们发现实际上一个操作重复两次就相当于这两次操作没有进行，因为它会使同样的几个位置上的数\text{xor~1~xor~1},相当于不变。所以我们不认为这样的两个解法是不同的。

考虑一个解法的实质，其代表了一个n维的向量，其中每一维都在01中取值，而这个解法就是将原局面的每一个数异或上这个向量中的对应维的那个数。

很明显我们可以对任何一个解法构造这样一个向量，并且每一个解法能解决的局面是唯一的，于是我们知道解法的集合A和局面的集合B的有映射f:A\to B。

接下来我们想证明的其实是这个映射是单射。

我们已经知道任何一个解法只能对应一个局面，并且解法的数量(2^n)和局面的数量(2^n)是相同的，于是如果我们能证明其为满射，就能知道它是一个单射。

我们先假设其为满射，证明其为单射。使用反证法，假设其不为单射。

那么就一定存在两个不同的解法集合对应了同一个局面，此时必然会出现局面没有被对应到，于是此时映射不是一个满射，与条件矛盾，所以其为单射。

之后我们发现对于任意一个局面，按照如上所述的构造方法一定能构造出一个解法，于是可以知道其为满射。于是其为单射。（当然它也是双射）

换句话而言，对于任何一个局面，其解法是唯一的，而我们做的任何操作都相当于向这个这个局面的解法追加了一个操作。

而解决一个局面的唯一方法就是进行数次追加后将这个集合变为空集，这基于上面对映射为单射的证明。

如果我们进行的操作是解法中的某个操作，那么解法中的这个操作会和我们进行的这个操作抵消，使得解法的集合的大小变为k-1，此时即代表我们从需要k次操作的状态转移到了需要k-1次操作的状态。

如果我们进行的操作不属于这个解法中的操作，那么这个解法在添加这个操作后就变成了一个有k+1个元素的集合，而实际上上面这两个情况都是只和局面所需操作数有关的，所以我们就可以将局面所需操作数作为状态进行dp而不必关心具体局面。