Educational Codeforces Round 48 (Rated for Div. 2)异或思维

时间:2023-03-10 04:51:34
Educational Codeforces Round 48 (Rated for Div. 2)异或思维

题:https://codeforces.com/contest/1016/problem/D

题意:有一个 n * m 的矩阵, 现在给你 n 个数, 第 i 个数 a[ i ] 代表 i 这一行所有数的抑或和。

   再给你 m 个数, 第 i 个数 b[ i ] 代表 i 这一列 所有数的抑或和。
   问你是否能 构造出任意一个满足条件的矩阵, 不能输出 NO, 能输出YES 和那个 矩阵。

分析:考虑yes和no的情况,yes当且仅当,行的全部异或和等于列的全部异或和

   原因:行的全部异或和x,就是整个数组所有数的异或和,列也同样分析 y,那么显而易见这俩个异或和x==y必须相同,矩阵才能被构造出来。

   构造:简单的,就直接把一列数套在一行,另一列套在一列,是最简单的,但是考虑到第一行第一列的交叉位置,那么只要处理好这个交叉位置,那么就可以按照这种简单方法构造

        考虑第一列,这一列除了第一个位置的异或和为x^a[i],那么要达到这一列异或和==b[i],那么这个位置只能是x^a[i]^b[i],由于x==y那么恰好对于考虑行的情况也是一样的道理

#include<bits/stdc++.h>
using namespace std;
const int M=;
int mp[M][M];
int a[M],b[M];
int main(){
int n,m;
scanf("%d%d",&n,&m);
int x=,y=;
for(int i=;i<=n;i++){
cin>>a[i],x^=a[i];
}
for(int i=;i<=m;i++)
cin>>b[i],y^=b[i];
if(x!=y)
puts("NO");
else{ puts("YES");
x^=a[];
x^=b[];
mp[][]=x;
for(int i=;i<=n;i++)
mp[i][]=a[i];
for(int i=;i<=m;i++)
mp[][i]=b[i];
for(int i=;i<=n;i++){
for(int j=;j<=m;j++)
cout<<mp[i][j]<<" ";
cout<<endl;
}
}
return ;
}