云建站规划图,自己做的网站打开显示很慢,沈阳招聘网官网,巴中城乡建设官方网站题目描述 输入 输出 样例输入 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) 考虑… 题目描述 输入 输出 样例输入 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) 显然ansmin(f[x][y],x−x11,y−y11) 二分答案mid如果矩阵(x1mid-1,y1mid-1,x2,y2)的f最大值大于或等于mid那么mid合法。 静态子矩阵求最大值考虑使用二维RMQ。 总的时间复杂度为O(T∗log(n2))。 代码 #includeiostream
#includestdio.h
#includemath.h
#includestring.h
#includealgorithm
#define ll long long
#define ln(x,y) int(log(x)/log(y))
#define sqr(x) ((x)*(x))
using namespace std;
const char* finsquare.in;
const char* foutsquare.out;
const int inf0x7fffffff;
const int maxn1007,maxk10;
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 i0,j0;while (sx(1(i1))-1tx) i;while (sy(1(j1))-1ty) j;return max(max(g[i][j][sx][sy],g[i][j][tx-(1i)1][sy]),max(g[i][j][sx][ty-(1j)1],g[i][j][tx-(1i)1][ty-(1j)1]));
}
int main(){freopen(fin,r,stdin);freopen(fout,w,stdout);scanf(%d%d,n,m);for (i1;in;i){for (j1;jm;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 (i0;(1i)n;i){for (j0;(1j)m;j){if (i0 j0) continue;for (k1;k(1i)-1n;k)for (l1;l(1j)-1m;l){if (j0) 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 {lef1;rigmin(k-i1,l-j1);int l1lef,r1rig;while (lefrig){mid(lefrig)/2;if (getmax(imid-1,jmid-1,k,l)mid) lefmid;else rigmid-1;if (l1lef r1rig) break;else l1lef,r1rig;}if (getmax(irig-1,jrig-1,k,l)rig) lefrig;printf(%d\n,lef);}}return 0;
} 启发 静态子矩阵求和可以使用RMQ。 这类型无修改离线多次询问的问题可以这样考虑 1.由询问次数决定时间复杂度 2.考虑一次询问如何在规定复杂度内求出答案。 3.考虑预处理在2中所需要的信息。 这题类似于妮厨的愤怒那样处理三元取最值。 转载于:https://www.cnblogs.com/hiweibolu/p/6714872.html
