MYF

HDU 5755 Gambler Bo

Posted on | In | | Visitors

题目链接

HDU 5755

题目类型：找规律

题目来源：2016年多校Round3

题目分析

题目大意

给定nm的矩阵，每个位置的值只会为{0, 1, 2}中的一个。当选择一个点时，该点会自增2，周围四个方向的点（如果存在的话）会自增1，当其大于等于3时，会自动对3取模，问在选择小于2\n*m个点，如何使这个矩阵变为0？

解析

比赛时想的比较复杂，想去枚举点用dfs去跑，O(n3m3)不会T真的很神奇，900^3大概是7.29*108，理论上会T。

实际上使用最简单的解决多元方程的方法即可。那么要怎么建立方程组呢？对于每一个下标为p的点，如果该点选择1次，本身会自增2，当其周围的点下标分别为l, r, u ,d，当这四个点共计选择k次的话，该点本身也会自增k，当p点位置本身值为s时，我们希望该点选择(3-k)%3次。那么我们就可以设这nm个点各被选择了x1,x2,x3…x(n\m)次，然后对于每一个点找到对应的几个未知数累加求解即可。至于为何要选择(3-k)%3，对于一个点来讲，如果我可以让他自增4次，为什么不能让他自增1次呢？以及多元方程组为什么不会出现负数，这点小弟无法证明，如有大神幸临小站，还望指点。

代码

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
/*
 参数说明：
 equ表示等式数量
 var表示未知数数量
 a数组中[0~n-1][0~n-1]存储系数矩阵，a[0~n-1][n]存储等号右边的值
 x数组储存最后求出来的值

 优点：在数据较小的情况下跑的比“高斯消元2_琦神版”快一点
 缺点：数据可以处理范围较小
 
 示例题目：HDU5755
*/
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const double eps=1e-8;


/***高斯消元模版开始**/
const int maxn=1000+5;
const int mod=3;
int a[maxn][maxn] = {0}, x[maxn] = {0};
void Gauss(int equ, int var) {
    int row, max_r, col;
    for(row = 0, col = 0; col < var && row < equ; col++, row++) {
        max_r = row;
        for(int i = row + 1; i < equ; i++) {
            if(abs(a[i][col]) > abs(a[max_r][col])) {
                max_r = i;
            }
        }
        if(!a[max_r][col]) {
            row--;
            continue;
        }
        if(row != max_r) {
            for(int j = 0; j <= var; j++) {
                swap(a[row][j], a[max_r][j]);
            }
        }
        for(int i = row + 1; i < equ; i++) {
            if(a[i][col]) {
                int lcm = a[i][col] / __gcd(a[i][col], a[row][col]) * a[row][col];
                int t1 = lcm / a[i][col];
                int t2 = lcm / a[row][col];
                for(int j = col; j <= var; j++) {
                    a[i][j] = ((a[i][j] * t1 - a[row][j] * t2) % mod + mod) % mod;
                }
            }
        }
    }
    // print();
    // for(int i = row; i < equ; i++)
    //     if(a[i][var]) continue;
    for(int i = var - 1; i >= 0; i--) {
        x[i] = a[i][var];
        for(int j = i + 1; j < var; j++) {
            x[i] = ((x[i] - a[i][j] * x[j]) % mod + mod) % mod;
        }
        //mod 3下的逆元就是其本身
        x[i] = a[i][i] * x[i] % mod;
        // printf("x[%d] = %d\n", i, x[i]);
    }
}
/***高斯消元模版结束**/
int n,mp[maxn];
int main(){
    int t,N,M;
    scanf("%d",&t);
    while (t--) {
        Memset(a,0);
        scanf("%d%d",&N,&M);
        n=N*M;
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                scanf("%d",&mp[i*M+j]);
            }
        }
        for (int i=0; i<n; i++) {
            a[i][n]=(3-mp[i])%3;
            a[i][i]=2;
            int l = i-1;
            int r = i+1;
            int u = i-M;
            int d = i+M;
            if (l>=0&&l<n&&i%M!=0) {
                a[i][l]=1;
            }
            if (r>=0&&r<n&&i%M!=M-1) {
                a[i][r]=1;
            }
            if (u>=0&&u<n) {
                a[i][u]=1;
            }
            if (d>=0&&d<n) {
                a[i][d]=1;
            }
        }
        Gauss(n,n);
        vector<int>v;
        for (int i=0; i<n; i++) {
            while (x[i]!=0) {
                v.PB(i);
                x[i]--;
            }
        }
        int sz =  v.size();
        cout<<sz<<endl;
        for (int i=0; i<sz; i++) {
            printf("%d %d\n",v[i]/M+1,v[i]%M+1);
        }
    }
}