闲话

老师在 NOIP 模拟赛中把这题放到 T2 的位置，话说真的合适吗。考完后瞅了眼题解区。好像和没有我很像的。个人感觉自己的想法很好理解。

做法

对于 $m = 1$，很简单，怎么做都有。所以我们现在只对 $m = 2$ 进行研究。

首先看到求最大的 $k$，不难想到二分答案。但是 check 函数怎么写呢？我想到了如下方法：

记 $x$ 为二分的长度，同时求出所有长度为 $x$ 的连续 . 段，记为 $ans$，如果有重合也都算上。随后对每一段长度为 $x$ 的连续 . 段所在对应位置都加上 $1$。读者可以按照如下图片进行理解。

然而这有什么用呢？显然每个位置上的数，代表了这个点被几段连续段覆盖了。我们找到每个位置上的数的最大值，记为 $maxn$，如果 $maxn = ans$，则说明所有的连续段都相交于一点，那么显然是不合法的，如果 $maxn < ans$，则说明最多有 $maxn$ 个相交的，我们选一个在 $maxn$ 个相交的段中的，和一个不在 $maxn$ 个相交的段中的即可，所以必然合法。

上述操作可以在 $\varTheta(n^2)$ 的时间复杂度内完成，加上二分就是 $\varTheta(n^2\log{n})$。

代码

#include <bits/stdc++.h>
using namespace std;
#define ui unsigned int
const int N = 1505;
struct node {
	int x, y, v;
};
int n, sum[N][N], cf[N], m;
char ch[N][N];
vector<node> vec[N], vev[N];
bool check(int x) {
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (ui j = 0; j < vec[i].size(); j++) {
			if (vec[i][j].v >= x) {
				for (int k = vec[i][j].x; k <= vec[i][j].y - x + 1; k++) {
					++cf[k]; ++ans;
				}
				for (int k = vec[i][j].x + x; k <= vec[i][j].y + 1; k++) {
					--cf[k];
				}
			}
		}
		for (int j = 1; j <= n; j++) {
			cf[j] += cf[j - 1];
			sum[i][j] += cf[j];
		}
		for (int j = 1; j <= n; j++) cf[j] = 0;
	}
	for (int i = 1; i <= n; i++) {
		for (ui j = 0; j < vev[i].size(); j++) {
			if (vev[i][j].v >= x) {
				for (int k = vev[i][j].x; k <= vev[i][j].y - x + 1; k++) {
					++cf[k]; ++ans;
				}
				for (int k = vev[i][j].x + x; k <= vev[i][j].y + 1; k++) {
					--cf[k];
				}
			}
		}
		for (int j = 1; j <= n; j++) {
			cf[j] += cf[j - 1];
			sum[j][i] += cf[j];
		}
		for (int j = 1; j <= n; j++) cf[j] = 0;
	}
	if (m == 1) {
		if (ans) return true;
		return false;
	}
	bool flag = true;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (sum[i][j] >= ans) flag = false;
			sum[i][j] = 0;
		}
	}
	return flag;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int cnt = 0;
		for (int j = 1; j <= n; j++) {
			cin >> ch[i][j];
			if (ch[i][j] == '.') ++cnt;
			if (ch[i][j] == 'X' && cnt != 0) {
				vec[i].push_back({j - cnt, j - 1, cnt});
				cnt = 0;
			}
		}
		if (cnt > 0) vec[i].push_back({n - cnt + 1, n, cnt});
	}
	for (int i = 1; i <= n; i++) {
		int cnt = 0;
		for (int j = 1; j <= n; j++) {
			if (ch[j][i] == '.') ++cnt;
			if (ch[j][i] == 'X' && cnt != 0) {
				vev[i].push_back({j - cnt, j - 1, cnt});
				cnt = 0;
			}
		}
		if (cnt > 0) vev[i].push_back({n - cnt + 1, n, cnt});
	}
	int l = 1, r = n, mid;
	while (l <= r) {
		mid = l + r >> 1;
		if (check(mid)) l = mid + 1;
		else r= mid - 1;
	}
	cout << l - 1;
	return 0;
}