欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

codeforces 1016D. Vasya And The Matrix

程序员文章站 2022-06-04 09:24:07
...

链接
codeforces 1016D. Vasya And The Matrix

提议很简单,就是一个矩阵,你知道每行,每列异或后的结果,然后还原这个矩阵,如果不能还原输出NO。

很显然这是一个构造,比赛时没有想出来,真是有点傻。。但是看了好多博客发现大家都是简单的写个结论,什么全补0,只保留最后一行,一列。几乎没有解释为什么这样的。我把自己的理解写出吧。
codeforces 1016D. Vasya And The Matrix
对于这个矩阵:
a1 = x1^x2^x3,a2 = x4^x5^x6;
b1 = x1^x4,b2 = x2^x5,b3 = x3^x6;
所以a1^a2 = x1^x2^x3^x4^x5^x6;
b1^b2^b3 = x1^x2^x3^x4^x5^x6;
所以行列异或值是否相等,或者二者再异或结果为0,就是判断是否有解的条件来。
对于有解的情况我们仍要构造出一种矩阵,我们可以只考虑最后一行,一列空的做法。也可以逐位枚举来计算。
我们如果把前面都填上一样的数,这样最后一列数也可以确定下来,因为0异或任何数都为0,所以我们一般是填0,
这样的话,这个矩阵就是如下
codeforces 1016D. Vasya And The Matrix
这样空白的那个空就是b1^b2^a2求得,或者是a1^b3求得。这样填一定符合吗?我们首先来看这俩个的异或结果
b1^b2^a2 = x1^x4^x2^x5^x4^x5^x6 = x1^x2^x6;
a1^b3 = x1^x2^x3^x3^x6 = x1^x2^x6;
因为二者是相等的,所以任意异或出来的解一定是二者都符合的。所以这一定是正确的解。

代码如下:

#include<bits/stdc++.h>

using namespace std;
const int MAX = 110;
int a[MAX],b[MAX],res[MAX][MAX];
int main(void){
    int N,M;
    cin >> N >> M;
    int tempA = 0,tempB = 0;
    for(int i=1;i<=N;++i){
        cin >> a[i];
        tempA ^= a[i];
    }
    for(int i=1;i<=M;++i){
        cin >> b[i];
        tempB ^= b[i];
    }
    if(tempA != tempB){
        cout << "NO" << endl;
    }
    else{
        cout << "YES" << endl;
        for(int i=1;i<=N-1;++i){
            for(int j=1;j<=M-1;++j){
                res[i][j] = 0;
            }
            res[i][M] = a[i];
        }
        int v = 0;
        for(int i=1;i<=M-1;++i){
            res[N][i] = b[i];
            v ^= b[i];
        }
        v ^= a[N];
        res[N][M] = v;
        for(int i=1;i<=N;++i){
            for(int j=1;j<=M;++j){
                cout << res[i][j];
                if(j != M)  cout << " ";
                else    cout << endl;
            }
        }
    }
    return 0;
}
相关标签: codeforces