codeforces 1016D. Vasya And The Matrix
程序员文章站
2022-06-04 09:24:07
...
提议很简单,就是一个矩阵,你知道每行,每列异或后的结果,然后还原这个矩阵,如果不能还原输出NO。
很显然这是一个构造,比赛时没有想出来,真是有点傻。。但是看了好多博客发现大家都是简单的写个结论,什么全补0,只保留最后一行,一列。几乎没有解释为什么这样的。我把自己的理解写出吧。
对于这个矩阵:
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,
这样的话,这个矩阵就是如下
这样空白的那个空就是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 - 1030C Vasya and Golden Ticket(思维题)
-
codeforces 1016D. Vasya And The Matrix
-
Codeforces - Vasya and a Tree
-
Codeforces Round #234 (Div. 2):B. Inna and New Matrix of Candies_html/css_WEB-ITnose
-
Codeforces Round #234 (Div. 2):B. Inna and New Matrix of Candies_html/css_WEB-ITnose
-
Codeforces Round #512 (Div. 2, based on Technocup 2019 Elimination Round 1) D. Vasya and Triangle
-
Codeforces Round #512 (Div. 2 E. Vasya and Good Sequences 异或问题
-
Codeforces Round #512 (Div. 2) D. Vasya and Triangle
-
Codeforces Round #512 (Div. 2,) C. Vasya and Golden Ticket【暴力】
-
Codeforces Round #512 (Div. 2) - D. Vasya and Triangle (皮克公式)