Wa on 03_two_evens,蒟蒻求调
查看原帖
Wa on 03_two_evens,蒟蒻求调
500202
Aranak楼主2023/6/8 20:55
/*
一道大分类讨论。

如果有一个可以交换的段包含奇数,
那么你可以把所有奇数移到最左边并任意调整相对顺序,
然后回到任意一种有一个可以交换的段包含奇数的状态。
这种情况,如果偶数的数量为 2,
这两个偶数是不能交换相对位置的,
有至少 3 个偶数就能交换偶数间相对位置。
所以只需要判断a和b中的数是否相同以及两个偶数的相对位置即可。

如果没有一个可以交换的段包含奇数,
则所有奇数都不能移动,
同时奇数把整个序列分成几段,
每一段中如果只有 2 个偶数,
那不能移动;
如果有至少 3 个偶数,
那么块内的偶数是可以移动的。
所以要判断 a 是奇数的位置和 b 是否相同,
然后在每一段内判断 a 和 b 中的数是否相同以及两个偶数的段是否位置对应相同。

——lyx大佬
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;

const int N = 2*1e5+10;

int n,a[N],b[N],cnt,s,fr,ou,aou[10],bou[10],cfpa[N],cfpb[N];

int posou[N];

typedef pair<int, int> PII;
#define x first
#define y second

bool swapji;

int main()
{
    scanf("%d",&n);cnt=1;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);cfpa[a[i]]++;
        if((a[i]&1)==0) ou++;
        s^=a[i];
        if(i>=3){
            if((s&1)==0){
                if((a[i-1]&1)==1 || (a[i-2]&1)==1 || (a[i]&1)==1) swapji=1;
            }
            s^=a[i-2];
        }
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
        cfpb[b[i]]++;
    }
    for(int i=1;i<=N-10;i++){
        if(cfpa[i]!=cfpb[i]) {
            printf("No");
            return 0;
        }
    }
    if(swapji){
        if(ou>2 || ou==1) {
            printf("Yes");
            return 0;
        }
        int ca=0,cb=0;
        for(int i=1;i<=n;i++){
            if((a[i]&1)==0) aou[++ca]=a[i];
            if((b[i]&1)==0) bou[++cb]=b[i];
        }
        if(aou[1]==bou[1] && aou[2]==bou[2]) printf("Yes");
        else printf("No");
        return 0;
    }
    for(int i=1;i<=n;i++){
        if((a[i]&1)==1){
            if(b[i]!=a[i]) {
                printf("No");
                return 0;
            }
            continue;///////
        }
        fr=i;
        while(i<=n && (a[i]&1)==0 && ((a[i+1]&1)==0)) i++;/////////
        sort(a+fr,a+i+1);sort(b+fr,b+i+1);
        for(int j=fr;j<=i;j++){
            if(a[j]!=b[j]){
                printf("No");
                return 0;
            }
        }
    }
    printf("Yes");
    return 0;
}
2023/6/8 20:55
加载中...