邻位交换总结

嘉然小姐的狗 · 2020-11-13 16:40:49 · 个人记录

给一个字符串 S，每次操作可以交换相邻两个字符，求将 S 转化至不含有子串 \texttt{VK} 的最少操作次数。|S| \leq 75。

如果你已经会了上面这一道题，那么你可以关掉这个页面了。这个页面就讲的这玩意，没什么。

顺便提一下，交换相邻两个元素，交换出所有排列的可达性可达性在树上也成立，具体题目可以看看 ARC107 C - Shuffle Permutation。这就是我要讲的了，会的可以关了。

题外话：所有排列的可达性

所有排列的可达性 对于任意一个 n 个元素的排列 \{P_n\}，都存在一种方案使得若干次交换后序列 \{A_n\} 变为 \{A_{P_1}, A_{P_2}, \ldots, A_{P_n}\}。

证明 只需证明我们可以交换任意两个元素，而保持其他元素不变即可。

不失一般性地，假设我们要交换 (i, j)，其中 i < j。那么我们只需要依次交换 (i, i + 1), (i + 1, i + 2), \ldots, (j - 2, j - 1), (j - 1, j), (j - 2, j - 1), (j - 3, j - 2) \ldots, (i + 1, i + 2), (i, i + 1) 即可。因此我们可以任意交换两个元素而保持其他元素不变，自然也就可以交换出所有排列。

树上所有排列的可达性 对于一棵带点权树，点权为排列，如果可以交换相邻两个元素，那么我们可以交换出所有排列。

证明 同理。

具体题目可以看看 ARC107 C - Shuffle Permutation。

当然这是题外话了。我们今天要讲的是：邻位交换问题的最少操作次数。

从最简单的一道题讲起

给一个 n 个元素的序列 \{A_n\}，每次操作可以交换相邻两个元素，求将 \{A_n\} 交换至不下降的最少操作次数。n \leq 10^6，1 \leq A_i \leq 10^9。

相信大部分人应该都知道，答案就是逆序对数。为什么呢？给个证明。

证明

最少操作次数的下界 最少操作次数不小于逆序对数。

证明 可以发现，每次交换两个相邻元素，逆序对数会增加 1，减少 1 或不变。注意到最终序列逆序对数为 0，而理论最优情况是每次交换都减少一对逆序对，操作次数为逆序对数。因此，最少操作次数不小于逆序对数。

最少操作次数的上界 最少操作次数不大于逆序对数。

证明 显然地，不存在 i 使得 A_i > A_{i + 1}，当且仅当 \{A_n\} 不下降（逆序对数为 0）。因此只要 \{A_n\} 逆序对数大于 0，一定可以找出一个 i 使得 A_i > A_{i + 1}，交换这一对后逆序对数减 1。这一构造方案的操作次数为逆序对数。因此，最少操作次数不大于逆序对数。

综上，最少操作次数等于逆序对数。

逆序对数可以通过各种方式 O(n \log n) 求解，此处略去。

扩展一下

当然只是排序太没意思了，能不能扩展一下呢？

邻位交换定理 若已知交换后原来第 i 个元素的位置，则最少邻位交换次数等于有多少对 i, j，满足原先 A_i 在 A_j 前面，交换后 A_i 在 A_j 后面。

证明 同理。

同值顺序不变定理 若 A_i = A_j，则在最优方案中，A_i, A_j 的相对顺序必定不会发生改变。

证明 因为权值一样，所以交不交换 (i, j) 都对序列没有影响，强行交换只会让逆序对数增加，答案更劣。

这两个定理非常非常重要，在类似的题目中经常出现。

NOIP2013 D1T2 火柴排队

link

给两个序列 \{A_n\}, \{B_n\}，同序列元素互不相同。可以交换同序列中相邻元素，请使得 \sum_{i = 1}^n (A_i - B_i)^2 最小，在此情况下的最少交换次数。

首先观察可以得到 (A_i - B_i)^2 = A_i^2 + B_i^2 - 2A_iB_i，而 \sum A_i^2 和 \sum B_i^2 是定值，因此我们需要让 \sum A_iB_i 最大。根据排序不等式，可以知道让第 k 小的 A_i 和第 k 小的 B_i 配对可以达到最大值。

注意到交换 A_i 相邻元素等价于交换 B_i 相邻元素，因此我们可以只考虑交换 A_i。因为我们已经知道了 A_i 要和哪个 B_i 配对，也就知道了其最终位置。这样就可以利用邻位交换定理解决了。

时间复杂度：O(n \log n)。

POI2012 Letters

link

给定两个字符串 A, B，可以交换 A 中相邻两个元素，求让 A 变为 B 的最少次数。|A| = |B| \leq 10^6。

和上面那道题是类似的，但是要注意：字符串中元素可能有重复的权值。

不过不难处理。根据同值顺序不变定理，如果有多个相同的权值，让位置小的和位置小的匹配即可，之后类似，不再赘述。

这一点要注意：同值相对顺序不变，这一点非常重要。之后如果出现了权值类似的情况，也可以根据这个来处理。

时间复杂度：O(|A| \log |A|)。

ARC097 E Sorted and Sorted

link

有 2n 个小球，小球有黑白两种颜色，每种颜色都有 n 个，权值分别从 1 到 n。可以交换相邻两个小球，请使得同色小球权值递增，并求出最少交换次数。

这一道题开始，我们就要引入用 DP 解决此类问题的经典做法了。

设 F_{i, j} 表示以权值为 1 \ldots i 的黑球和权值为 1 \ldots j 的白球构成相对排序序列时的最少逆序对数，答案为 F_{n, n}。

递推方面，可以考虑放入的是黑球还是白球。

• 如果序列末尾是权值为 i 的黑球，那么有 F_{i, j} \leftarrow F_{i - 1, j} + B_{i, j}，其中 B_{i, j} 表示在权值为 1 \ldots i 的黑球和权值为 1 \ldots j 的白球中，有多少个球初始在权值为 i 的黑球后面。
  • 解释：因为我们计算的是逆序对数，所以这里需要加上权值为 i 的黑球的贡献。注意到其他已经加入的球都在它前面，所以我们只需要知道有多少已经加入的球初始在权值为 i 的黑球后面，就可以计算它的贡献了。
• 白球同理。