ABC296F分类讨论简单动脑筋构造方案

#include <bits/stdc++.h>
#define N 200050
using namespace std;
int n, m, i, j, k, a[N], b[N], c[N], d[N], p[N];
int main(){
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        scanf("%d", &a[i]);
        c[a[i]]++;//统计数量
    }
    for(i=1; i<=n; i++){
        scanf("%d", &b[i]);
        d[b[i]]++, p[b[i]] = i;//记录每个数的位置
    }
    for(i=1; i<=n; i++){
        if(c[i] != d[i]) break;//数量不一致无解
        if(c[i] > 1) k = 1;//一种数字出现至少2次必有解
    }
    if(i <= n) printf("No\n");
    else if(k) printf("Yes\n");
    else{//数字不重复，模拟即可
        for(i=1; i<=n-2; i++){
            if(a[i] == b[i]) continue;
            k = p[a[i]];//a[i] = b[k]
            for(j=i+1; j<=n; j++){
                if(j != k) break;
            }//先一起换到位置j，再交换i和j（不影响判断）
            swap(a[i], a[j]);//没必要
            swap(b[k], b[j]);//相同的换到j，b序列还要维护位置
            p[b[k]] = k, p[b[j]] = j;
            swap(a[i], a[j]);//为了好看，而不是无聊
            swap(b[i], b[j]);//保证前i个都相同
            p[b[i]] = i, p[b[j]] = j;
        }
        if(a[i] == b[i]) printf("Yes\n");
        else printf("No\n");//剩下两个，无解即无解
    }
    return 0;
}