Preface
- 你不觉得这很酷吗？作为一名 OIer 我觉得这太酷了，很符合我对构造题的想象，傻逼并带着人类智慧。
- 虽然是复读官方题解但是相比意识流我希望带给您更好的阅读体验。
- 您好，Sol1 先生，请问您在 NOI 之余方便解决一下我的疑问吗 /kel ：【云剪贴板】
- 我大概看了一遍，是不是您那个placeBack函数的逻辑是判断x和x-1，如果太小就每次加进来两个
- 我不知道这样会不会慢，我的写法是让对应元素和目标的距离一直减小，您要不要试着改一下这个，，，
- 对的，因为我看官方题解好像说是“到最后小步输送元素的时候，如果发现到某一个时刻右边恰好剩 x 个，那么直接给左边挂点东西然后推过去，可以省去 x-1 次操作”
- 请问这是您的代码吗，我从某位前团员那边搞到的？【云剪贴板】
- 是的吧
- 我其实也不是很理解这一部分的各种实现在随机数据下面为什么会有很大差距，，，
- 您要不要先对着改改看看，我得睡觉去了，明天还得考day2，，，，
从 NOI 2022 咕到现在 /cf/cf/cf
Solution
用 Powerpoint 做的。
\(\mathbf{proof.\ 1}\)
- 我们都知道把一个序列还原为有序序列的次数与逆序对个数的奇偶性相同。
- 考虑每一次交换，把它看做将逆序序列还原为有序序列的操作，那么逆序对个数为 \(x(x \pm 1)\)（前后区间各自有序，唯一的贡献在于前面的所有数与后面的所有数一一对应），故逆序对奇偶性不变。
- 上文中的黄 \(2\)，蓝 \(3\)，绿 \(1\) 的情况对应的是逆序对个数为奇数，故它会直接被判为无解。
- 同样地，这也证明了为何逆序对数为奇数时无解，以及为何这种做法是正确的。
\(\mathbf{prune.\ 1}\)
这部分还是复读的官方题解。
- 容易发现如果在第一张幻灯片中归位 \([1, n - 2x - 1]\) 的时候如果存在一个数距离它应到的位置是 \(\leq x - 1\) 的偶数那么要一直 \(+2\) 直到 \(2x - 2\) 的位置才能换回去。
- 但是你会发现 \(x\) 也是一个偶数，而很显然我们可以把一个数往左平移 \(x\) 的位置。于是到这里就可以直接剪枝了，大概在 \(\mathcal O(\frac{n^2}{x})\) 的复杂度上常数可以小一半。
\(\mathbf{prune.\ 2}\)
考虑在 Step1 复位的时候让距离一直不减而不是反复增加，常数会比较小。
不这样剪枝只能过 \(n \leq 5\times 10^3\)，clcn 丧尽天良。
需要代码可以找我要。