Bluefissure's Blog

A Place for Recording

0%

HDU 5755 Gambler Bo 高斯消元

Posted on Edited on In Disqus:

2016 Multischool-Training-3-1004

题目链接

思路：

首先这道题比赛时路子有点野并没有A掉，后来看才发现高斯消元能够很快的求出答案，主要方法类似于反转开关，只是反转开关只有两种操作和两种状态，因此由列出的xor方程便能很容易的异或解出，这个题目有三种操作（点击一次或两次）以及三种状态（0,1,2），因此列出的方程不是异或方程，而是模3域下的加法（即\((x+y)\%3\)）。

对每个点，点击它的次数设为\(x_i\)，则其对自己的贡献为2，它周围格子对它的贡献为1，他们的和与初始格子上的值的和加起来应该等于0（模3域下），因此可以列出\(N\times M\)个方程，\(N\times M\)个变量。

因为数域是模3域，因此我们可以只用加法消元，高斯消元不再多讲，有自由变元直接取0就行，另外需要注意的是最后求\(x_i\)的过程中如果常数是1而系数是2需要给常数+3再求得结果（因为是模3域），其他情况如果除不尽则结果为0（因为系数只可能是1或者2），具体不详细讲了，直接看代码就行。

哦对，高斯消元复杂度 \(O({ \left( N\times M \right)  }^{ 3 })\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define MAXN 1000
#define range(x,y) (x>=0&&x<N&&y>=0&&y<M)
#define f(a,b) (((a)+(b))%3)
#define getx(i,j) ((i)*M+(j))
#define geti(x) ((x)/M)
#define getj(x) ((x)-(x)/M*M)
int N,M;
int mp[35][35];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int x[MAXN];//answer
int g[MAXN][MAXN];//augmented matrix
int var,equ;
inline void uniqueans(int var)
{
    for(int i=var-1;i>=0;i--){
        if(!g[i][i]){
            x[i]=0;
            continue;
        }
        int tmp=g[i][var];
        for(int j=i+1;j<var;j++){
            int v=((g[i][j]==0)?0:3-g[i][j]);
            tmp+=v*x[j];
        }
        if(tmp%g[i][i]==0)
            x[i]=tmp/g[i][i];
        else if((tmp+3)%g[i][i]==0)
            x[i]=(tmp+3)/g[i][i];
        else x[i]=0;
        x[i]%=3;
    }
}
inline int gauss(int equ,int var)
{
    int col,k,maxr;
    for(k=0,col=0;k<equ&&col<var;k++,col++){
        maxr=k;
        for(int i=k+1;i<equ;i++)
            if(abs(g[maxr][col])<abs(g[i][col]))
                maxr=i;
        if(maxr!=k)
            for(int i=col;i<=var;i++)
                swap(g[k][i],g[maxr][i]);
        if(g[k][col]==0){
            k--;continue;
        }
        for(int i=k+1;i<equ;i++)
            if(g[i][col]!=0){
                int v=((g[i][col]+g[k][col]==3)?1:2);
                for(int j=col;j<=var;j++)
                    g[i][j]=f(g[i][j],v*g[k][j]);
            }
    }
    for(int i=k;i<equ;i++)
        if(g[i][var]!=0) return -1;//no answer
    //if(k<var) return var-k;//inf answer return number of free vars
    uniqueans(var);
    return 0;//ans -> x[]
}
int main()
{
    int T,t;
    scanf("%d",&T);
    while(T--){
        memset(g,0,sizeof(g));
        memset(x,0,sizeof(x));
        scanf("%d%d",&N,&M);
        var=equ=N*M;
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                scanf("%d",&t);
                g[getx(i,j)][var]=t==0?0:3-t;
                g[getx(i,j)][getx(i,j)]=2;
                for(int k=0;k<4;k++){
                    int x=i+dx[k],y=j+dy[k];
                    if(range(x,y)) g[getx(i,j)][getx(x,y)]=1;
                }
            }
        }
        int err=gauss(equ,var);
        int cnt=0;
        for(int i=0;i<var;i++)
            cnt+=(x[i]%=3);
        printf("%d\n",cnt);
        for(int i=0;i<var;i++){
            while(x[i]--)
                printf("%d %d\n",geti(i)+1,getj(i)+1);
        }
    }
    return 0;
}