从 OI 退役下来就一直计划要写一批回报 OI 界的文章, 其他文章还在规划当中, 而这一篇是从九月份的 UyHiP 的解法而想到的. 接下来这段时间也不算太忙, 我就保质保量的完成这一批文章吧.

一百囚犯问题: 这里的一百囚犯可不是开关灯泡的那些囚犯, 而是戴手套的. 这一群囚犯被告知, 在第二天早上, 他们每个人头上会被写上一个不同的实数, 每个人在单间里会看到其他人头上写着数的照片, 但都不知道自己头上写了什么, 接下来每个人会有一只白手套和一只黑手套, 在每个人都决定好要怎么戴上手套之后, 他们会被从各单间里拉出来按照头上的数从小到大排成一排, 相邻的人要手拉着手, 如果每一对拉着的手都是同样颜色的, 那么他们就会被释放. 现在他们有一晚上的时间来商量如何应对.

答案当然就是利用逆序对, 如果我们给每个人都编上号, 最后按照头上的数排序后我们就会得到一个序列. 每个人可以看到的特征: 这个序列除去他自己, 这样得到的一个序列就是它能得到的所有可用信息了. 仔细观察每个人看到的序列的逆序对个数是有性质的: 原序列中相邻两个同奇偶的数看到的逆序对数是不同奇偶的, 反之相邻两个不同奇偶的数看到的逆序对个数就是同奇偶的. 这启发了我们用一个巧妙的构造来解决这些囚犯们的难题: 如果我们把两种戴手套方法叫做 0 和 1 的话, 一个编号是奇数的人, 若看到的逆序对数是奇数就是 0 状态, 否则就是 1 状态; 一个是编号是偶数的人, 若看到的逆序对数是奇数就是 1 状态, 否则就是 0 状态. 这样我们就可以保证相邻两个人的状态不同了.

你可能会想, 逆序对难道有这么重要的性质吗? 事实上, 逆序对是一个数列的很重要的特征. 有一个很简单的例子, 就是信息学竞赛当中的八数码问题, 如果我们把八数码中的那个空格忽略, 把剩下来的 8 个数按照顺序写成一个数列. 我们发现, 把空格平移对数列没有影响, 而若是把空格上移或者下移的话, 分情况讨论被移动的数和中间隔的两个数, 我们会发现逆序对的奇偶性是不变的. 因此, 我们对于八数码的初状态和目标状态, 若逆序对奇偶性不相同, 一定是无解的. 但反过来证明要是逆序对就相同就有一点点困难了, 虽然这也是对的, 所有八数码的可能状态只分为两个等价类: 逆序对奇数, 逆序对偶数.

从上面的例子还可以推广到很多, 比如说一个排列通过对换变成一个顺序列 (eg., 1, 2, 3, 4…) 的次数的奇偶性和逆序对相同, 也就是说, 一个排列应用一次对换逆序对的奇偶性会改变.

另外, 逆序对能够一定程度上反映序列的混乱状况, 所以逆序对在排序算法的复杂度分析上也有很重要的作用, 当然了, 在各种 OI 竞赛上面逆序对也同样有他的一番用武之地.