Rearrangement_牛客博客

In a two dimensional array of integers of size $\times n2×n, is it possible to rearrange integers so that the sum of two adjacent elements (which are adjacent in a common row or a common column) is never divisible by three?$

Input

The input has several test cases and the first line contains an integer $\le t \le 200)t(1≤t≤200) which is the number of test cases.$

In each case, the first line contains an integers $\le n \le 10000)n(1≤n≤10000) indicating the number of columns in the array. The second line contains the elements of the array in the first row separated by single spaces. The third line contains the elements of the array in the second row separated by single spaces. The elements will be positive integers less then 100000010000001000000.$

Output

For each test case, output “YES” in a single line if any valid rearrangement exists, or “NO” if not.

样例输入

6
3
3 6 9
1 4 7
3
3 6 9
1 3 8
5
1 2 3 4 5
6 7 8 9 10
10
1 1 1 1 1 1 1 1 1 1
2 3 2 3 2 3 2 3 2 3  
2
3 1
2 3
2
3 1
1 2

样例输出

YES
NO
YES
YES
YES
NO
一个大水题嘤嘤嘤

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int s[20100]={0};
int main()
{
    ios::sync_with_stdio(false);
    int i,m,n;
    int T;
    cin>>T;
    while(T--)
    {
        bool flag=0;
        int a=0,b=0,c=0;
        cin>>n;
        for(i=1;i<=2*n;i++)
        {
            cin>>m;
            s[i]=m%3;
            if(s[i]==0) a++;
            else if(s[i]==1) b++;
            else if(s[i]==2) c++;
        }
        if(a>n) flag=0;
        else if(a==n) flag=1;
        else if(a<n){
            if(b==0||c==0) flag=1;
            else if(a<=1) flag=0;
            else if(a==2){
                if(b%2==0&&c%2==0) flag=0;
                else flag=1;
            }
            else flag=1;
        }
        if(flag) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

View Code

首先对三取模这是最先想到的

然后对a在各个情况下讨论

当a大于n 肯定是不可能的，因为这样两个0一定会相遇

当a大于n一定可以，交叉嘛

当a小于n

有b和c有只要有一个为0，一定可以

然后是n小于等于1 一定不行

接下来n大于1：

耗费了两个小时啊啊啊

首先这肯定只能找规律，跟数量有关吗，很明显没有关系

那应该跟奇数还是偶数有关

当n奇数我发现其他数一定为一奇一偶，然后一定可以；

于是我就想当n为偶数的时候，然后我就拿2当例子，做了一大堆实验，WA了好多发；

后来才知道2是一个特殊情况，我不能就通过2来断定偶数都是这个规律