2016多校第三場 HDU 5755 -开发者知识库

2016多校第三場 HDU 5755 -开发者知识库,第1张

一道明顯的高斯消元模板題。。賽上sb的覺得 n3m3 會炸沒敢寫,推了半天最后一題的積分。。。。

建邊也很簡單,都是套路,模板。。

有的讀者可能覺得程序寫的有點問題,建邊應該是別的點對當前點的貢獻,但是因為這個題的性質,這個問題可以不考慮

//
// Created by Running Photon
// Copyright (c) 2015 Running Photon. All rights reserved.
//
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <sstream>
#include <set>
#include <vector>
#include <stack>
#define ALL(x) x.begin(), x.end()
#define INS(x) inserter(x, x,begin())
#define ll long long
#define CLR(x) memset(x, 0, sizeof x)
using namespace std;
const int inf = 0x3f3f3f3f;
const int MOD = 3;
const int maxn = 1e6 10;
const int maxv = 1e3 10;
const double eps = 1e-9;

int a[maxv][maxv];
int x[maxv];
int mp[905];
int all;
void print() {
for(int i = 0; i < all; i ) {
for(int j = 0; j <= all; j ) {
printf("%d ", a[i][j]);
}
puts("");
}
puts("");
}
int Gauss(int equ, int var) {
int row, max_r, col;
// print();
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]);

}
}
bool check(int u) {
return u >= 0 && u < all;
}
int main() {
#ifdef LOCAL
freopen("C:\Users\Administrator\Desktop\in.txt", "r", stdin);
freopen("C:\Users\Administrator\Desktop\out.txt","w",stdout);
#endif
// ios_base::sync_with_stdio(0);
int T;
scanf("%d", &T);
while(T--) {
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i ) {
for(int j = 0; j < m; j ) {
scanf("%d", &mp[i*m j]);
}
}
all = n * m;
CLR(a);
for(int i = 0; i < all; i ) {
int u = i - m;
int d = i m;
int l = i - 1;
int r = i 1;
a[i][i] = 2;
a[i][all] = (3 - mp[i]) % MOD;
if(check(u)) a[i][u] = 1;
if(check(d)) a[i][d] = 1;
if(check(l) && i % m != 0) a[i][l] = 1;
if(check(r) && i % m != m - 1) a[i][r] = 1;
}
Gauss(all, all);
std::vector<int> ans;
for(int i = 0; i < all; i ) {
while(x[i]) {
x[i]--;
ans.push_back(i);
}
}
cout << ans.size() << endl;
for(int i = 0; i < ans.size(); i ) {
int r = ans[i] / m;
int c = ans[i] % m;
printf("%d %d\n", r 1, c 1);
}
}

return 0;
}

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复