题解：CF2031B Penchick and Satay Sticks

传送门

题意

考虑反向操作，变成给定一个 1 到 n 的严格递增排列，可以进行一种操作，即将两个绝对值差为一的两个数交换位置，问所给排列是否能通过一定次数的操作实现。

思路

和官解做法不一样。

因为这种独特的交换条件，可以发现在位置 x 的数 h_x 只可能到达 h_{x-1} 和 h_{x+1}，或者位置不变。所以可以扫一遍，直接判断这个数和其位置的绝对值差，不符合一定不合法。

然后我们再考虑符合后就一定合法了吗？我们可以从排列最前端开始考虑。对于 h_1 只有两种可能操作，不变和与 h_2 交换。而如果交换了，下一个数的操作其实就已经确定了（因为再重新交换回原来的状态没有意义）。所以只需要满足上面的条件，其实就是合法的。可以自己画画，理解一下。

CF思维题猜结论题，纪念我因数组开小而获得的一发罚时。

code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
/*快读省了*/
ll t, n, h[200200];

int main() {
    read(t);
    while (t--) {
        read(n);
        for (int i = 1; i <= n; i++) {
            read(h[i]);
        }
        ll key = 1;
        for (int i = 1; i <= n; i ++) 
            if (abs(h[i] - i) >= 2) {
                key = 0;
                break;
            }

        if (key == 0) puts("No");
        else puts("Yes");
    }
    return 0;
}