题解：AT_arc155_c [ARC155C] Even Sum Triplet

· · 题解

前言。

一道还不错的分类讨论题，本身涉及的知识点不多，就是细节比较多，细心点调是没有什么大问题的。

题意简述：给定两个长为 n 的序列 a 和 b。选定一个 i 使其满足 1\leq i\leq n-2 的条件。如果 a_i+a_{i+1}+a_{i+2} 的值为偶数，那么可以任意交换这三个数。请问能否通过这种操作使得序列 a 变成序列 b。

分析。

根据我们小学的知识，我们不难发现，如果保证三个数的和为偶数，那么仅存在两个情况：要么均是偶数，要么一个偶数，两个奇数。

我们先从一个奇数，两个偶数的情况入手。考虑构造。分成两个情况：在 a_i 前的数的奇偶性来分类讨论。设 a_i 为偶数且 a_{i+1} 和 a_{i+2} 均是奇数。如果 a_{i-1} 为偶数，那么必定能够使 a_{i-1} 移动到 a_{i+2} 后面去，且前面的序列不变，同时构造除了一个新的区间及 a_i+a_{i+1}+a_{i+2} 放在前面。举个例子：

1 2 5 7 //因为1，2，5的和为偶数，所以符合条件，交换1和5的位置。
5 2 1 7 //因为2，1，7的和为偶数，所以符合条件，交换位置。
5 7 2 1 //因为5，7，2的和为偶数，所以符合条件，交换位置。
2 5 7 1 //注意此时存着一个新的区间即2 5 7。

事实上，我们不难将其拓展到一般情况下，因为在其中的交换对于任意的这种情况都是可以构造出来的。同理，如果我们将 a_{i-1} 看做是偶数，那么通过交换 a_i 和 a_{i+1} 以及 a_{i+2} 的位置即可使 a_{i-1} 和 a_{i+1} 与 a_{i+2} 构成一个新的区间。举个例子：

2 4 5 7 //4+5+7为偶数，所以交换。
2 5 7 4 //此时2+7+5为偶数，构成一个新的。

仍然可以拓展到一般情况。所以我们可以得出结论：相邻的三个数中有一个偶数，两个奇数时，这两个奇数可以一起向左边或者右边移动（右边和上面的左边同理）一位，构造出一个新的合法区间。那么我们在任意交换的过程中，考虑每一个数的相对位置的变化情况。我们不妨设有两个奇数 f 和 s 存在。同时有一个合法区间 x+y+z 存在（这个区间仍然是第一个数为偶数，后两个数为偶数）。那么我们显然可以让 s 和 x+y 组合成为一个新的区间，然后 i 也可以同 x+y 组合，然后通过移动，我们就可以再使得 x+y+z 的区间再次存在，所以此时我们可以总结出一个规律：如果三个数可以组成一个合法区间，那么奇数的相对顺序可以随意改变，并且偶数的相对顺序不变。

注意到，在一个偶数，两个奇数的情况下，偶数的顺序是不会受到影响的，而可以改变相对顺序的只能是三个偶数的情况，此时因为均是偶数，所以可以任意交换，使得其相对顺序改变。此时算法就很显然了，先去判断一下是否存在合法区间然后分成是否存在三个偶数的合法区间，如果 a 和 b 均有，那么肯定可以，如果只有一个存在那么不行。如果两个都没有，判断一些奇数和偶数的相对位置能不能对应即可。相应的，如果序列中只有 1 个或者 2 个偶数，此时偶数的相对顺序是固定的，则直接暴力判断偶数的相对顺序能否对应即可。剩下的都是奇数的情况，都是奇数肯定交换不了，所以判断一下是否严格上下对应，直接输出即可。

代码如下，仅供参考：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,a[200005],b[200005];
int a2[200005],b2[200005],flag;
int tot1,tot2,sum;
template <typename T> void read(T &x){
    x = 0;
    bool f = 0;
    char c = getchar();
    while (c < '0' || c > '9') f |= c == '-', c = getchar();
    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    if (f) x = -x;
}
template <typename T> void write(T x){
    if (x < 0) putchar('-'), x = -x;
    if (x < 10) putchar(x + '0');
    else write(x / 10), putchar(x % 10 + '0');
}
bool cheak1(){
    sum=0;
    for(int i=1;i<=n-2;i++){
        if(((a[i]&1)+(a[i+1]&1)+(a[i+2]&1))==2){
            tot1=tot2=0;
            //判断一些偶数的移动情况。 
            for(int i=1;i<=n;i++){
                if(!(a[i]&1)){
                    a2[++tot1]=a[i];
                }
                if(!(b[i]&1)){
                    b2[++tot2]=b[i];
                }
            }
            if(tot1==2&&a2[1]!=b2[1]){//只有两个偶数
                return 0;
            } 
            return 1;
        }
    }
    for(int i=1;i<=n;i++){
        a2[i]=a[i];
        b2[i]=b[i];
        //记得还原一些。 
    }
    for(int i=1;i<=n;i++){
        if((a2[i]&1)&&(a2[i]!=b2[i])){
            return 0;
        }//奇数不对于，相对位置不可改变。 
        if(a2[i]&1){
            sort(a2+sum,a2+i);
            sort(b2+sum,b2+i);
            for(int j=sum;j<=i-1;j++){
                if(a2[j]!=b2[j]){
                    return 0;
                }
            }
            if(((i-1)-sum)==2&&a[i-1]!=b[i-1]){
                return 0;
            }
            sum=i;
        }
    }
    sort(a2+sum,a2+n+1);
    sort(b2+sum,b2+n+1);
    if(n-sum==2&&a2[n]!=b2[n]){ 
        return 0;
    }
    return 1;
}
int main(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        a2[i]=a[i];
    }
    for(int i=1;i<=n;i++){
        read(b[i]);
        b2[i]=b[i];
    }
    //记录序列。 
    sort(a2+1,a2+n+1);
    sort(b2+1,b2+n+1);
    //排序用来判断是否存在的数相同。 
    for(int i=1;i<=n;i++){
        if(a2[i]!=b2[i]){
            printf("No");
            return 0;
        }//有的数个数不同，不能构造。 
    }
    for(int i=1;i<=n;i++){
        if(a[i]&1){
            flag=1;
            break;
        }//奇数。 
    }
    if(!flag){
        cout<<"Yes\n";
        return 0;
    }//均是一种数合法的情况，肯定可以。 
    if(!cheak1()){
        cout<<"No\n";
        return 0;
    }
    for(int i=1;i<=n;i++){
        swap(a[i],b[i]);
    }
    if(!cheak1()){
        cout<<"No\n";
        return 0;
    }
    cout<<"Yes\n";
    return 0;
}

后记。

大家如有疑问，可以在评论区提出，我会尽力解答的。