【JZOJ4817】【NOIP2016提高A组五校联考4】square
题目大意：给你一个\(n*m\)的矩阵，矩阵上有一些点是障碍，有\(T\)次询问，每次给你一个矩形\(x1,y1,x2,y2\)，你要在这个矩形内找一个最大正方形使得正方形内不包含障碍。
\(n,m\leq 1000,T \leq 10^6\)
Solution
假设没有给定矩形的限制，设\(f[i][j]\)表示以\((i,j)\)为右下角最大不包含障碍的正方形，转移如下：
- \((i,j)\)有障碍则\(f[i][j]=0\)
- \((i,j)\)无障碍则\(f[i][j]=min(f[i-1][j],f[i][j-1],f[i-1][j-1])+1\)
现在有了矩形的限制，我们可以二分答案\(mid\)，则若矩形\((x1+mid-1,y1+mid-1)\)到\((x2,y2)\)中\(f\)的最大值大于等于\(mid\)，这个\(mid\)就是合法的了。查询范围的左上角\((x1+mid-1,y1+mid-1)\)相当于保证了最大的正方形不超出矩形范围。
于是用一个二维rmq维护矩阵最大值即可，时空复杂度均为\(O(n^2log^2n)\)。
Tips: 由于没有按题解说的开mx[10][10][N][N]而开了mx[N][N][10][10]，导致程序TLE。这说明多维数组把小的下标开在前面可以显著提高访问速度，涨知识了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rg register
using namespace std;
const int N=1007;
inline int read(){
int x=0,f=0;
char c=getchar();
for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^'0');
return f?-x:x;
}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
int n,m,T,a[N][N],f[N][N],mx[10][10][N][N],Log[N],two[10];
int x1,y1,x2,y2,l,r,mid,ans;
inline int qrymax(int x1,int y1,int x2,int y2){
int k=Log[x2-x1+1],l=Log[y2-y1+1];
return max(max(mx[k][l][x1][y1],mx[k][l][x2-two[k]+1][y2-two[l]+1]),max(mx[k][l][x1][y2-two[l]+1],mx[k][l][x2-two[k]+1][y1]));
}
int main(){
//freopen("in","r",stdin);
//freopen("square.in","r",stdin);
//freopen("square.out","w",stdout);
Log[1]=0;for(int i=2;i<=1000;++i)Log[i]=Log[i>>1]+1;
for(int i=0;i<=9;++i)two[i]=(1<<i);
n=read(),m=read();
for(rg int i=1;i<=n;++i)for(rg int j=1;j<=m;++j)a[i][j]=read();
for(rg int i=1;i<=n;++i)for(rg int j=1;j<=m;++j){
if(a[i][j])f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1;
else f[i][j]=0;
}
for(rg int i=1;i<=n;++i)for(rg int j=1;j<=m;++j)mx[0][0][i][j]=f[i][j];
for(rg int k=0;k<=Log[n];++k)for(rg int l=0;l<=Log[m];++l){
if(k+l==0)continue;
for(rg int i=1;i+two[k]-1<=n;++i)for(rg int j=1;j+two[l]-1<=m;++j){
if(l==0)mx[k][l][i][j]=max(mx[k-1][l][i][j],mx[k-1][l][i+two[k-1]][j]);
else mx[k][l][i][j]=max(mx[k][l-1][i][j],mx[k][l-1][i][j+two[l-1]]);
}
}
T=read();
while(T--){
x1=read(),y1=read(),x2=read(),y2=read();
l=1,r=min(x2-x1+1,y2-y1+1),ans=0;
while(l<=r){
mid=l+r>>1;
if(qrymax(x1+mid-1,y1+mid-1,x2,y2)>=mid)ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d\n",ans);
}
return 0;
}1、python--数据类型
2、《软件需求十步走》阅读笔记01
3、jsp html5 video实现在线视频播放源码，支持IE6,7,8,10,11，谷歌，火狐等浏览器
4、《用户网络行为画像》读书笔记（一）
5、tomcat监控脚本（监控进程，测试接口，告警动作为发送邮件）