首页 > 代码库 > codeforces713D Animals and Puzzle（二维倍增）
codeforces713D Animals and Puzzle（二维倍增）
引自：http://www.cnblogs.com/qscqesze/p/5929117.html
题意：
给你一个01矩阵，然后Q次询问，每次询问一个矩形区域中，最大的全一正方形的边长是多少。
思路：
首先考虑Dp，dp[i][j]表示以(i,j)位置为右下角，最大的正方形边长是多少，显然dp[i][j]=min(dp[i-1][j],dp[j][i-1],dp[i-1][j-1])+1
然后我们做出这个dp之后，我们怎么做呢？
直接二分答案，假设我们二分的答案为mid，显然在这个矩形区域的左上角的点是废点，然后查询剩下的点的最大值，是否大于等于m就行了。
这个可以用二维线段树，也可以用二维倍增去做就好了。
/* ***********************************************Author :devil************************************************ */#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <vector>#include <queue>#include <set>#include <stack>#include <map>#include <string>#include <cmath>#include <stdlib.h>#define LL long long#define rep(i,a,b) for(int i=a;i<=b;i++)#define dep(i,a,b) for(int i=a;i>=b;i--)#define ou(a) printf("%d\n",a)#define pb push_back#define mkp make_pairtemplate<class T>inline void rd(T &x){ char c=getchar(); x=0; while(!isdigit(c))c=getchar(); while(isdigit(c)) { x=x*10+c-‘0‘; c=getchar(); }}#define IN freopen("in.txt","r",stdin);#define OUT freopen("out.txt","w",stdout);using namespace std;const int inf=0x3f3f3f3f;const int N=1e3+10;const int M=10;int f[M][M][N][N],lg[N],n,m,q,x,x1,x2,y1,y2;void build(){ rep(i,2,N) lg[i]=lg[i/2]+1; for(int i=1;i<=n;i++) for(int k2=1;(1<<k2)<=m;k2++) for(int j=1;j<=m-(1<<k2)+1;j++) f[0][k2][i][j]=max(f[0][k2-1][i][j],f[0][k2-1][i][j+(1<<(k2-1))]); for(int k1=1;(1<<k1)<=n;k1++) for(int i=1;i<=n-(1<<k1)+1;i++) for(int k2=0;(1<<k2)<=m;k2++) for(int j=1;j<=m-(1<<k2)+1;j++) f[k1][k2][i][j]=max(f[k1-1][k2][i][j],f[k1-1][k2][i+(1<<(k1-1))][j]);}int query(int x1,int y1,int x2,int y2){ int k1=lg[x2-x1+1],k2=lg[y2-y1+1]; x2=x2-(1<<k1)+1; y2=y2-(1<<k2)+1; return max(max(f[k1][k2][x1][y1],f[k1][k2][x1][y2]),max(f[k1][k2][x2][y1],f[k1][k2][x2][y2]));}int main(){ #ifndef ONLINE_JUDGE //IN #endif rd(n),rd(m); rep(i,1,n)rep(j,1,m) { rd(x); if(x) f[0][0][i][j]=min(f[0][0][i-1][j],min(f[0][0][i-1][j-1],f[0][0][i][j-1]))+1; } build(); rd(q); while(q--) { rd(x1),rd(y1),rd(x2),rd(y2); int l=0,r=min(x2-x1,y2-y1)+1,ans=0; while(l<=r) { int mid=l+r>>1; if(query(x1+mid-1,y1+mid-1,x2,y2)>=mid) l=mid+1,ans=mid; else r=mid-1; } ou(ans); } return 0;}
codeforces713D Animals and Puzzle（二维倍增）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。