<span>codeforces713D Animals and Puzzle(二维倍增)</span>

引自: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_pair
template<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;
}

 

全部评论

相关推荐

01-23 14:54
同济大学 Java
热爱敲代码的程序媛:给你提几点【专业技能】这个模块里面可优化的地方:1.【具备JVM调优经验】可以去b站上搜一下JVM调优的视频,估计一两个小时凭你的学习能力就能掌握JVM调优的实践方面的技能。2.【MySql优化】MySql这一栏,你去b站或者找个博客看看MySql优化,学一下,如果你本身比较熟悉MySql语句的话,那基本半天时间凭你的学习能力MySql语句优化方面的技能你也能掌握个差不多。以上1,2两点主要是因为我看你专业技能大部分都说的是偏理论,没有写应用。再就是最后,你结合你的项目,想一想你的项目中哪些sql语句是可以用MySql优化的,到时候你面试的时候也好结合着说一下。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务