题解：P17220 [ICPC 2017 Nanning R] Rearrangement

· · 题解

P17220 [ICPC 2017 Nanning R] Rearrangement

题目大意

对于一个 2 \times n 的矩阵，重排顺序使得任意相邻两数之和不为 3 的倍数。

算法分析

把每个数用 3 模一遍，只有三种情况分别为 0，1，2，能再次凑成 3 的倍数只有两种情况，分别是 0 与 0 匹配和 1 与 2 匹配。于是进行分类讨论，分为以下几种情况。

  1. 记 0 的个数为 cnt_0，若cnt_0>n，无论如何摆放都无法满足任意两个 0 不相邻，直接输出 NO。
  2. 记 1，2 的个数分别为 cnt_1 和 cnt_2，当 cnt_1 与 cnt_2 均大于 0 时，为了不让它们接触，需要用 0 隔开。为了把他们隔开，必须使用至少两个 0 交错分布。若 cnt_0<2 直接输出 NO。
  3. 当 cnt_1 和 cnt_2 奇偶性不同时，cnt_0 必为奇数，在大于 2 的基础上可拿一个 0 填补偶数个的那一项，剩下的 0 按蛇形填充即可。
  4. 若奇偶性相同并且都为奇数，肯定能够拼好。若都为偶数，需要再次进行分类讨论。cnt_0 肯定是偶数，如果 cnt_0 \ge 4，就可以两边分别填充一个 0，剩下的蛇形分布。否则两边的 1 和 2 必定重合，无法满足条件。

    代码

    #include<iostream>
using namespace std;
int cnt[5];
int main(){
int t;cin>>t;
while(t--){
    cnt[0]=0,cnt[1]=0,cnt[2]=0;
    int n,x;cin>>n;
    for(int i=0;i<2;i++)
        for(int j=1;j<=n;j++){
            cin>>x;cnt[x%3]++;//模3
        }
    if(cnt[0]>n) cout<<"NO\n";//0会重合
    else if(cnt[1]==0||cnt[2]==0) cout<<"YES\n";//只有1或2，不可能重合
    else if(cnt[0]<2) cout<<"NO\n";//没有足够0作隔板
    else{
        if((cnt[1]&1)==1&&(cnt[2]&1)==1)//同为奇 cout<<"YES\n";
        else if((cnt[1]&1)==0&&(cnt[2]&1)==0){//同为偶
            if(cnt[0]>=4) cout<<"YES\n";
            else cout<<"NO\n";
        }
        else cout<<"YES\n";//奇偶性不同
    }
}
return 0;
}