题解 CF1365F 【Swaps Again】

· · 题解

这么水的round我怎么没打啊。

看到这种交换的、改数的、输出yes和no的，猜个结论绝对不亏。

看这个样例：

例如对于 a=\{1,2,3,4,5,6\}，选择k=2，那么交换后会得到 \{5,6,3,4,1,2\}

注意到{5,2}和{1,6}的位置关于中间那个点对称，于是我们有了一个大胆的想法

  1. 前后数字是一样的（废话

于是我们就愉快地写出了code：

#include <map>
#include <iostream>

using namespace std;

const int MAXN = 5e3 + 5;

map<pair<int, int>, int> mp;
int a[MAXN], b[MAXN];

void Solve() {
    mp.clear();
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    for(int i = 1; i <= (n >> 1); i++) {
        mp[make_pair(a[i], a[n - i + 1])]++;
        mp[make_pair(a[n - i + 1], a[i])]++;
    }
    if((n & 1) && a[(n + 1) >> 1] != b[(n + 1) >> 1]) {
        cout << "No" << endl;
        return;
    }
    for(int i = 1; i <= (n >> 1); i++) {
        if(!mp[make_pair(b[i], b[n - i + 1])]) {
            cout << "No" << endl;
            return;
        }
        mp[make_pair(b[i], b[n - i + 1])]--;
        mp[make_pair(b[n - i + 1], b[i])]--;
    }
    cout << "Yes" << endl;
}

int main() {
    int t, n;
    cin >> t;
    while(t--) {
        Solve();
    }
}

然后你就AC了。

可是为什么呢？

考虑到我们换掉了一个i\le k，那么原来a_i就变成了a_{i+(n-k)}，a_{n-i+1}就变成了a_{n-i+1-(n-k)=k-i+1}又因为有i+(n-k)+k-i+1=n+1，故上面两个是关于中心点对称的，这证实了我们上面的猜想。