For XeniaF

(☆▽☆)

阅读ByaP1169代码&题解笔记

发布于 2021-07-11 | 分类于 随笔 | 13分钟 | 2488字数

大前言：花了一晚上，被花式吊打。

做法一：(ByaBya)优先队列+并查集

（1）Someting new.Someting\ new.

  • a^=b^=a^=b为交换a,ba,b，不用借助第三个变量
  • pairpair的定义方式为#define P pair<int,int>

（2）思路

  • 正方形的求法o(nmlogn)o(nmlogn)，二分加前缀和（这一部分直接看我自己的代码即可）
  • 矩形首先对于合法的放置方式作处理（是它们都变为00，具体方式可以参见我的代码和AcAc的代码，我们两个实现方式不太一样），统计：f[i][j]f[i][j]表示的是在第ii列中，到jj为止有多少个合法的00；将n∗mn*m个点入队（大根堆），每次截取一个点更新矩形宽的最大面积（我们可以注意到AcAc在入队的时候并没有储存i,ji,j这个具体位置而是仅储存了jj,在合并的时候查看是否可以将这一列与其他列并在一起；如果可以的话将其并在一起。cc数组应该存的是可以并在一起的列的个数）。
  • 在这里可能会向问如果v[j]v[j]和v[j−1]v[j-1]不在同一行呢？这样岂不是不能合并了吗？然而值得注意的是whilewhile是含在外层ii的循环中的，也就是它每一次处理只会考虑一行，其中如果到p[i][j]p[i][j]的时候有22个纵连，到p[i][j−1]p[i][j-1]的时候有33个纵连，那么这期间其实有22个纵连是一定可以合并的。而最终在合并的时候AcAc取得是两列中较小的那一个，这样一定是正确的（不好解释，自己想一下）
  • 特别需要注意的是，正方形也是矩形的一种。
  • AcAc的正方形算法我是在不敢恭维（瑟瑟）

（3）收获

  • 这个题和P1174 打砖块的统计方式较为类似，都是在一列中进行统计，即f[i][j]f[i][j]是由f[i−1][j]f[i-1][j]递推得到的
  • 与P2216 [HAOI2007]理想的正方形计算方式类似，在P2216P2216中是先算横行再算竖行，这里恰好相反
  • 在此题中并查集的功能为合并可以合并在一起的

（4）代码

#include<bits/stdc++.h>
#define P pair<int,int>
#define mp(x,y) make_pair(x,y)
#define F first
#define S second
using namespace std;
const int max_n=2005;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) x=-x,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10^48);
}
inline int mx(int a,int b){return a>b?a:b;}
inline int mn(int a,int b){return a<b?a:b;}

int n,m,a[max_n][max_n],s[max_n][max_n];

inline int sm(int lx,int ly,int rx,int ry){
    return s[rx][ry]-s[lx-1][ry]-s[rx][ly-1]+s[lx-1][ly-1];
}

int p[max_n][max_n];

inline void init(){
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j)
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
    for(register int j=1;j<=m;++j)
        for(register int i=1;i<=n;++i){
            if(!a[i][j]) p[i][j]=p[i-1][j]+1;
            else p[i][j]=0;
        }
}

inline int sc(int l,int r,int ki,int kj){
    int res=1;
    while(l<=r){
        int m=(l+r)/2;
        if(!sm(ki,kj,ki+m-1,kj+m-1)){
            l=m+1;
            res=m;
        }
        else r=m-1;
    }
    return res;
}

priority_queue< P > q;
int f[max_n],c[max_n];
bool v[max_n];

inline int fd(int x){
    if(f[x]==x) return x;
    else return f[x]=fd(f[x]);
}

inline void mg(int a,int b){
    a=fd(a),b=fd(b);
    if(c[a]>c[b]) a^=b^=a^=b;
    c[b]+=c[a];
    f[a]=b;
}

inline P sol(){
    init();
    int res1=1,res2=1;
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j) if(!a[i][j]){
            int l=sc(1,mn(n-i+1,m-j+1),i,j);
            res1=mx(res1,l*l);
        }

    for(register int i=1;i<=n;++i){
        for(register int j=1;j<=m;++j)
            q.push(mp(p[i][j],j)),
            f[j]=j,c[j]=1,v[j]=0;

        while(!q.empty()){
            int l=q.top().F,j=q.top().second;
            q.pop();
            if(l==0) continue;
            v[j]=1;
            if(v[j-1]) mg(j,j-1);
            if(v[j+1]) mg(j,j+1);
            res2=mx(res2,c[fd(j)]*l);
        }
    }

    return mp(res1,res2);
}

inline void clr(){
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j)
            a[i][j]^=1;
    memset(s,0,sizeof(s)),
    memset(p,0,sizeof(q));
}

signed  main(){
    n=read(),m=read();
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j){
            a[i][j]=read();
            if((i&1)==(j&1)) a[i][j]^=1;
        }

    P ans1=sol();
    clr();
    P ans2=sol();

    write(mx(ans1.F,ans2.F)),putchar('\n');
    write(mx(ans1.S,ans2.S)),putchar('\n');
    return 0;
}

做法二：悬线法

（1）方法介绍
其实网上有很多介绍阿这里就说一下自己的理解

  • 用途：解决给定矩阵中满足条件的最大子矩阵

  • 做法：用一条线(横竖貌似都行)左右移动直到不满足约束条件或者到达边界
    （2）本题目做法（部分摘自题解）

  • 定义：
    left[i][j]left[i][j]:代表从(i,j)(i,j)能到达的最左位置

    right[i][j]right[i][j]:代表从(i,j)(i,j)能到达的最右位置

    up[i][j]up[i][j]:代表从(i,j)(i,j)向上扩展最长长度.

  • 相当于由i,ji,j这个位置向外向上拓展成为一个区间

  • 预处理左右边界，即分别从左往右/从右往左拓展

  • 如果可以向上扩展的话，取两个长度的交集

    （vscodevscode画图能画就不错了）

  • 最后再横竖求一下长度就好了！

#include<bits/stdc++.h>
#define IL inline
#define RI register int
#define maxn 2001
using namespace std;
IL void read(int &x){
    int f=1;x=0;char s=getchar();
    while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
    while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();}
    x*=f;
}
int res[maxn][maxn],left[maxn][maxn],right[maxn][maxn],up[maxn][maxn];
int n,m,ans1,ans2;
int main()
{
    read(n),read(m);
    for(RI i=1;i<=n;i++)
        for(RI j=1;j<=m;j++)
            {
                read(res[i][j]);
                left[i][j]=right[i][j]=j;
                up[i][j]=1;
            }
    for(RI i=1;i<=n;i++)
        for(RI j=2;j<=m;j++)
            if(res[i][j]!=res[i][j-1])
                left[i][j]=left[i][j-1];//预处理左边界
    for(RI i=1;i<=n;i++)
        for(RI j=m-1;j>0;j--)
            if(res[i][j]!=res[i][j+1])
                right[i][j]=right[i][j+1];//预处理右边界
    for(RI i=1;i<=n;i++)
        for(RI j=1;j<=m;j++)
            {
                if(i>1&&res[i][j]!=res[i-1][j])
                {
                    left[i][j]=max(left[i][j],left[i-1][j]);
                    right[i][j]=min(right[i][j],right[i-1][j]);
                    up[i][j]=up[i-1][j]+1;
                }
                int a=right[i][j]-left[i][j]+1;	//横向长度
                int b=min(a,up[i][j]);//竖向长度
                //printf("a:%d b:%d\n",a,b);
                ans1=max(ans1,b*b);//正方形
                ans2=max(ans2,a*up[i][j]);//长方形
            }
    printf("%d\n%d",ans1,ans2);
}

做法三：栈

其实思路和前面几种很像阿。
（1）做法

  • 一行一行进行考虑
  • 每一行，首先统计每一列的最大纵连个数
  • 从第一列开始，如果一直都满足条件的话（即左右不相等），统计最大的高度hh，更新两个答案
  • 进栈出栈有亿点点难理解，还好luoguluogu有个优秀的图片，自行手动模拟一下就懂了
#include<cstdio>
#include<iostream>
#include<cstring>
#define X (h[stack[top]])//矩形的宽 
#define Y (cur-stack[top-1]-1)//矩形的长 
#define Z (min(X,Y))//正方形的边长 
using namespace std;
int n,m,top,cur,ans1,ans2,stack[2010],map[2010][2010],h[2010];
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j) scanf("%d",&map[i][j]);
    for (int j=1;j<=n;++j){
        for (int i=1;i<=m;++i)
            if (j>1&&map[j][i]!=map[j-1][i]) ++h[i];
            else h[i]=1;
        cur=1;
        while (cur<=m){
            stack[0]=cur-1;
            stack[top=1]=cur++;
            while (cur<=m&&(map[j][cur]!=map[j][cur-1])){
                while (top&&h[stack[top]]>h[cur])
                    ans1=max(ans1,Z*Z),ans2=max(ans2,X*Y),--top;
                stack[++top]=cur++;
            }
            while (top) ans1=max(ans1,Z*Z),ans2=max(ans2,X*Y),--top;
        }
    }
    printf("%d\n%d\n",ans1,ans2);
    return 0;
}

做法0.50.5:最后说一下第一问的DPDP算法吧，时间复杂度o(n2)o(n^{2})

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,a[2005][2005];
namespace DynamicProgramming
{
    int dp1[2005][2005],dp2[2005][2005];
    void Dp()
    {
        int ans=0;
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=m;++j)
            {
                if(a[i][j])	dp1[i][j]=min(min(dp1[i-1][j],dp1[i][j-1]),dp1[i-1][j-1])+1;
                else	dp2[i][j]=min(min(dp2[i-1][j],dp2[i][j-1]),dp2[i-1][j-1])+1;
                ans=max(ans,max(dp1[i][j],dp2[i][j]));
            }
        }
        printf("%d\n",ans*ans);
    }
}
namespace MonotonicStack
{
    int cnt[2005][2005],ans,s[2005],l[2005];
    void Monotonic(int sp[])
    {
        int top=0,len=0;
        s[top]=l[top]=0;
        for(int i=1;i<=m;++i)
        {
            if(sp[i]>=s[top])	s[++top]=sp[i],l[top]=1;
            else
            {
                len=0;
                while(top && s[top]>sp[i])
                {
                    len+=l[top];
                    ans=max(ans,len*s[top]);
                    --top;
                }
                s[++top]=sp[i];
                l[top]=len+1;
            }
        }
        len=0;
        while(top)
        {
            len+=l[top];
            ans=max(ans,len*s[top]);
            --top;
        }
    }
    void Stack(){for(int i=1;i<=n;++i)	Monotonic(cnt[i]);}
    void Ans(){printf("%d",ans);}
}
using namespace MonotonicStack;
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            scanf("%d",&a[i][j]);
            if(!((i+j)&1))	a[i][j]^=1;
            if(a[i][j])	cnt[i][j]=cnt[i-1][j]+1;
        }
    }
    DynamicProgramming::Dp();
    MonotonicStack::Stack();
    memset(cnt,0,sizeof cnt);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            if(!a[i][j])	cnt[i][j]=cnt[i-1][j]+1;
        }
    }
    MonotonicStack::Stack();
    MonotonicStack::Ans();
    return 0;
}

结语

写了整整一个晚自习，人都是傻了。
希望自己也能从这道题目中学点什么吧（）

# 随笔
P2470 上一篇
P1248 加工生产调度 下一篇
浏览数 次 | 访客数 人
Powered by Gridea ©2019 | Theme By HsxyHao
Powered by ？
0%