2024年 9月8号 拼多多机试解题报告 | 珂学家

思路: 0-1 二维前缀和

因为格子的数必须要和v不互质，可以把是否互质的关系，转化为0-1矩阵。

那这题就转化为简单的0-1 二维前缀和模型了。

整个时间复杂度为$O(h\ast w\ast q)$

#include <bits/stdc++.h>using namespace std;int solve(vector<vector<int>> &g, int v, int y, int x) {int h = g.size(), w = g[0].size();vector<vector<int>> pre(h + 1, vector<int>(w + 1, 0));// 1. 构建二维前缀和for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {int gv = __gcd(g[i][j], v);gv = gv > 1 ? 1 : 0;pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j] + gv;}}// 2. 统计结果int ans = 0;for (int i = 0; i + y <= h; i++) {for (int j = 0; j + x <= w; j++) {// i, j, i + y - 1, j + w - 1// int z = pre[i + y][j + x] - pre[i][j + x] - pre[i + y][j] + pre[i][j]; //cout << "zzzz " << z << " expect " << (y * x) << endl;if (z == y * x) {ans++;}}}return ans;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t;cin >> t;while (t-- > 0) {int h, w, q;cin >> h >> w >> q;vector<vector<int>> g(h, vector<int>(w));for (int i = 0; i < h; i++) {for (int j = 0; j< w; j++) {cin >> g[i][j];}}while (q-- > 0) {int h1, w1;int v;cin >> h1 >> w1 >> v;int r = solve(g, v, h1, w1);cout << r << endl;}}return 0;
}