专栏文章

题解：CF713D Animals and Puzzle

GGrace2022
CF713D题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min9zr88
此快照首次捕获于
2025/12/01 22:59
3 个月前
此快照最后确认于
2025/12/01 22:59
3 个月前
查看原文

题意

给定一个 n×mn \times m 的 01 矩阵 aa，给定 qq 个询问，每次给出一个询问矩形的左上角 (x1,y1)(x1, y1) 和右下角 (x2,y2)(x2, y2)，问这个矩形内的最大全 1 正方形的边长是多少。1≤n,m≤10001 \le n,m \le 1000，1≤q≤1061 \le q \le 10^6。

思路

首先考虑暴力，我们希望枚举询问矩形里的每个点，找到这一个点作为右下角的最大正方形（需要特判一下边界）。而每一个点对应的最大正方形边长也可以暴力预处理。时间复杂度 O(m2n+nmq)\mathcal{O}(m^2n + nmq)。
暴力代码
暴力代码的预处理是把每个点作为右上角的。
CPP
#include<bits/stdc++.h>
using namespace std;
template<typename T> inline void read(T &x){
	T s = 0; int st = 1; char c = getchar();
	while(c < '0' || c > '9'){(c == '-') && (st = -1); c = getchar();}
	while(c >= '0' && c <= '9'){s = (s << 3) +(s << 1) + (c ^ 48); c = getchar();}
	x = s * st;
}
template<typename T> inline void write(T x){
	if(x <0) x= -x, putchar('-');
	if(x > 9) write(x / 10);
	putchar(x % 10 + 48);
}
#define LL long long
#define PII pair<int, int>
#define x1 orjsodfjdsofi
#define x2 dsoasgsapofj
#define y1 dlfzgjzdroier
#define y2 erogxlfigures
const int N = 1e3 + 5;
bool a[N][N];
int sum[N][N], sq[N][N];
inline int get1(int x1, int y1, int x2, int y2){
	return sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
}
int main(){
	int n, m, q;
	read(n), read(m);
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			read(a[i][j]);
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
		}
	}
	for(int i = 1; i <= m; ++i){
		int l = 0, r = 0;
		for(int j = 1; j <= n; ++j){
			if(a[j][i]){
				if(l == 0) l = r = j;
				else r = j;
			}
			else l = r = 0;
			int tmp = r - l + 1;
			if(i + tmp - 1 > m) tmp = m - i + 1;
			if(j - tmp + 1 < 0) tmp = j;
			while(tmp > 0 && get1(j - tmp + 1, i, j, i + tmp - 1) < tmp * tmp){
				--tmp;
			}
			sq[j][i] = tmp;
		}
	} 
	read(q);
	while(q--){
		int x1, x2, y1, y2, ans = 0;
		read(x1), read(y1), read(x2), read(y2);
		for(int i = x1; i <= x2; ++i){
			for(int j = y1; j <= y2; ++j){
				ans = max(ans, min({sq[i][j], i - x1 + 1, y2 - j + 1}));
			}
		}
		write(ans);
		putchar('\n');
	}
	return 0;
}
时间复杂度式子的每一项都需要优化。
预处理可以通过递推优化成 O(nm)\mathcal{O}(nm)，设 fi,jf_{i, j} 表示以 (i,j)(i, j) 为右下角的最大正方形边长。这个正方形可以通过 (i−1,j−1)(i - 1, j - 1) 的正方形边长加一拓展而来。但是，我们得保证第 ii 行和第 jj 列对应边上点都是 1。所以在 ai,ja_{i, j} 为 1 时，有转移方程：
fi,j←min⁡(fi−1,j−1,fi,j−1,fi−1,j)+1f_{i, j} \gets \min(f_{i - 1, j - 1}, f_{i, j - 1}, f_{i - 1, j})+1
当 ai,ja_{i, j} 为 0 时，不存在合法正方形，所以有：
fi,j←0f_{i, j} \gets 0
预处理部分优化完成，现在需要优化查询部分。
我们发现，对于一个合法边长 ansans，所有边长 x≤ansx \le ans 的均合法，x>ansx \gt ans 的需要再判断。这个过程熟悉吗？二分答案。由于答案具有单调性，我们通过二分答案优化查询时间复杂度至 O(qlog⁡min⁡(n,m))\mathcal{O}(q\log\min(n,m))，把最值转化成判定性问题。
考虑二分答案的“check”函数。一个合法边长 midmid 合法，当且仅当左上角为 (x1+mid−1,y1+mid−1)(x1 + mid - 1, y1 + mid - 1)，右下角为 (x2,y2)(x2, y2) 的矩形内部的“右下角”，所组成的正方形的最大边长 ≥mid\ge mid 即可。可能有同学对边界条件有疑惑，其实满足在 (x1+mid−1,y1+mid−1)(x1 + mid - 1, y1 + mid - 1) 右下的“右下角”，如果所对应最大边长 ff 值比 midmid 大可以通过 (x1,y1)(x1, y1) 的边界“截”到 midmid 这么长，说明 midmid 就是合法的。
问题转化成了求 ff 数组上左上角为 (x1+mid−1,y1+mid−1)(x1 + mid - 1, y1 + mid - 1)，右下角为 (x2,y2)(x2, y2) 的矩形的最大值。这里用二维 st 表即可。
一维 st 表是通过两个区间并求得的，二维 st 表就可以通过四个矩形并求。查询同理。

代码

注意 st 表部分容易出错，包括哪些地方有没有 -1 之类的，要仔细。
CPP
#include<bits/stdc++.h>
using namespace std;
template<typename T> inline void read(T &x){
	T s = 0; int st = 1; char c = getchar();
	while(c < '0' || c > '9'){(c == '-') && (st = -1); c = getchar();}
	while(c >= '0' && c <= '9'){s = (s << 3) +(s << 1) + (c ^ 48); c = getchar();}
	x = s * st;
}
template<typename T> inline void write(T x){
	if(x <0) x= -x, putchar('-');
	if(x > 9) write(x / 10);
	putchar(x % 10 + 48);
}
#define LL long long
#define PII pair<int, int>
#define x1 orjsodfjdsofi
#define x2 dsoasgsapofj
#define y1 dlfzgjzdroier
#define y2 erogxlfigures
const int N = 1e3 + 1;
int n, m, q;
int f[11][11][N][N], lg[N];
inline void init(){
	for(int k = 1; k <= lg[n]; ++k){
		for(int i = 1; i + (1 << k) - 1 <= n; ++i){
			for(int j = 1; j <= m; ++j){
				f[k][0][i][j] = max(f[k - 1][0][i][j], f[k - 1][0][i + (1 << k - 1)][j]);
			}
		}
	}
	for(int l = 1; l <= lg[m]; ++l){
		for(int i = 1; i <= n; ++i){
			for(int j = 1; j + (1 << l) - 1 <= m; ++j){
				f[0][l][i][j] = max(f[0][l - 1][i][j], f[0][l - 1][i][j + (1 << l - 1)]);
			}
		}
	}
	for(int k = 1; k <= lg[n]; ++k){
		for(int l = 1; l <= lg[m]; ++l){
			for(int i = 1; i + (1 << k) - 1 <= n; ++i){
				for(int j = 1; j + (1 << l) - 1 <= m; ++j){
					f[k][l][i][j] = max({f[k - 1][l - 1][i][j], 
						f[k - 1][l - 1][i + (1 << k - 1)][j], 
						f[k - 1][l - 1][i][j + (1 << l - 1)], 
						f[k - 1][l - 1][i + (1 << k - 1)][j + (1 << l - 1)]});
				}
			}
		}
	}
}
inline int get(int x1, int y1, int x2, int y2){//左上角, 右下角 
	int lx = lg[x2 - x1 + 1], ly = lg[y2 - y1 + 1];
	return max({f[lx][ly][x1][y1], 
		f[lx][ly][x1][y2 - (1 << ly) + 1], 
		f[lx][ly][x2 - (1 << lx) + 1][y1], 
		f[lx][ly][x2 - (1 <<lx) + 1][y2 - (1 << ly) + 1]});
}
int main(){
	read(n), read(m);
	for(int i = 2; i <= max(n, m); ++i) lg[i] = lg[i >> 1] + 1;
	for(int i = 1, a; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			read(a);
			if(a){
				f[0][0][i][j] = min({f[0][0][i - 1][j], f[0][0][i][j - 1], f[0][0][i - 1][j - 1]}) + 1;
			}
		}
	}
	init();
	read(q);
	while(q--){
		int x1, x2, y1, y2, l, r, mid, ans = 0;
		read(x1), read(y1), read(x2), read(y2);
		l = 1, r = min(y2 - y1 + 1, x2 - x1 + 1);
		while(l <= r){
			mid = l + r >> 1;
			if(get(x1 + mid - 1, y1 + mid - 1, x2, y2) >= mid){
				ans = mid;
				l = mid + 1;
			}
			else{
				r = mid - 1;
			}
		}
		write(ans); putchar('\n');
	}
	return 0;
}
/*
3 4
1 1 0 1
0 1 1 0
0 1 1 0
5
1 1 2 3
2 1 3 2
3 2 3 4
1 1 3 4 
1 2 3 4
*/
讲得有点抽象抱歉。这是今天学校 s 组%你赛 T3，赛时一直在想扫描线树套树之类的东西，最后只把暴力写了拿了 40 分非常遗憾，觉得题目还是有点价值于是克服倦意写了这篇题解。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...