P11815 [PA 2019 Final] 领地 / Terytoria 题解

· · 题解

简单题。

注意到一个 ban 掉的矩形至少会留下一条边界上的两个端点，所以所有的点都至少可以被集中在矩形的两个对角顶点上，先放完仅能放在一个顶点上的，对于能在两个顶点自由选择的点，显然全放在更多的那边更优。

但这样不一定最优，可能存在中间的一个点能够集中很多点。我们直接枚举一个中间点，把所有能放的点全部集中过来，剩下的点继续考虑选择放在对角顶点即可，直接模拟用差分维护一下即可做到 O(n+XY)。

正确性的话，稍微画一下能发现最优情况不会选择 \ge 4 个点，且非顶点不会选择超过 1 个，因为非顶点之间也肯定是尽量把一个弄的很大，剩下的那个一定可以平移到顶点上，或者与一个顶点重新分成一对对角顶点。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;

int n,X,Y,all;
int A[16];
int a[16][1005][1005];

inline void in(int &n){
    n=0;
    char c=getchar();
    while(c<'0' || c>'9') c=getchar();
    while(c>='0'&&c<='9') n=n*10+c-'0',c=getchar();
    return ;
}

int main(){
    in(n),in(X),in(Y);
    while(n--){
        int x,y,xx,yy,c,s=0;
        in(x),in(y),in(xx),in(yy),in(c);
        all+=c;
        if(x==1&&y==1) s|=1;
        if(x==1&&yy==Y) s|=2;
        if(xx==X&&y==1) s|=4;
        if(xx==X&&yy==Y) s|=8;
        A[s]+=c;
        a[s][x][y]+=c;
        a[s][xx+1][y]-=c;
        a[s][x][yy+1]-=c;
        a[s][xx+1][yy+1]+=c;
    }
    for(int s=0;s<16;s++)
        for(int i=1;i<=X;i++)
            for(int j=1;j<=Y;j++)
                a[s][i][j]+=a[s][i-1][j]+a[s][i][j-1]-a[s][i-1][j-1];
    ll ans=0;
    for(int x:{0,1,2,3}){
        for(int y:{0,1,2,3}){
            if(x==y) continue;
            ll xx=0,yy=0,cc=0;
            for(int s=0;s<16;s++){
                if(!(s>>x&1)) xx+=A[s];
                if(!(s>>y&1)) yy+=A[s];
                if(!(s>>x&1)&&!(s>>y&1)) cc+=A[s];
            }
            if(xx<yy) xx-=cc;
            else yy-=cc;
            ans=max(ans,xx*(xx-1)/2+yy*(yy-1)/2);
        }
    }
    for(int i=1;i<=X;i++){
        for(int j=1;j<=Y;j++){
            if(i==1&&j==1) continue;
            if(i==1&&j==Y) continue;
            if(i==X&&j==1) continue;
            if(i==X&&j==Y) continue;
            ll s=all;
            for(int x=0;x<16;x++) s-=a[x][i][j];
            s=s*(s-1)/2;
            ans=max(ans,s);
            int b[4]={0},c[4][4]={0};
            for(int x=0;x<16;x++){
                for(int xx:{0,1,2,3}){
                    if((x>>xx)&1) continue;
                    b[xx]+=a[x][i][j];
                    for(int yy:{0,1,2,3})
                        if(!((x>>yy)&1)) c[xx][yy]+=a[x][i][j];
                }
            }
            for(int x:{0,1,2,3}){
                ans=max(ans,s+1ll*b[x]*(b[x]-1)/2);
                for(int y:{0,1,2,3}){
                    if(y==x) continue;
                    ll xx=b[x],yy=b[y];
                    if(xx>yy) yy-=c[x][y];
                    else xx-=c[x][y];
                    ans=max(ans,s+xx*(xx-1)/2+yy*(yy-1)/2);
                }
            }
        }
    }
    printf("%lld\n",ans);

    return 0;
}