题解：P17220 [ICPC 2017 Nanning R] Rearrangement

· · 题解

这道题重要的不仅是判断的方法，判断的顺序也很重要。

1. 题意简述

给你一个 2\times n 的二维数组，每一位都有一个数字，问你是否能通过重排这个数组使得任意两个相邻的数的和相加不能被 3 整除。

2. 思路分析

这种相加整除的问题肯定是从余数方面去考虑。因此，我们先把每种余数有多少个统计出来。

统计完余数，我们就要想如何判断了。可以发现 3 只有三个余数，分别是 0、1、2，而这三个数中 0 是最特殊的，因为只有 0 不能和它自己相邻。因此，我们要想放最多的 0，就必须按照第一行第一列放一个，第二行第二列放一个，第一行第三列放一个……这样来放，根据最不利原则，我们就可以知道 0 最多放 n 个。

接下来我们思考，如果 1 的数量和 2 的数量有一个等于 0，在 0 的数量满足条件的情况下是一定可以构造出正确方案的，我们只需要按照上面的方案放 0，剩下的空位用数量不为零的那一个数填满就可以了。

容易发现 1 和 2 是不能相邻的，所以我们要用 0 当分隔符。如果 0 的数量小于 2 的话是不可能分开 1 和 2 的，所以 0 的数量必须不小于二。

接下来要分成两种情况讨论。

情况一：0 的数量等于 2。这种情况下，我们要保证 0 不能相邻又要能分割，只能按照下面这样放：

0
0

然后在两边分别放 1 和 2。容易发现要想构成一个矩阵，1 和 2 的数量必须都是奇数，判断即可。

情况二：0 的数量大于 2。这个时候无论如何都是有解的。如果 0 的数量为奇数，那么剩余的空位数量也一定是奇数，不难得到 1 的数量和 2 的数量中一定有一个是奇数，我们只需要把数量是奇数的放在上面，就像这样：

0 1 0
2 0 2

剩下的分别放在两侧就能满足条件了。

如果 0 的数量为偶数呢？容易得到 1 的数量和 2 的数量差也一定是偶数，我们按照这个差来填补中间，中间不够拉开这么多差距就把两边的数字删去一列，这样每次可以把差距拉大 2，最后就能达到两数数量之差。

其实这道题判断方法还是不难想的，但是由于判断顺序不能乱所以还是比较容易出错的。

3. AC 代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n;
int a[5][10005];
int ze,on,tw;
signed main(){
    cin>>t;
    while(t--){
        cin>>n;
        ze=0;
        on=0;
        tw=0;
        for(int i=1;i<=2;i++){
            for(int j=1;j<=n;j++){
                cin>>a[i][j];
                a[i][j]%=3;
                if(a[i][j]==0) ze++;
                if(a[i][j]==1) on++;
                if(a[i][j]==2) tw++;
            }
        }
        if(ze>n){
            cout<<"NO\n";
            continue;
        }
        if(on==0||tw==0){
            cout<<"YES\n";
            continue;
        }
        if(ze<2){
            cout<<"NO\n";
            continue;
        }
        if(ze==2){
            if(on%2==1&&tw%2==1){
                cout<<"YES\n";
            }else{
                cout<<"NO\n";
            }
        }else{
            cout<<"YES\n";
        }
    }
    return 0;
}