洛谷P2216 [HAOI2007]理想的正方形 题解

洛谷P2216 [HAOI2007]理想的正方形 题解

题目链接：P2216 [HAOI2007]理想的正方形

题意： 有一个 a × b a \times b a×b 的整数组成的矩阵，现请你从中找出一个 n × n n \times n n×n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

去年集训写过这题，也是去年集训唯一过了的（那个数据水

当时的解法稍微改了一下也可以过，放在本文最后

正解：单调队列

考虑先对每一行跑一次单调队列

构造一个 m × ( n − k + 1 ) m \times (n-k+1) m×(n−k+1) 的矩阵（设 n n n 行 m m m 列）

再交换一下行列，跑出一个 ( m − k + 1 ) × ( n − k + 1 ) (m-k+1)\times (n-k+1) (m−k+1)×(n−k+1) 的矩阵

然后就直接枚举就好了，其实没啥难的

时间复杂度 O ( n 2 ) O(n^2) O(n2)

代码：

#include 
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e3+15)
int st,en,q[N];
int n,m,k,in[N][N],a[N][N],b[N][N],mn[N][N],mx[N][N];
void solve1(int *num,int rowid,int n,int len,int f)
{
    st=en=0;
    for(int i=1; i<=n; i++)
    {
        if(f==1)while(st<en&&num[i]<num[q[en]])--en;
        if(f==2)while(st<en&&num[i]>num[q[en]])--en;
        q[++en]=i;
        while(st<en&&q[st+1]+len<=i)++st;
        if(i>=len&&f==1)a[i-len+1][rowid]=num[q[st+1]];
        if(i>=len&&f==2)b[i-len+1][rowid]=num[q[st+1]];
    }
}
void solve2(int *num,int rowid,int n,int len,int f)
{
    st=en=0;
    for(int i=1; i<=n; i++)
    {
        if(f==1)while(st<en&&num[i]<num[q[en]])--en;
        if(f==2)while(st<en&&num[i]>num[q[en]])--en;
        q[++en]=i;
        while(st<en&&q[st+1]+len<=i)++st;
        if(i>=len&&f==1)mn[i-len+1][rowid]=num[q[st+1]];
        if(i>=len&&f==2)mx[i-len+1][rowid]=num[q[st+1]];
    }
}
signed main()
{
    read(n);read(m);read(k);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            read(in[i][j]);
    for(int i=1; i<=n; i++)
        solve1(in[i],i,m,k,1),solve1(in[i],i,m,k,2);
    for(int i=1; i<=m-k+1; i++)
        solve2(a[i],i,n,k,1),solve2(b[i],i,n,k,2);
    int ans=INF;
    for(int i=1; i<=n-k+1; i++)
        for(int j=1; j<=m-k+1; j++)
            ans=min(ans,mx[i][j]-mn[i][j]);
    printf("%lld\n",ans);
    return 0;
}

这里是奇怪的解法

构建一个二维的st表，和上面思路差不多

时间复杂度 O ( n 2 log ⁡ n ) O(n^2\log n) O(n2logn) ，也可以过

代码：

#include 
using namespace std;
//#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define MAXN (int)(1e3+5)
int n,m,k,N,M;
int MX[MAXN][MAXN];
int MN[MAXN][MAXN];
int stmx[MAXN][MAXN][11];
int stmn[MAXN][MAXN][11];
ll ans=INF;
void change1(int x,int u,int v)
{
    stmx[x][u][0]=v;
    stmn[x][u][0]=v;
    for(int i=1; u-(1<<(i-1))>=1; i++)
    {
        stmx[x][u][i]=max(stmx[x][u][i-1],stmx[x][u-(1<<(i-1))][i-1]);
        stmn[x][u][i]=min(stmn[x][u][i-1],stmn[x][u-(1<<(i-1))][i-1]);
    }
}
void change2(int x,int u)
{
    stmx[x][u][0]=MX[x][u];
    stmn[x][u][0]=MN[x][u];
    for(int i=1; u-(1<<(i-1))>=1; i++)
    {
        stmx[x][u][i]=max(stmx[x][u][i-1],stmx[x][u-(1<<(i-1))][i-1]);
        stmn[x][u][i]=min(stmn[x][u][i-1],stmn[x][u-(1<<(i-1))][i-1]);
    }
}
int qrymx(int x,int l,int r)
{
    int k=(double)log(r-l+1)/log(2);
    return max(stmx[x][l+(1<<k)-1][k],stmx[x][r][k]);
}   
int qrymn(int x,int l,int r)
{
    int k=(double)log(r-l+1)/log(2);
    return min(stmn[x][l+(1<<k)-1][k],stmn[x][r][k]);
}
int qrymx(int x,int l)
{
    int r=l+k-1;
    int p=(double)log(r-l+1)/log(2);
    return max(stmx[x][l+(1<<p)-1][p],stmx[x][r][p]);
}   
int qrymn(int x,int l)
{
    int r=l+k-1;
    int p=(double)log(r-l+1)/log(2);
    return min(stmn[x][l+(1<<p)-1][p],stmn[x][r][p]);
}
signed main()
{
    read(n);read(m);read(k);
    for(int i=1; i<=n; i++)
        for(int j=1,x; j<=m; j++)
        {
            read(x);
            change1(i,j,x);
        }
    for(int j=1; j<=m-k+1; j++)
        for(int i=1; i<=n; i++)
            MX[j][i]=qrymx(i,j,j+k-1),
            MN[j][i]=qrymn(i,j,j+k-1);

    for(int i=1; i<=m-k+1; i++)
        for(int j=1; j<=n; j++)
            change2(i,j);

    for(int i=1; i<=m-k+1; i++)
        for(int j=1; j<=n-k+1; j++)
        ans=min(ans,(ll)qrymx(i,j)-qrymn(i,j));
    printf("%lld\n",ans);
    return 0;
}

转载请说明出处