首页 > 代码库 > Codeforces Gym10008E Harmonious Matrices（高斯消元）
Codeforces Gym10008E Harmonious Matrices（高斯消元）
【题目链接】 http://codeforces.com/gym/100008/
【题目大意】
给出 一个n*m的矩阵，要求用0和1填满，使得每个位置和周围四格相加为偶数，要求1的数目尽量多。
【题解】
首先，如果确定第一排的填法，要求最终结果为偶数，那么就能推出第二排的填法，同理可以依次推出整个矩阵，因此我们设置第一排填法为未知数，可以将方程推到最后一排，因为n+1排填的数字一定是0，这样子就可以得到m个方程。高斯消元求解即可，因为在要求1最多，因此自由变元尽量设为1.
【代码】
#include <cstdio>#include <algorithm> #include <cstring>using namespace std;#define rep(i,n) for(int i=1;i<=n;i++)const int N=50;int T,n,m,p[N][N];long long f[N][N];void Gauss(int n,int m) { int i,j,k,h,w; for(i=j=1;j<m;j++,w=0){ for(k=i;k<=n;k++)if(p[k][j])w=k; if(w){ for(k=j;k<=m;k++)swap(p[i][k],p[w][k]); for(k=i+1;k<=n;k++) if(p[k][j]){ for(h=j;h<=m;h++)p[k][h]^=p[i][h]; }i++; }if(i>n)break ; }for(j=1;j<m;j++)f[1][j]=1; for(j=i-1;j;j--){ for(k=1;k<m;k++)if(p[j][k])break ; f[1][k]=f[j][m]; for(h=k+1;h<m;h++)if(f[1][h]&&p[j][h])f[1][k]^=1; } } int main(){ scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); memset(p,0,sizeof(p)); memset(f,0,sizeof(f)); rep(i,m)f[1][i]=1LL<<i; rep(i,n)rep(j,m)f[i+1][j]=f[i][j-1]^f[i][j]^f[i][j+1]^f[i-1][j]; rep(i,m)rep(j,m)if(f[n+1][i]&(1LL<<j))p[i][j]=1; Gauss(m,m+1); for(int i=2;i<=n;i++)rep(j,m)f[i][j]=f[i-1][j-1]^f[i-1][j]^f[i-1][j+1]^f[i-2][j]; rep(i,n){rep(j,m-1)printf("%lld ",f[i][j]);printf("%lld\n",f[i][m]);} }return 0;}
Codeforces Gym10008E Harmonious Matrices（高斯消元）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。