HDU 5755 Gambler Bo 高斯消元

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;
}