首页 > 代码库 > codeforces 713D Animals and Puzzle
codeforces 713D Animals and Puzzle
题意：
给出n * m 的0/1矩阵，然后q组询问，问询问的矩形中包含的全1正方形的最大边长。
题解：
首先考虑暴力算法，对于每个询问的矩形，在里面暴力找到全1正方形，现在的问题就是怎么找全1正方形，可以递推实现，dp[i][j]表示以(i, j)作为右下角的全一正方形最长边长。
dp[i][j] = min (dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1。
while (T--) {
int x1, y1, x2, y2;
scanf ("%d%d%d%d", &x1, &y1, &x2, &y2);
int ans = 0;
for (int i = x1; i <= x2; ++i) {
for (int j = y1; j <= y2; ++j) {
int len = dp[i][j];
if (i - len + 1 < x1 && j - len + 1 < y1) ans = max (ans, min(i - x1 + 1, j - y1 + 1));
else if (j - len + 1 < y1) ans = max (ans, j - y1 + 1);
else if (i - len + 1 < x1) ans = max (ans, i - x1 + 1);
else ans = max (ans, len);
}
}
cout << ans << endl;
}
现在考虑，对每个询问的两个for循环优化：
那么现在的问题就是维护一个矩形中最大的dp值是多少，二维线段树？不不不，TLE，复杂度(T * (logn)^3)，显然可以用二维ST表
但是会发现有很多情况会越过边界从而不符合条件，可以二分出矩形的全1正方形的边长，根据定义那么问题就等价于在（x1 + mid - 1, y1 + mid -1）到 （x2, y2）中寻找最大的dp值，就直接拿最大值和二分值比较就好了，就可以不用考虑是否越界的问题了。O(∩_∩)O~
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e3 + 100;
int n, m, dp[11][11][N][N], T, lg[N];
void BuildSt () {
lg[1] = 0;
for (int i = 2; i <= 1000; ++i) lg[i] = lg[i >> 1] + 1;
for (int x = 1; x <= n; ++x)
for (int i = 1; i <= 10; ++i)
for (int y = 1; y <= m; ++y)
if (y + (1<<i-1) <= m) dp[0][i][x][y] = max (dp[0][i-1][x][y], dp[0][i-1][x][y+(1<<i-1)]);
for (int i = 1; i <= 10; ++i)
for (int x = 1; x <= n; ++x)
for (int j = 0; j <= 10; ++j)
for (int y = 1; y <= m; ++y)
if (x + (1<<i-1) <= n) dp[i][j][x][y] = max (dp[i-1][j][x][y], dp[i-1][j][x+(1<<i-1)][y]);
}
int query (int x1, int y1, int x2, int y2) {
int lx = lg[x2 - x1 + 1], ly = lg[y2 - y1 + 1];
x2 = x2 - (1 << lx) + 1;
y2 = y2 - (1 << ly) + 1;
return max (max (dp[lx][ly][x1][y1], dp[lx][ly][x1][y2]), max (dp[lx][ly][x2][y1], dp[lx][ly][x2][y2]));
}
int main () {
scanf ("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int x;
scanf ("%d", &x);
if (x == 1)dp[0][0][i][j] = min (dp[0][0][i-1][j], min (dp[0][0][i][j-1], dp[0][0][i-1][j-1])) + 1;
}
}
BuildSt();
scanf ("%d", &T);
while (T--) {
int x1, y1, x2, y2;
scanf ("%d%d%d%d", &x1, &y1, &x2, &y2);
int l = 0, r = min (x2 - x1 + 1, y2 - y1 + 1);
while (l < r) {
int mid = l + r + 1 >> 1;
if (query(x1 + mid - 1, y1 + mid - 1, x2, y2) >= mid) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
return 0;
}
总结：
蒟蒻涨姿势了～学到了二维的ST，还有这道题的边界处理也非常巧妙，而且我不知道下次我能不能想到，总之先记住这个套路吧。。。
codeforces 713D Animals and Puzzle
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。