草根妖怪网络

chen_zhe · 2022-08-07 17:21:16 · 题解

预处理出 \texttt G 和 \texttt P 的二维前缀和，以便后续计算。

进行计算的时候，只需枚举子矩阵的第一行和最后一行，判断这其中需要改的名字颜色数量是否小于等于 k（即可以用神权将其全部变得相同），这里可以用二维前缀和差分完成。接着，使用双指针（two-pointers）便可计算出子矩阵的最大整齐度。

输出方案也类似，通过记录下最大整齐度的子矩阵选择的四个顶点，通过对其内部的元素判断之后便可构造。

注意有一种 corner cases：最大子矩阵为全紫名矩阵。

时间复杂度 O(n^3)。

#include<bits/stdc++.h>
using namespace std;
int n,m,k,ans,ansxl,ansxr,ansyl,ansyr;
int sum[505][505],cnt[505][505];
char s[505][505];
bool check1(int xl,int xr,int yl,int yr)
{
    if(cnt[xr][yr]-cnt[xr][yl-1]-cnt[xl-1][yr]+cnt[xl-1][yl-1]>0)
        return 0;
    if(sum[xr][yr]-sum[xr][yl-1]-sum[xl-1][yr]+sum[xl-1][yl-1]<=k)
        return 1;
    if(sum[xr][yr]-sum[xr][yl-1]-sum[xl-1][yr]+sum[xl-1][yl-1]>=(xr-xl+1)*(yr-yl+1)-k)
        return 1;
    return 0;
}
bool check2(int xl,int xr,int yl,int yr)
{
    if(cnt[xr][yr]-cnt[xr][yl-1]-cnt[xl-1][yr]+cnt[xl-1][yl-1]==(xr-xl+1)*(yr-yl+1))
        return 1;
    else
        return 0;
}
int main()
{
    cin >> n >> m >> k;
    for(int i=1;i<=n;i++)
    {
        cin >> (s[i]+1);
        for(int j=1;j<=m;j++)
        {
            sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+(s[i][j]=='G');
            cnt[i][j]=cnt[i][j-1]+cnt[i-1][j]-cnt[i-1][j-1]+(s[i][j]=='P');
        }
    }
    for(int yl=1;yl<=m;yl++)
    {
        for(int yr=yl;yr<=m;yr++)
        { 
            int l=1,r=0;
            while(r<=n && l<=n)
            {
                while(r<n && check1(l,r+1,yl,yr))
                    r++;
                if((yr-yl+1)*(r-l+1)>ans)
                {
                    ansxl=l;
                    ansxr=r;
                    ansyl=yl;
                    ansyr=yr;
                    ans=(yr-yl+1)*(r-l+1);
                }
                l++;
            }
        }
    }
    for(int yl=1;yl<=m;yl++)
    {
        for(int yr=yl;yr<=m;yr++)
        { 
            int l=1,r=0;
            while(r<=n && l<=n)
            {
                while(r<n && check2(l,r+1,yl,yr))
                    r++;
                if((yr-yl+1)*(r-l+1)>ans)
                {
                    ansxl=l;
                    ansxr=r;
                    ansyl=yl;
                    ansyr=yr;
                    ans=(yr-yl+1)*(r-l+1);
                }
                l++;
            }
        }
    }
    cout << ans << endl;
    if(check2(ansxl,ansxr,ansyl,ansyr))
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
                cout << s[i][j];
            cout << endl;
        }
    }
    else if(sum[ansxr][ansyr]-sum[ansxr][ansyl-1]-sum[ansxl-1][ansyr]+sum[ansxl-1][ansyl-1]<=k)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(i>=ansxl && i<=ansxr && j>=ansyl && j<=ansyr)
                    cout << 'B';
                else
                    cout << s[i][j];
            }
            cout << endl;
        }
    }
    else 
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(i>=ansxl && i<=ansxr && j>=ansyl && j<=ansyr)
                    cout << 'G';
                else
                    cout << s[i][j]; 
            }
            cout << endl;
        }
    }
    return 0;
}

验题人 @离散小波变换° 的代码：

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
const int MAXN=500+3;
int A[MAXN][MAXN],B[MAXN][MAXN],C[MAXN][MAXN];
int qry(int T[][MAXN],int l1,int l2,int r){
    return T[l2][r]-T[l1-1][r];
}
char S[MAXN][MAXN];
int n,m,k;
int qread(){
    int w=1,c,ret;
    while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0';
    while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
    return ret*w;
}
int ans=-1,a1,a2,a3,a4,a5;
int main(){
    n=qread(),m=qread(),k=qread();
    up(1,n,i) scanf("%s",S[i]+1);
    up(1,n,i) up(1,m,j){
        A[i][j]=(S[i][j]=='P')+A[i-1][j];
        B[i][j]=(S[i][j]=='B')+B[i-1][j];
        C[i][j]=(S[i][j]=='G')+C[i-1][j];
    }
    up(1,n,i) up(i,n,j){
        int sp=0,sb=0,sg=0,lp=1,lb=1,lg=1,x=j-i+1;
        up(1,m,r){
            int wp=qry(A,i,j,r); sp+=wp;
            int wb=qry(B,i,j,r); sb+=wb;
            int wg=qry(C,i,j,r); sg+=wg;
            if(wp    ) lb=r+1,lg=r+1,sb=sg=0;
            if(wb||wg) lp=r+1,sp=0;
            while(lp<=r&&x*(r-lp+1)-sp>k) sp-=qry(A,i,j,lp),++lp;
            while(lb<=r&&x*(r-lb+1)-sb>k) sb-=qry(B,i,j,lb),++lb;
            while(lg<=r&&x*(r-lg+1)-sg>k) sg-=qry(C,i,j,lg),++lg;
            if(x*(r-lp+1)>ans) ans=x*(r-lp+1),a1=i,a2=lp,a3=j,a4=r,a5='P';
            if(x*(r-lb+1)>ans) ans=x*(r-lb+1),a1=i,a2=lb,a3=j,a4=r,a5='B';
            if(x*(r-lg+1)>ans) ans=x*(r-lg+1),a1=i,a2=lg,a3=j,a4=r,a5='G';
        }
    }
    up(a1,a3,i) up(a2,a4,j) S[i][j]=a5;
    printf("%d\n",ans);
    up(1,n,i) printf("%s\n",S[i]+1);
    return 0;
}