题解：P17220 [ICPC 2017 Nanning R] Rearrangement

· · 题解

我们只关心每个数对 3 取模的值。容易发现多个 0 是不能挨在一起的，多个 1 或者多个 2 就可以，但 1 和 2 之间必须用 0 隔开。

我们有两行数，显然隔开 1 和 2 至少需要 2 个 0，就像这样：

1 1 0 2 2
1 1 1 0 2

那么计 x 出现的次数为 cnt_x，若 cnt_1>0 且 cnt_2>0 且 cnt_0<2 的话一定无解。

我们还能发现上面的例子 cnt_1 是奇数，让两个 0 得以交错摆放，那么如果 cnt_1 是偶数呢？显然 2 个 0 是不够的，我们需要三个以上的 0 才能把 1 和 2 隔开，同时保证 0 交错摆放：

1 1 0 2 2 2
1 0 1 0 2 2
1 1 0 2 0 2
1 0 1 0 2 2

那么若 cnt_1\bmod 2=0 且 cnt_0=2 的话一定无解。

最后，如果 cnt_0>n，显然会有至少一列放了两个 0，一定无解。

代码如下，可供参考：

#include<bits/stdc++.h>
using namespace std;
int cnt[3];
int main(){
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        cnt[0]=cnt[1]=cnt[2]=0;
        for(int i=1;i<=2*n;i++){
            int x;cin>>x;
            cnt[x%3]++;
        }
        if(cnt[1]&&cnt[2]&&cnt[0]<2){
            cout<<"NO\n";
            continue;
        }
        if(cnt[1]%2==0&&cnt[0]==2){
            cout<<"NO\n";
            continue;
        }
        if(cnt[0]>n){
            cout<<"NO\n";
            continue;
        }
        cout<<"YES\n";
    }
    return 0;
}