当前位置：首页 > news >正文

2025 暑期 mx 集训 7.19

news 2025/11/7 23:25:39

T1

https://www.mxoj.net/problem/P110016?contestId=49

题意

给你一个 \(n \times n\) 的网格，你每一步可以选择下或者右，从 \((1,1)\) 走到 \((n,n)\)，走过的路径把整个网格划分成 \(A,B\) 两部分。

求 \(\min( \max_{x\in A, y\in B} \left | x - y\right |)\)。

\(n\leq 500\)。

Solution

考虑整个网格的最大值和最小值一定都选在同一个里了。

不妨设为 \(A\)，那剩下的是 \(B\)，此时是求 \(\min(\max_{y\in B}( \left | y - mx\right |, \left | y - mn\right |))\)。

然后考虑这个 \(B\) 里一定包含角上的元素，然后其余元素全删掉，因为这样起码不会更劣，反而可能更优。

所以就是 \(A\) 取 \((1, n)\) 求一下，\(B\) 取 \((n, 1)\) 求一下，两者取 \(\min\) 即可。

Code

#include <bits/stdc++.h>using namespace std;const int N = 5e2 + 10, inf = 0x3f3f3f3f;int n, a[N][N];int main()
{cin.tie(0)->ios::sync_with_stdio(false);cin >> n;for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> a[i][j];int mn1 = inf, mx1 = 0, mn2 = inf, mx2 = 0;for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {if (i != 1 || j != n) mn1 = min(mn1, a[i][j]), mx1 = max(mx1, a[i][j]);if (i != n || j != 1) mn2 = min(mn2, a[i][j]), mx2 = max(mx2, a[i][j]);}cout << min(max(abs(a[1][n] - mn1), abs(a[1][n] - mx1)), max(abs(a[n][1] - mn2), abs(a[n][1] - mx2)));return 0;
}

T2

https://www.mxoj.net/problem/P110017?contestId=49

题意

给你一个 \(n\times n\) 的网格，有些格子能涂色，有些不能涂色。

你需要求出一个最大的 \(l\)，使得可以找到两个 \(1\times l\) 或 \(l \times 1\) 的连续格子可以被涂色。他们不能相交。

\(n\leq 1500\)。

Solution

首先考虑枚举其中一个，然后预处理另一个。

我们可以预处理：前 \(i\) 行最大的 \(l\)，后 \(i\) 行最大的 \(l\)，前 \(i\) 列最大的 \(l\)，后 \(i\) 列最大的 \(l\)。

这些可以 \(n^2\) 预处理出来。

然后可以二分答案直接判断即可。具体可看代码。

Code

#include <bits/stdc++.h>using namespace std;const int N = 1.5e3 + 10, inf = 0x3f3f3f3f;int n, a[N][N], s[N][N], l[N][2], r[N][2];void clear() { for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) s[i][j] = 0; }bool chk(int x)
{for (int i = 1; i <= n; i++) {int c = 0;for (int j = 1, k = 1; j + x - 1 <= n; j++) {while (k <= j + x - 1) {c += !a[i][k];k++;}// (i, j) -> (i, j + x - 1)if (!c) {if (l[i - 1][0] >= x || l[i + 1][1] >= x || r[j - 1][0] >= x || r[j + x][1] >= x) return 1;}c -= !a[i][j];}}for (int j = 1; j <= n; j++) {int c = 0;for (int i = 1, k = 1; i + x - 1 <= n; i++) {while (k <= i + x - 1) {c += !a[k][j];k++;}// (i, j) -> (i + x - 1, j)if (!c) {if (l[i - 1][0] >= x || l[i + x][1] >= x || r[j - 1][0] >= x || r[j + 1][1] >= x) return 1;}c -= !a[i][j];}}return 0;
}void solve()
{cin >> n;for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {char c; cin >> c;a[i][j] = (c == '.');}clear();for (int i = 1; i <= n; i++) {int c = 0;l[i][0] = l[i - 1][0];for (int j = 1; j <= n; j++) {if (a[i][j]) {c++;s[i][j] = s[i - 1][j] + 1;l[i][0] = max(l[i][0], s[i][j]);} else l[i][0] = max(l[i][0], c), c = 0;}l[i][0] = max(l[i][0], c);}clear();for (int i = n; i >= 1; i--) {int c = 0;l[i][1] = l[i + 1][1];for (int j = 1; j <= n; j++) {if (a[i][j]) {c++;s[i][j] = s[i + 1][j] + 1;l[i][1] = max(l[i][1], s[i][j]);} else l[i][1] = max(l[i][1], c), c = 0;}l[i][1] = max(l[i][1], c);}clear();for (int j = 1; j <= n; j++) {int c = 0;r[j][0] = r[j - 1][0];for (int i = 1; i <= n; i++) {if (a[i][j]) {c++;s[i][j] = s[i][j - 1] + 1;r[j][0] = max(r[j][0], s[i][j]);} else r[j][0] = max(r[j][0], c), c = 0;}r[j][0] = max(r[j][0], c);}clear();for (int j = n; j >= 1; j--) {int c = 0;r[j][1] = r[j + 1][1];for (int i = 1; i <= n; i++) {if (a[i][j]) {c++;s[i][j] = s[i][j + 1] + 1;r[j][1] = max(r[j][1], s[i][j]);} else r[j][1] = max(r[j][1], c), c = 0;}r[j][1] = max(r[j][1], c);}int l = 0, r = n, res = 0;while (l <= r) {int mid = (l + r) / 2;if (chk(mid)) l = (res = mid) + 1;else r = mid - 1;}cout << res << "\n";
}int main()
{cin.tie(0)->ios::sync_with_stdio(false);int _; cin >> _;while (_--) solve();return 0;
}