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（高斯消元）

最新文章

热门文章