problem.php?pid=2076

输入一个T表示有T个样例
每组实例一个整数n(0〈n〈1000
接下来输入2*n个数字，代表一个2*n的矩阵（每个数大于0小于1000）

这些数可以任意调换位置，如果任意一个数与相邻一个数相加和不是三的倍数，则输出YES，反之输出NO。

占一行。

样例输入

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

样例输出

YES
YES

Preview

emmm，本来这场比赛有一道矩阵快速幂的fib，结果写到一半被学长改掉了，这题题目恰巧又说矩阵，导致以为换题了全程死扣矩阵解法，毫无悬念地GG.

解题思路：

因为数字能任意换位置，所以矩阵的格式原则上没有太大作用.

将输入所有数字对3取余，统计0的个数a.

原则上3的倍数最完美会出现如下情况：

　　　　0 X 0 X 0

　　　X 0 X 0 X

这种交错情况下就能无视其他非3倍数了，因为我们只需要将a与 n 进行比较.

显然易见，当 a>n时候，必定会出现0 与 0镶嵌的情况，因此必定输出 NO.

此题关键在于a<=n 时候会有 a<=1 和 a==2 的特殊情况.

当a<=1时。出现如下情况：

　　　　　　?XX

　　　　　　XXX

显然，无论 ? 是否为0，X只能全为2或者全为1.

当a==2时，原则上必定要如下情况:

　　　　　　X0XX

　　　　　　XX0X

同上情况，X全为1或全为2必定符合，再仔细看，其实0 0 这斜着的一竖两边分别全为1 2其实也符合.

AC代码：

//E

#include <cstdio>

#include <cstring>

using namespace std;

int main()

{

    int t,x,n;

    scanf("%d",&t);

    while(t--)

    {

        int a=,b=,c=;

        scanf("%d",&n);

        //memset(a,0,sizeof(a));

        for(int i=; i<=n*; i++)

        {

                scanf("%d",&x);

                x%=;

                if(x==) a++;

                else if (x==) b++;

                else c++;

        }

        bool flag=true;

        if(a>n) flag=false;

        else

        {

            if(a<=)

            {

                if(b==||c==) flag=true;

                else flag=false;

            }

            else if(a==)

            {

                if(c%==&&b%==) flag=true;

                else if(b==||c==) flag=true;

                else flag=false;

            }

        }

        if(flag)  puts("YES");

        else puts("NO");

    }

    return ;

}

巴特西

ZZNU 2076(退役学长最后的神功 zz题)