ACM-ICPC 2017 Asia Nanning

Rearrangement

题意：

给两行数字，每行有n个数字，问是否可以通过重新排列这些数字，使得相邻的数字之和不能被3整除？相邻包括同一行两个数相邻和两行数字上下相邻。

分析：

可以把数字分为3种：第一种：x除以3的余数为0，第二种：x除以3的余数为1，第三种：x除以3的余数为2。

1.余数为1和2的两种数不能相邻

2.余数为0的两种数不能相邻

0的个数为2时，不合法的情况

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

 0的个数为2时，合法的情况

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

/*
1.余数为0的两个数不能相邻
2.余数为1和余数为2的两个数不能相邻
*/
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,a[4];
        memset(a,0,sizeof a);
        scanf("%d",&n);
        for(int i=0;i<2*n;i++)
        {
            int x;
            scanf("%d",&x);
            a[x%3]++;
        }
        if(a[0]>n)
        printf("NO\n");//当0的个数大于n时，必定有两个0相邻
        else
        {
            if(a[0]<=1&&a[1]&&a[2])
            printf("NO\n");//当0的个数小于等于1,必定有1和2相邻

            if(a[1]==0||a[2]==0)
            printf("YES\n");//因为0的个数小于等于n，所以1和2的个数只能一个为0

            if(a[0]>=2&&a[1]&&a[2])
            {
                if(a[0]==2&&a[1]%2==0&&a[2]%2==0)//必定有一对1和2相邻
                printf("NO\n");
                else
                printf("YES\n");
            }
        }
    }
    return 0;
}