題目描述

輸入

輸出

樣例輸入

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

樣例輸出

1
1
1
2
2

數據范圍

解法

設f[i][j]為以(i,j)為右下角的正方形的最大邊長。
則f[i][j]=min(f[i?1][j],f[i?1][j?1],f[i][j?1])+1(a[i][j]=1)

---

考慮利用f來求答案。
對于詢問(x1,y1,x2,y2)：
顯然ans=min(f[x][y],x?x1+1,y?y1+1)
二分答案mid，如果矩陣(x1+mid-1,y1+mid-1,x2,y2)的f最大值大于或等于mid，那么mid合法。

---

靜態子矩陣求最大值，考慮使用二維RMQ。

---

總的時間復雜度為O(T?log(n2))。

代碼

#include<iostream> #include<stdio.h> #include<math.h> #include<string.h> #include<algorithm> #define ll long long #define ln(x,y) int(log(x)/log(y)) #define sqr(x) ((x)*(x)) using namespace std; const char* fin="square.in"; const char* fout="square.out"; const int inf=0x7fffffff; const int maxn=1007,maxk=10; int n,m,t,i,j,k,l,lef,mid,rig; int f[maxn][maxn],g[maxk][maxk][maxn][maxn]; int getmax(int sx,int sy,int tx,int ty){int i=0,j=0;while (sx+(1<<(i+1))-1<=tx) i++;while (sy+(1<<(j+1))-1<=ty) j++;return max(max(g[i][j][sx][sy],g[i][j][tx-(1<<i)+1][sy]),max(g[i][j][sx][ty-(1<<j)+1],g[i][j][tx-(1<<i)+1][ty-(1<<j)+1])); } int main(){freopen(fin,"r",stdin);freopen(fout,"w",stdout);scanf("%d%d",&n,&m);for (i=1;i<=n;i++){for (j=1;j<=m;j++){scanf("%d",&k);if (k) f[i][j]=min(f[i][j-1],min(f[i-1][j-1],f[i-1][j]))+1;else f[i][j]=0;g[0][0][i][j]=f[i][j];}}for (i=0;(1<<i)<=n;i++){for (j=0;(1<<j)<=m;j++){if (i==0 && j==0) continue;for (k=1;k+(1<<i)-1<=n;k++)for (l=1;l+(1<<j)-1<=m;l++){if (j==0) g[i][j][k][l]=max(g[i-1][j][k][l],g[i-1][j][k+(1<<(i-1))][l]);else g[i][j][k][l]=max(g[i][j-1][k][l],g[i][j-1][k][l+(1<<(j-1))]);}}}scanf("%d",&t);for (;t;t--){scanf("%d%d%d%d",&i,&j,&k,&l);if (getmax(i,j,k,l)==0) printf("0\n");else {lef=1;rig=min(k-i+1,l-j+1);int l1=lef,r1=rig;while (lef<rig){mid=(lef+rig)/2;if (getmax(i+mid-1,j+mid-1,k,l)>=mid) lef=mid;else rig=mid-1;if (l1==lef && r1==rig) break;else l1=lef,r1=rig;}if (getmax(i+rig-1,j+rig-1,k,l)>=rig) lef=rig;printf("%d\n",lef);}}return 0; }

啟發

靜態子矩陣求和可以使用RMQ。

---

這類型（無修改離線多次詢問）的問題可以這樣考慮：
1.由詢問次數決定時間復雜度；
2.考慮一次詢問如何在規定復雜度內求出答案。
3.考慮預處理在2中所需要的信息。

---

這題類似于妮廚的憤怒，那樣處理三元取最值。

轉載于:https://www.cnblogs.com/hiweibolu/p/6714872.html

總結

以上是生活随笔為你收集整理的【JZOJ4817】【NOIP2016提高A组五校联考4】square的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。