001F
[AGC001F] Wide Swap 题解
特别有意思的思维题。 ### 思路 参考题解第一位的神仙思路。 将排列 $a_i$ 变为 $b_{a_i}$。 限制便变为了只能交换相邻的两个差大于 $k$ 的点。 那么这个限制就已经与普通排序很相似。 考虑使用归并排序。 一个点可以跑到其他点的前面要求这一连续段都是比它加 $k$ 都不大。 在归并 ......
「解题报告」AGC001F Wide Swap
首先题目给的限制条件很奇怪,下标差 $K$ 而值域差 $1$。我们变成逆排列,然后就转换成了下标差 $1$,值域差 $K$ 了,每次操作就相当于交换相邻的两个差 $\ge K$ 的数。 假设新的逆排列为 $Q_i$。我们发现,假如存在两个数差 $<K$,那么它们的相对位置关系一定不变。那么我们现在有 ......