题解：P17220 [ICPC 2017 Nanning R] Rearrangement

· · 题解

因为最后看的是是否被 3 整除，而且还要重新排列，所以位置和原数字不重要，只需要记录对 3 取模后余数分别为 0,1,2 的个数。

余数为 1 的和余数为 2 的不能放一起，余数为 0 的和余数为 0 的也不能放一起。

如果余数为 0 的个数小于等于 n 那么可以交替间隔摆放余数为 0 和非 0 的数避免两个余数为 0 的数相邻反之无解。

如果余数为 0 的数量小于 2 那么无解，否则可以使用余数为 0 的数把数组分成两半一半全放余数为 1 的一半全放余数为 2 的（如果余数为 0 的数量正好为 2 那么它们必须放置在相邻列的对角线上，分成的两半数量都只能是奇数，需要特判）。


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