首页 > 代码库 > codeforces 713D D. Animals and Puzzle 二分+二维rmq
codeforces 713D D. Animals and Puzzle 二分+二维rmq
题目链接
给一个01矩阵， 然后每个询问给出两个坐标（x1, y1）, （x2, y2）。 问你这个范围内的最大全1正方形的边长是多少。
我们dp算出以i, j为右下角的正方形边长最大值。 然后用二维st表预处理出所有的最大值。 对于每个询问， 我们二分一个值mid， 查询(x1 + mid -1, y1 + mid -1), (x2, y2)这个范围内的最大值是否大于mid 。如果大于的话就说明在(x1, y1), （x2, y2）范围内存在一个边长为mid的正方形。
#include <bits/stdc++.h>using namespace std;#define pb(x) push_back(x)#define ll long long#define mk(x, y) make_pair(x, y)#define lson l, m, rt<<1#define mem(a) memset(a, 0, sizeof(a))#define rson m+1, r, rt<<1|1#define mem1(a) memset(a, -1, sizeof(a))#define mem2(a) memset(a, 0x3f, sizeof(a))#define rep(i, n, a) for(int i = a; i<n; i++)#define fi first#define se secondtypedef complex <double> cmx;typedef pair<int, int> pll;const double PI = acos(-1.0);const double eps = 1e-8;const int mod = 1e9+7;const int inf = 1061109567;const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };int dp[1001][1001][11][11], mm[1005];void initRmq(int n, int m){ mm[0] = -1; for(int i = 1; i <= max(n, m); i++) { mm[i] = ((i&(i-1)) == 0) ? mm[i-1] + 1 : mm[i-1]; } for (int ii = 0; ii <= mm[n]; ii ++) { for (int jj = 0; jj <= mm[m]; jj ++) { if (ii + jj) { for (int i = 1; i + (1<<ii) - 1 <= n; i ++) { for(int j = 1; j + (1<<jj) - 1 <= m; j ++) { if (ii) { dp[i][j][ii][jj] = max(dp[i][j][ii-1][jj], dp[i+(1<<(ii-1))][j][ii-1][jj]); } else { dp[i][j][ii][jj] = max(dp[i][j][ii][jj-1], dp[i][j+(1<<(jj-1))][ii][jj-1]); } } } } } }}int rmq(int x1, int y1, int x2, int y2){ int k1 = mm[x2-x1+1]; int k2 = mm[y2-y1+1]; x2 = x2 - (1<<k1) + 1; y2 = y2 - (1<<k2) + 1; return max(max(dp[x1][y1][k1][k2], dp[x1][y2][k1][k2]), max((dp[x2][y1][k1][k2]), dp[x2][y2][k1][k2]));}int main(){ int n, m, x, q, x1, y1, x2, y2; cin>>n>>m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%d", &x); if (x) dp[i][j][0][0] = min(min(dp[i-1][j][0][0], dp[i][j-1][0][0]), dp[i-1][j-1][0][0]) + 1; } } initRmq(n, m); cin>>q; while (q--) { scanf("%d%d%d%d", &x1, &y1, &x2, &y2); int l = 0, r = min(x2 - x1, y2 - y1) + 1; int ans; while (l <= r) { int mid = l + r >> 1; if (rmq(x1 + mid - 1, y1 + mid - 1, x2, y2) >= mid) { ans = mid; l = mid + 1; } else { r = mid - 1; } } printf("%d\n", ans); } return 0;}
codeforces 713D D. Animals and Puzzle 二分+二维rmq
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。