题解：CF1955G GCD on a grid

题目大意

对于

n \times m

的网格中，每一个格子都有一个对应的

a[i][j]

，求出从

a[1][1]

到

a[n][m]

路径中所有数的最大公约数所能达到的最大值。

思路简述

好水的绿题。观察到数据范围

n,m

较小，且

a[i][j] \le 10^6

。
考虑暴力乱搞。
由于所有路径必定经过

a[1][1]

，所以最后输出的答案必定为

a[1][1]

的因数。
故而我们可以先找出

a[1][1]

的所有因数，从大到小到暴力枚举答案，每个检验一下是否存在合法方案，若存在，则输出。
如何检验呢。
考虑用

f[i][j]

表示第

i

行

j

列的位置是否可以到达，则转移方程可以表示为：

f[i][j]=\left\{\begin{matrix} 0，x\nmid a[i][j] \\ f[i-1][j] | f[i][j-1],x\mid a[i][j] \end{matrix}\right.

这里存约数时使用优先队列或者开个数组排序一下都可以，个人认为优先队列更方便一些，所以我是使用优先队列实现的。
这里要记得每次检验答案是否成立时要清空

f

数组和队列，而且 memset 容易超时。
结合代码看看挺好懂的，结束撒花撒花。

代码实现

CF提交记录
马蜂良好。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 110;
int a[N][N], f[N][N]; 
priority_queue<int> q;
int n, m; 
bool check (int x) { // 检验 
	for (int i = 1; i <= n; i ++ ) {
		for (int j = 1; j <= m; j ++ ) {
			f[i][j] = 0;
		}
	}
	f[1][1] = 1; // 初始化 
	for (int i = 1; i <= n; i ++ ) {
		for (int j = 1; j <= m; j ++ ) {
			if (i == 1 && j == 1) continue;
			if (a[i][j] % x == 0) {  
				f[i][j] = f[i - 1][j] | f[i][j - 1]; // 从上方和左边转移 
			}
		}
	}
	return f[n][m]; // 返回 
}
void solve () {
	while (!q.empty()) q.pop(); // 清空 
	cin >> n >> m;
	for (int i = 1; i <= n; i ++ ) {
		for (int j = 1; j <= m; j ++ ) {
			cin >> a[i][j];
		}
	}
	for (int i = 1; i <= sqrt(a[1][1]); i ++ ) {
		if (a[1][1] % i == 0) {
			q.push(i); q.push(a[1][1] / i);
		}
	} // 处理因数 
	while (!q.empty()) {
		int x = q.top(); q.pop();
		if (check(x)) { // 检验 
			cout << x << "\n";
			return;
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T --) solve();
}

题解：CF1955G GCD on a grid

文章操作

题目大意

思路简述

代码实现

相关推荐

评论

题解：CF1955G GCD on a grid