大家好,又见面了,我是你们的朋友全栈君。
Description
我们称一个由0和1组成的矩阵是和谐的,当且仅当每个元素都有偶数个相邻的1。一个元素相邻的元素包括它本
身,及他上下左右的4个元素(如果存在)。
给定矩阵的行数和列数,请计算并输出一个和谐的矩阵。注意:所有元素为0的矩阵是不允许的。
Input
输入一行,包含两个空格分隔的整数m和n,分别表示矩阵的行数和列数。
Output
输出包含m行,每行n个空格分隔整数(0或1),为所求矩阵。测试数据保证有解。
Sample Input
Sample Output
1 1 1 0
0 0 0 1
1 1 0 1
数据范围
1 <=m, n <=40
Solution
讲真这个题不知道比1770那个题低到哪里去了(其实差不多)
会做那个题一定会做这个【认真脸
很明显这个还是构造01矩阵然后解异或方程组
只不过这个构造出来的矩阵是n*m的,n^3显然很吃力
那么我们把1770代码里的异或用bitset来搞常数就小很多了
听说bitset随便虐1e9?
Code
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<bitset> 5 #define N (1600+100) 6 #define id(x,y) (x-1)*m+y 7 using namespace std; 8 9 bitset<N>f[N];10 int ans[N],n,m;11 int dx[7]={ 0,1,-1,0,0,0},dy[6]={ 0,0,0,1,-1,0};12 13 void Gauss(int n)14 {15 for (int i=1; i<=n; ++i)16 {17 int num=i;18 for (int j=i+1; j<=n; ++j)19 if (f[j][i]>f[num][i]) num=j;20 if (num!=i) swap(f[i],f[num]);21 22 for (int j=i+1; j<=n; ++j)23 if (f[j][i]) f[j]^=f[i];//这里用bitset来搞常数好像很小 24 }25 for (int i=n; i>=1; --i)26 {27 if (!f[i][i]) ans[i]=1;28 else29 {30 for (int j=i+1; j<=n; ++j)31 f[i][n+1]=f[i][n+1]^(f[i][j]*ans[j]);32 ans[i]=f[i][n+1];33 }34 }35 }36 37 int main()38 {39 scanf("%d%d",&n,&m);40 for (int i=1; i<=n; ++i)41 for (int j=1; j<=m; ++j)42 for (int k=1; k<=5; ++k)43 {44 int x=i+dx[k],y=j+dy[k];45 if (x>0 && x<=n && y>0 && y<=m)46 f[id(i,j)][id(x,y)]=1;47 }48 Gauss(n*m);49 for (int i=1; i<=n; ++i)50 {51 for (int j=1; j<=m-1; ++j)52 printf("%d ",ans[id(i,j)]);53 printf("%d\n",ans[id(i,m)]);54 }55 }
转载于:https://www.cnblogs.com/refun/p/8953107.html
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107559.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...