[XOR][思维][构造] codeforces 1016D Vasya And The Matrix

首先确定,什么时候是NO,因为把ai全部异或起来一定是整个矩阵全异或,bi同理所以这俩数字应该相等,xor为0,如果不为0一定是不存在的。所以,如果存在,那么a全部xor和b全部xor一定是相等的,记为tmp

否则的话,把b1到bm-1全放到第一行的左边m-1个空位,剩下的右边那个补上一个t使得这一行xor为a1,此时最右边一列的xor为tmp^a1^t=tmp^(b1^bi..^bm-1)==bm,所以这样构造的矩阵一定满足要求!!!

#include 
#include 
#include
#include
#include
#include
#include

using namespace std;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
typedef long long LL;

int a[maxn],b[maxn];

int main()
{
    int n,m,tmp1=0,tmp2=0;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        tmp1^=a[i];
    }

    for (int i=1;i<=m;i++)
    {
        scanf("%d",&b[i]);
        tmp2^=b[i];
    }
    if(tmp1^tmp2)
        printf("NO\n");
    else
    {
        printf("YES\n");
        for (int i=1;i

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据