Luogu5920 [IOI2005] gar(前缀和&思维)题解

发布于 2021-06-30  102 次阅读


题目大意

原题链接

给定一个 $L \times W$ 的花园,它被分为 $L \times W$ 个 $1 \times 1$ 的矩形。花园中有 $n$ 朵花。注意,这里一个格子上可能有两朵花

现在要求你找出两个不相交的矩形 $M_1$ 和 $M_2$,要求它们各包含 $k$ 朵花。

最小化 $M_1$ 和 $M_2$ 的周长。

$1 \le L,W \le 250$,$2 \le n \le 5 \times 10^3$,$K \le \frac{n}{2}$。

解题思路

我们发现两个不相交的矩形有一个奇妙的性质:必然可以找到一条平行于坐标轴的直线把这两个矩形隔开

这个性质有什么用呢?

我们可以枚举这条直线。当这条直线是横线是横着的(平行于 $x$ 轴)时,我们设 $U_i$ 是第 $i$ 行及上方的部分中,包含 $K$ 朵花的矩形的最小周长,$D_i$ 是第 $i$ 行下方的部分中,包含 $K$ 朵花的矩形的最小周长。

那么我们可以发现最后的答案就是两个矩形加起来,也即 $ans=\min_{1 \le i < L}(U_i+D_{L-i})$。

如果这条分割线是竖着的,同理,设 $L_i$ 和 $R_i$ 即可。

怎么求 $L,R,U,D$ 这四个数组呢?

以求 $U$ 为例,我们考虑枚举一个点 $(i,j)$ 作为上方矩形的左下角坐标,再枚举一个 $(i,k)$ 作为右下角。我们假设左上角的坐标为 $(t,j)$,那么可以发现,在 $k$ 不断变大的途中,由于增加了右边的一块区间,所以矩形内花的数量显然不会减少,也即上方的 $t$ 是不断下移(不会上移)的

效果类似于下图:

利用这样类似于单调性的优化,我们可以把复杂度优化到均摊 $O(L^3)$ 级别($L,W$ 同阶)。

这里关于求四个数组,有一个写法上的小技巧:

我们可以在求出一个数组后,每次直接顺时针把矩形旋转 $90$ 度,在新的矩形中按照上面一样的过程再求一遍即可。更多的细节见代码注释。

啊,对了,这道题中花的坐标是可能不在给定 $L \times W$ 矩阵内的,与题面描述不符,注意判断一下。

代码注释用英文写,是因为如果用中文,在不同编码转化的时候会出问题。

另外,锻炼一下英语也是好的(

#include<bits/stdc++.h>
#define min(a,b) ((a) < (b) ? (a) : (b))
using namespace std;
const int N=505;
const int inf=1000000005;

struct Position{
    int x,y;
}p[N*N];

int r,c,n,K,cnt=0;
int S[N][N],U[N],D[N],L[N],R[N];

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

inline int count(int A,int B,int C,int D){
    return S[C][D]-S[A-1][D]-S[C][B-1]+S[A-1][B-1];
}

inline void Rotate1(){      // From vertical rectangle to horizontal rectangle
    for (int i=1;i<=n;++i){
        int x=p[i].x,y=p[i].y;
        p[i].x=y,p[i].y=r-x+1;
    }
}

inline void Rotate2(){      // From horizontal rectangle to vertical rectangle
    for (int i=1;i<=n;++i){
        int x=p[i].x,y=p[i].y;
        p[i].x=y,p[i].y=c-x+1;
    }
}

inline void Calc(int r,int c,int *now){
    memset(S,0,sizeof(S));
    for (int i=1;i<=n;++i) ++S[p[i].x][p[i].y];     // not S[p[i].x][p[i].x]=1 ...
    // printf("S-before:\n");
    // for (int i=1;i<=r;++i){
    //  for (int j=1;j<=c;++j)
    //      printf("%d ",S[i][j]);
    //  printf("\n");
    // }
    for (int i=1;i<=r;++i)
        for (int j=1;j<=c;++j)
            S[i][j]=S[i][j]+S[i-1][j]+S[i][j-1]-S[i-1][j-1];
    // printf("S-after:\n");
    // for (int i=1;i<=r;++i){
    //  for (int j=1;j<=c;++j)
    //      printf("%d ",S[i][j]);
    //  printf("\n");
    // }
    for (int i=1;i<=r;++i)
        for (int j=1;j<=c;++j){
            int t=1;
            for (int k=j;k<=c;++k){
                while ((t<i) && (count(t+1,j,i,k)>=K)) ++t;
                if (count(t,j,i,k)==K) now[i]=min(now[i],(k-j+1+i-t+1)*2);
                // (t,j) —————————— (t,k)
                //  |                 |
                //  |                 |
                // (i,j) —————————— (i,k)
            }
        }
}

int main(){
    //freopen("Luogu5920.in","r",stdin);
    //freopen("Luogu5920.out","w",stdout);
    r=read(),c=read(); n=read(),K=read();
    for (int i=0;i<N;++i) L[i]=R[i]=U[i]=D[i]=inf;
    for (int i=1;i<=n;++i){
        int x=read(),y=read();
        if ((x<1) || (x>r)) continue;       // special judge
        if ((y<1) || (y>c)) continue;
        p[++cnt].x=x,p[cnt].y=y;
    }
    n=cnt;
    Calc(r,c,U),Rotate1(); Calc(c,r,R),Rotate2();       // rotate matrix 90 degrees clockwise each time
    Calc(r,c,D),Rotate1(); Calc(c,r,L),Rotate2();
    for (int i=2;i<=c;++i) L[i]=min(L[i],L[i-1]);       // notice that it is always a prefix minimum no matter it is L,U,R or D,because the matrix is rotated!
    for (int i=2;i<=r;++i) U[i]=min(U[i],U[i-1]);
    for (int i=2;i<=c;++i) R[i]=min(R[i],R[i-1]);
    for (int i=2;i<=r;++i) D[i]=min(D[i],D[i-1]);
    int ans=inf;
    for (int i=1;i<c;++i) ans=min(ans,L[i]+R[c-i]);     // calc the answer
    for (int i=1;i<r;++i) ans=min(ans,U[i]+D[r-i]);
    if (ans>=inf) printf("NO\n");
    else printf("%d\n",ans);
    return 0;
}

我们无法选择过去,但我们可以改变未来。