省选构造专题

The same permutation

首先打个表，发现在 \(1\le n\le 5\) 之内的是否有合法方案的情况为 √××√√ 大了打不出来了。

考虑一下 \(4,5\) 连续有解，注意到一个偶数有解，则这个偶数 \(+1\) 也必定有解。

考虑以下构造方法

即对于某一个交换，可以在它前后各添加一个右端点相同的交换，添加前后结果是等价的。

回到上面那个结论，对于新增的点，考虑新增的交换，总共只有偶数个，所以可以在 \((1,2),(3,4),(5,6)\dots (i,i+1)\) 前后进行这个操作。

考虑继续扩展上述结论。

对于一个合法的奇数 \(i\) 发现 \(i+1\) 是否有解似乎不是那么好判断，先跳过，\(i+2\) 也不好判断，也先跳过。

发现 \(i+3\) 是可以构造出合法解的，考虑如下构造。

现将 \(i+1,i+2,i+3\) 为右端点 \(1~i-1\) 为左端点通过上述方法处理掉（这是合法的因为 \(i-1\) 是偶数），现在就变为 \(i,i+1,i+2,i+3\) 这 \(4\) 个点 \(\dbinom{4}{2}\) 种交换未处理，这个问题等价于 \(n=4\) 时的构造方案，直接代入即可。

现在合法情况是形如 √××√√??√√??√√??√√... 猜测一下对于 ? 是不可能构造出来的，所以直接写代码

对于 ? 而言确实是无法构造的，考虑证明

有一个结论，每一次交换操作全局逆序对个数的奇偶性会发生变化，考虑证明。首先只用考虑交换的两个数以及它们之间的数的贡献的变化，对于交换的两个数显然 \(|\Delta|=1\)，对于中间的数分讨一下它和交换的两个数的大小关系发现 \(|\Delta|=0/2\)，证毕

所以只有交换总次数是偶数才会有解，而 \(n \bmod 4 =2/3\) 时 \(\dbinom{n}{2}=\dfrac{n(n-1)}{2}\) 是奇数，所以无解。

证毕。

所以考虑以上构造方法，用链表进行维护即可。

时间复杂度 \(O(n^2)\)。

[AGC006E] Rotate 3x3

先判断掉一些显然的错误。

可以转化题意变为

给定一个排列 \(a\)，\(01\) 序列 \(b\)。

可以无限次进行下述操作：

翻转相邻 \(3\) 个元素，并使它们对应的 \(b\) 序列异或上 \(1\)

问是否存在操作使得 \(a\) 序列升序时，\(b\) 序列全为 \(0\)

显然有每个数只能在下标奇或偶上移动，取决于最初的状态。

现在毫无头绪啊，发现第四个样例根本模不出来，写个暴力试试。

发现很多有解的操作序列中都有一段很有趣的操作。（描述一个翻转操作时设 \(x\) 为中间的那个数）

即形如 \(x,x+2,x,x+2,x,x+2\)，仔细研究一下，发现这种操作不会改变 \(a\) 序列，但会使 \(b_x,b_{x+2}\) 异或上 \(1\)。

这是一个有力的工具。

由于 刷题=IOI赛制，猜测一下能在不改变 \(a\) 的情况下改变 \(b\) 有意义的操作的只有这一个，所以写个 \(O(n^2)\) 的冒泡排序模拟排序序列 \(a\) ，得到最终的 \(a,b\)，然后套用上述操作的结论（即 \(\operatorname{xor}_{2\mid i}b_i=0\) 且 \(\operatorname{xor}_{2\nmid i}b_i=0\) 时有解），交上去发现只有 TLE 没有 WA!

考虑用树状数组优化上述做法，交上去发现 AC 了。

仔细思考一下，能得到下述严谨做法。

考虑一个翻转操作，会在不改变奇偶一方 \(b\) 序列异或和的情况下改变另一方的异或和。

这启发我们研究交换次数，而交换次数这个东西又是和逆序对挂钩的（考虑分奇偶后）。

所以可以分别求出奇偶的逆序对，然后套用上述结论 \(\operatorname{xor}_{2\mid i}b_i=0\) 且 \(\operatorname{xor}_{2\nmid i}b_i=0\) 时有解。

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