hdu 5755 Gambler Bo 高斯消元

Mike

Gambler Bo

题目连接：
http://acm.hdu.edu.cn/showproblem.php?pid=5755

Description
Gambler Bo is very proficient in a matrix game.
You have a N×M matrix, every cell has a value in {0,1,2}.
In this game, you can choose a cell in the matrix, plus 2 to this cell, and plus 1 to all the adjacent cells.
for example, you choose the cell (x,y), the value of (x,y) will be plused 2, and the value of (x−1,y)(x+1,y)(x,y−1)(x,y+1) will be plused 1.
if you choose the cell (1,2), the cell (1,2) will be plused 2, and the cell (2,2)(1,1)(1,3) will be plused 1, the cell (0,2) won't be changed because it's out of the matrix.
If the values of some cells is exceed 2, then these values will be modulo 3.
Gambler Bo gives you such a matrix, your task is making all value of this matrix to 0 by doing above operations no more than 2NM times.

Input
First line, an integer T. There are T test cases.
In each test, first line is two integers N,M, and following N lines describe the matrix of this test case.
T≤10,1≤N,M≤30, the matrix is random and guarantee that there is at least one operation solution.

Output
For each test, first line contains an integer num(0≤num≤2NM) describing the operation times.
Following num lines, each line contains two integers x,y(1≤x≤N,1≤y≤M) describing the operation cell.
The answer may not be unique, you can output any one.

Sample Input
2
2 3
2 1 2
0 2 0
3 3
1 0 1
0 1 0
1 0 1

Sample Output
1
1 2
5
1 1
1 3
2 2
3 1
3 3

Hint

题意
给你nm的矩阵，矩阵里面有值
你可以操作使得一个格子加二，然后他周围的格子加1，然后所有格子都得mod3
让你构造一个方案，使得所有格子都是0了

题解：
老题，开关灯的mod3版本。
两种做法 900^3，这个可以用bitset优化，毕竟只用存012三个状态。
30^3，知道第一行之后，剩下的可以自己推导出来，这个推倒比较烦，大家可以去试试。
下面代码是最智障版本，裸的900^3

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 31;
const int Maxn = 31*31;
int n,m;
int mp[maxn][maxn],id[maxn][maxn],cnt=0;
int a[Maxn][Maxn],x[Maxn];
int gcd(int a,int b){
  if(b==0)return a;
  return gcd(b,a%b);
}
int lcm(int a,int b){
  return a*b/gcd(a,b);
}
void solve(){
  memset(a,0,sizeof(a));cnt=0;
  memset(mp,0,sizeof(mp));
  memset(id,0,sizeof(id));
  memset(x,0,sizeof(x));
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
      scanf("%d",&mp[i][j]);
      id[i][j]=++cnt;
    }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      a[id[i][j]][n*m+1]=(3-mp[i][j])%3;
      a[id[i][j]][id[i][j]]=2;
      if(i>1)a[id[i][j]][id[i-1][j]]=1;
      if(i<n)a[id[i][j]][id[i+1][j]]=1;
      if(j>1)a[id[i][j]][id[i][j-1]]=1;
      if(j<m)a[id[i][j]][id[i][j+1]]=1;
    }
  }
  for(int i=1;i<=n*m;i++){
    int p=i;
    for(int j=i+1;j<=n*m;j++)
      if(abs(a[j][i])>abs(a[p][i]))
        p=j;
    if(a[p][i]){
      for(int j=i;j<=n*m+1;j++)swap(a[i][j],a[p][j]);
      for(int j=i+1;j<=n*m;j++){
        if(a[j][i]){
          int d = lcm(a[j][i],a[i][i]);
          int x1 = d/a[j][i],x2 = d/a[i][i];
          for(int t=i;t<=n*m+1;t++)
            a[j][t]=((a[j][t]*x1-a[i][t]*x2)%3+3)%3;
        }
      }
    }
  }
  for(int i=n*m;i>=1;i--){
    x[i]=a[i][n*m+1];
    for(int j=i+1;j<=n*m;j++){
      x[i]=((x[i]-a[i][j]*x[j])%3+3)%3;
    }
    x[i]=a[i][i]*x[i]%3;
  }
  int ans = 0;
  for(int i=1;i<=n*m;i++){
    ans+=x[i];
  }
  printf("%d\n",ans);
  for(int i=1;i<=n*m;i++){
    while(x[i]>0){
      printf("%d %d\n",(i-1)/m+1,(i-1)%m+1);
      x[i]--;
    }
  }
}
int main(){
  int t;
  scanf("%d",&t);
  while(t--)solve();
  return 0;
}