首页 > 其他 > 详细

HDU - 5755:Gambler Bo (开关问题,%3意义下的高斯消元)

时间:2019-04-25 16:28:38      阅读:147      评论:0      收藏:0      [点我收藏+]

pro:给定N*M的矩阵,每次操作一个位置,它会增加2,周围4个位置会增加1。给定初始状态,求一种方案,使得最后的数都为0;(%3意义下。

sol:(N*M)^3的复杂度的居然过了。          好像标程是M^3的,因为第一排确定了,后面的都确定了。所以我们只要设关于第一排的方程,那么跑下来,第N+1排的都为0,则合法。

(此题由于3的特殊性,x关于3的逆元=x;所以不用求逆元

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=1010;
int a[maxn][maxn],ans[maxn];
int x[4]={0,0,1,-1};
int y[4]={1,-1,0,0};
void Guass(int N)
{
    rep(i,0,N-1){
        int t=i;
        rep(j,i+1,N-1) if(a[j][i]>a[t][i]) t=j;
        if(i!=t) rep(j,i,N) swap(a[i][j],a[t][j]);
        if(!a[i][i]) continue;
        rep(j,i+1,N-1){
            if(!a[j][i]) continue;
                int t1=a[i][i],t2=a[j][i];//保留,不用直接带进去
                rep(k,i,N)
                  a[j][k]=((a[j][k]*t1-a[i][k]*t2)%3+3)%3;
        }
    }
    for(int i=N-1;i>=0;i--){
        a[i][N]=a[i][N]*a[i][i]%3;
        rep(j,0,i-1)
            a[j][N]=((a[j][N]-a[i][N]*a[j][i])%3+3)%3;
    }
}
int main()
{
    int T,N,M,S,t,p;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&N,&M); S=N*M;
        rep(i,0,S) rep(j,0,S) a[i][j]=0;
        rep(i,0,N-1) rep(j,0,M-1){
            t=i*M+j;
            scanf("%d",&a[t][S]);
            a[t][S]=3-a[t][S];
        }
        rep(i,0,S-1) a[i][i]=2;
        rep(i,0,N-1)
         rep(j,0,M-1){
            t=i*M+j;
            rep(k,0,3) {
                if(i+x[k]>=0&&i+x[k]<N&&j+y[k]>=0&&j+y[k]<M){
                    a[(i+x[k])*M+j+y[k]][t]=1;
                }
            }
        }
        Guass(S);
        int res=0;
        rep(i,0,S-1) res+=a[i][S];
        printf("%d\n",res);
        rep(i,0,S-1){
            p=i/M+1; t=i%M+1;
            if(a[i][S]) printf("%d %d\n",p,t);
            if(a[i][S]==2) printf("%d %d\n",p,t);
        }
    }
    return 0;
}

 

HDU - 5755:Gambler Bo (开关问题,%3意义下的高斯消元)

原文:https://www.cnblogs.com/hua-dong/p/10768963.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!