Good Start/Smilo and Minecraft

好的开始

 

 

 

思路 ：

两种情况可以铺满：

当两个瓦片在水平方向上的距离满足以下条件时，可以铺满：

距离足够大：x2 - x1 - a >= 0，即第二个瓦片的左边缘与第一个瓦片的右边缘之间有足够的空间放置至少一个完整的瓦片。

距离是瓦片宽度的整数倍：(x2 - x1 - a) % a == 0，确保两个瓦片之间的间隙可以被整数个瓦片填满。

当两个瓦片在垂直方向上的距离满足类似条件时，也可以铺满：

y 坐标关系：

如果y1 <= y2，计算第二个瓦片相对于第一个瓦片的垂直距离y2 - y1。

如果y1 > y2，计算第一个瓦片相对于第二个瓦片的垂直距离y1 - y2。

距离条件：垂直距离必须足够大且是瓦片高度的整数倍，确保两个瓦片之间的间隙可以被整数个瓦片填满。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int t, a, b, w,h;
long long x1o, x2o, y1o, y2o;
int main(){ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin与cout绑定cin >> t;while (t--) {cin >> w >> h >> a >> b;cin >> x1o >> y1o >> x2o >> y2o;if (x1o > x2o) {int x = x1o;x1o = x2o, x2o = x;int y = y1o;y1o = y2o, y2o = y;}if (y1o <= y2o) {if (((x2o - x1o - a) >= 0 && (x2o - x1o - a) % a == 0) || ((y2o - y1o - b) >= 0 && (y2o - y1o - b) % b == 0)) {cout << "Yes" << endl;}else {cout << "No" << endl;}}else {if (((x2o - x1o - a) >= 0 && (x2o - x1o - a) % a == 0) || ((y1o - y2o - b)>=0&&(y1o - y2o - b) % b == 0)) {cout << "Yes" << endl;}else {cout << "No" << endl;}}}return 0;
}

 

 Smilo and Minecraft

 

 

思路： 

问题分析：

炸药只能放在空单元格（'.'）中。

爆炸区域是以放置点为中心的边长为 2k+1 的正方形。

边界上的金矿会被收集，内部的金矿会消失。

我们需要计算每个可能放置点的收益，并找出最大值。

暴力解法的问题：

对于每个空单元格，直接检查其爆炸区域内的所有金矿会导致时间复杂度为 O (nmk²)，对于较大的 k 值会超时。

优化思路：

使用前缀和数组快速计算爆炸区域内的金矿数量。

总收益 = 总金矿数 - 爆炸区域内部的金矿数。

前缀和数组的应用：

构建二维前缀和数组 c，其中 c [i][j] 表示从 (1,1) 到 (i,j) 的矩形区域内的金矿数量。

利用前缀和数组，我们可以在 O (1) 时间内计算任意矩形区域内的金矿数量。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int t, n, m,k;
char a[502][502];
int c[502][502];
int sum = 0;
struct {int x, y;
}b[250001];
int z;
int main() {ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin与cout绑定cin >> t;while (t--) {z = 0, sum = 0;int sum0 = 0;cin >> n >> m >> k;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {c[i][j] = 0;cin >> a[i][j];if (a[i][j] == '.') {b[z].x = i;b[z].y = j;z++;}else if (a[i][j] == 'g') {sum++;c[i][j] = 1;}c[i][j] += c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1];}}for (int l = 0; l < z; l++) {int oo = 0;int qq = b[l].x - k + 1 > 0 ? b[l].x - k + 1 : 1;int pp = b[l].y - k + 1 > 0 ? b[l].y - k + 1 : 1;int q = b[l].x + k - 1 <= n ? b[l].x + k - 1 : n;int p = b[l].y + k - 1 <= m ? b[l].y + k - 1 : m;oo = c[q][p] - c[q][pp - 1] - c[qq - 1][p] + c[qq - 1][pp - 1];if (sum0 < sum - oo) {sum0 = sum - oo;}}cout << sum0 << endl;}return 0;
}