BZOJ3503:[CQOI2014]和谐矩阵(高斯消元,bitset)

2022-08-09 18:00:35

Description

我们称一个由0和1组成的矩阵是和谐的，当且仅当每个元素都有偶数个相邻的1。一个元素相邻的元素包括它本
身，及他上下左右的4个元素（如果存在）。
给定矩阵的行数和列数，请计算并输出一个和谐的矩阵。注意：所有元素为0的矩阵是不允许的。

Input

输入一行，包含两个空格分隔的整数m和n，分别表示矩阵的行数和列数。

Output

输出包含m行，每行n个空格分隔整数（0或1），为所求矩阵。测试数据保证有解。

Sample Input

4 4

Sample Output

0 1 0 0
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

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<bitset>

 #define N (1600+100)

 #define id(x,y) (x-1)*m+y

 using namespace std;

 bitset<N>f[N];

 int ans[N],n,m;

 int dx[]={,,-,,,},dy[]={,,,,-,};

 void Gauss(int n)

 {

     for (int i=; i<=n; ++i)

     {

         int num=i;

         for (int j=i+; j<=n; ++j)

             if (f[j][i]>f[num][i]) num=j;

         if (num!=i) swap(f[i],f[num]);

         for (int j=i+; j<=n; ++j)

             if (f[j][i]) f[j]^=f[i];//这里用bitset来搞常数好像很小

     }

     for (int i=n; i>=; --i)

     {

         if (!f[i][i]) ans[i]=;

         else

         {

             for (int j=i+; j<=n; ++j)

                 f[i][n+]=f[i][n+]^(f[i][j]*ans[j]);

             ans[i]=f[i][n+];

         }

     }

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for (int i=; i<=n; ++i)

         for (int j=; j<=m; ++j)

             for (int k=; k<=; ++k)

             {

                 int x=i+dx[k],y=j+dy[k];

                 if (x> && x<=n && y> && y<=m)

                     f[id(i,j)][id(x,y)]=;

             }

     Gauss(n*m);

     for (int i=; i<=n; ++i)

     {

         for (int j=; j<=m-; ++j)

             printf("%d ",ans[id(i,j)]);

         printf("%d\n",ans[id(i,m)]);

     }

 }

码农公寓