当前位置: 代码迷 >> 综合 >> codeforces D. Vasya And The Matrix 数学思维积累
  详细解决方案

codeforces D. Vasya And The Matrix 数学思维积累

热度:14   发布时间:2023-11-19 22:44:09.0

http://codeforces.com/contest/1016/problem/D

题意:

NxM的矩阵, 给你第1行到第n行的整行的异或和 , 以及第1列到第m列的整列上的异或和。问能否构造出这个矩阵

思路:

无论是从行的角度看, 还是列的角度看,他们描述的都是同一个矩阵, 因此如若矩阵合法,那么他们的异或和比必须为0, 相当于整个矩阵异或了两次。 可以判断是否合法之后,我们怎么构造呢?这里就需要积累了,小本本记下。 我们可以这样构造
0 0 0 a[1]
0 0 0 a[2]
b[1] b[2] b[3] x

怎么算x呢 , 假设行上的异或和为a0 (也等于列的异或和), 那么a0就表示整个矩阵的异或和,
则 a0 ^ a[3] 得到 a[1] ^ a[ 2 ] , 然后拿 b[4] ^ ( a[1] ^ a[ 2 ] )就得到t位置上的值了。异或大法好

代码:

#include<bits/stdc++.h>
#define MAXN 105
using namespace std;
int a[MAXN],b[MAXN];
int a0,b0;
int main()
{int n,m,i,j;scanf("%d %d",&n,&m);for(i=1; i<=n; i++){scanf("%d",&a[i]);a0^=a[i];}for(i=1; i<=m; i++){scanf("%d",&b[i]);b0^=b[i];}if(a0!=b0)printf("NO\n");else{printf("YES\n");for(int i=1; i<=n-1; i++){for(int j=1; j<=m-1; j++)printf("0 ");printf("%d\n",a[i]);}for(int j=1; j<=m-1; j++)printf("%d ",b[j]);printf("%d\n",b[m]^ a0^a[n]);}return 0;
}
  相关解决方案