[JOISC 2020] 汉堡肉

lzqy_ · 2023-03-03 13:35:12 · 个人记录

硬是写成了10K工程题。

如果退化成一维，那么就是很经典的贪心，每次取最小的 r 来覆盖即可。类似地，也可以按每次取最大的 l。

考虑将这个结论扩展到二维，我们可以每次从最左的右边界上取一点，类似地，也可以在最右的左边界、最上的下边界、最下的上边界上取点。

但和一维不同的是，贪心策略只指定了点所在的线段，并没有确切位置。考虑将四个边界取出，令左边界的位置为 l，右边界的位置为 r，下边界的位置为 d，上边界的位置为 u。

容易发现，若 l\le r，那么每个区间的左右边界都包含 [l,r]，因此可以转化为一维问题，x 坐标在 [l,r] 之间随便取即可。d\le u 同理。

考虑 l>r,d>u 的情况，即四个边界长成这个样子：

先看 K \le 3。有 4 个边界，但点数 \le 4，意味着一定要有点同时满足多个边界，即落在边界的交点上。由于交点数最多只有 4，所以直接 O(4^Kn) 爆搜即可。

再看 K=4。显然可以先跑一遍 K \le 3 的暴力，若无解，那么说明每条边界上恰好有一个点，并且要覆盖所有的矩形。

我们将每个矩形拿出来看：

• 和 1 个边界有交：直接缩小该边界的范围即可。
• 和 >2 个边界有交：容易发现，满足此条件的矩形至少完全包含一条边界，一定能被覆盖，因此可以直接忽略。

发现比较难处理的是恰好与 2 个边界有交的矩形。对于这样的矩形，实际上就是要选择它被哪条边界覆盖，且边界数 =2。发现这是一个 2-SAT 形式的问题，即交集为空的矩形不能选择同一条边界。这样暴力连边跑 2-SAT，我们就得到了一个 O(n^2) 的做法。

考虑利用四个边界优化建图。对于一条边界，若覆盖了一个和该边界的交为 [l,r] 矩形，那么如果有另一个矩形和该边界的交位于 (r,\inf],[0,l) 之间，那么这两个矩形就不能同时被这个边界覆盖。发现这是一个前后缀的形式，离散化后前后缀优化建图即可。

因此总时间复杂度 O(4^Kn+Kn)。

#include<bits/stdc++.h>
#define il inline
using namespace std;
const int maxn=800010;
const int inf=1<<30;
il int read(){
    int x=0;
    char c=getchar();
    for(;!(c>='0'&&c<='9');c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=(x<<1)+(x<<3)+c-'0';
    return x; 
}
il void chkmin(int &x,int y){if(y<x)x=y;}
il void chkmax(int &x,int y){if(y>x)x=y;}
struct pot{
    int x,y;
};
struct rec{
    int l,r,u,d,id;
}a[maxn];
il bool cmp1(rec a,rec b){return a.d<b.d;}
il bool cmp2(rec a,rec b){return a.r<b.r;}
il bool cr(rec a,pot b){return b.x>=a.l&&b.x<=a.r&&b.y>=a.u&&b.y<=a.d;}
int b1[maxn],b2[maxn];
int ax[maxn],ay[maxn]; 
int Re1[maxn],Re2[maxn];
map<int,int>M1,M2;
int n,K,N,M,cn;
int vis[maxn];
bool dfs(int x){
    int l=-1,r=inf,u=-1,d=inf;
    for(int i=1;i<=n;i++)
        if(!vis[i]){
            chkmax(l,a[i].l),chkmin(r,a[i].r);
            chkmax(u,a[i].u),chkmin(d,a[i].d);
        }
    if(l==-1){
        for(int i=1;i<x;i++)
            printf("%d %d\n",Re1[ax[i]],Re2[ay[i]]);
        for(int i=x;i<=K;i++)
            printf("100 100\n");
        return 1;
    }
    if(x>K) return 0;
    pot t;

    t=pot{l,u},ax[x]=l,ay[x]=u;
    for(int i=1;i<=n;i++) vis[i]+=cr(a[i],t);
    if(dfs(x+1)) return 1;
    for(int i=1;i<=n;i++) vis[i]-=cr(a[i],t);

    t=pot{l,d},ax[x]=l,ay[x]=d;
    for(int i=1;i<=n;i++) vis[i]+=cr(a[i],t);
    if(dfs(x+1)) return 1;
    for(int i=1;i<=n;i++) vis[i]-=cr(a[i],t);

    t=pot{r,u},ax[x]=r,ay[x]=u;
    for(int i=1;i<=n;i++) vis[i]+=cr(a[i],t);
    if(dfs(x+1)) return 1;
    for(int i=1;i<=n;i++) vis[i]-=cr(a[i],t);

    t=pot{r,d},ax[x]=r,ay[x]=d;
    for(int i=1;i<=n;i++) vis[i]+=cr(a[i],t);
    if(dfs(x+1)) return 1;
    for(int i=1;i<=n;i++) vis[i]-=cr(a[i],t);
    return 0;
}
struct edge{
    int v,to;
}e[maxn<<5];
int head[maxn<<3],ecnt;
void add(int u,int v){
    if(!u||!v) return ;
    e[++ecnt].v=v,e[ecnt].to=head[u],head[u]=ecnt;
}
void addd(int u,int v){add(u,v),add(v,u);}
bool Vis[maxn<<3];
int col[maxn<<3],sta[maxn<<3];
int dfn[maxn<<3],low[maxn<<3];
int st[maxn<<3],top,idx,Col;
int lu,ld,ru,rd;
int ul,ur,dl,dr;
int S,tot;
il int id(int x,int t){return t?S+cn+x:S+x;}
il int rid(int x,int t){return id(x,t)+2*cn;}
//l
il int idl(int i){return (i<lu||i>ld)?0:i-lu+1;}
il int ridl(int i){return (i<lu||i>ld)?0:(ld-lu+1)+i-lu+1;}
il int rev_idl(int i){return (i<lu||i>ld)?0:2*(ld-lu+1)+i-lu+1;}
il int rev_ridl(int i){return (i<lu||i>ld)?0:3*(ld-lu+1)+i-lu+1;}

//r
il int idr(int i){return (i<ru||i>rd)?0:4*(ld-lu+1)+i-ru+1;}
il int ridr(int i){return (i<ru||i>rd)?0:4*(ld-lu+1)+(rd-ru+1)+i-ru+1;}
il int rev_idr(int i){return (i<ru||i>rd)?0:4*(ld-lu+1)+2*(rd-ru+1)+i-ru+1;}
il int rev_ridr(int i){return (i<ru||i>rd)?0:4*(ld-lu+1)+3*(rd-ru+1)+i-ru+1;}

//u
il int idu(int i){return (i<ul||i>ur)?0:4*(ld-lu+1)+4*(rd-ru+1)+i-ul+1;}
il int ridu(int i){return (i<ul||i>ur)?0:4*(ld-lu+1)+4*(rd-ru+1)+(ur-ul+1)+i-ul+1;}
il int rev_idu(int i){return (i<ul||i>ur)?0:4*(ld-lu+1)+4*(rd-ru+1)+2*(ur-ul+1)+i-ul+1;}
il int rev_ridu(int i){return (i<ul||i>ur)?0:4*(ld-lu+1)+4*(rd-ru+1)+3*(ur-ul+1)+i-ul+1;}

//d
il int idd(int i){return (i<dl||i>dr)?0:4*(ld-lu+1)+4*(rd-ru+1)+4*(ur-ul+1)+i-dl+1;}
il int ridd(int i){return (i<dl||i>dr)?0:4*(ld-lu+1)+4*(rd-ru+1)+4*(ur-ul+1)+(dr-dl+1)+i-dl+1;}
il int rev_idd(int i){return (i<dl||i>dr)?0:4*(ld-lu+1)+4*(rd-ru+1)+4*(ur-ul+1)+2*(dr-dl+1)+i-dl+1;}
il int rev_ridd(int i){return (i<dl||i>dr)?0:4*(ld-lu+1)+4*(rd-ru+1)+4*(ur-ul+1)+3*(dr-dl+1)+i-dl+1;}
void Tarjan(int x){
    dfn[x]=low[x]=++idx,st[++top]=x,Vis[x]=1;
    for(int i=head[x];i;i=e[i].to)
        if(!dfn[e[i].v]) Tarjan(e[i].v),chkmin(low[x],low[e[i].v]);
        else if(Vis[e[i].v]) chkmin(low[x],dfn[e[i].v]);
    if(low[x]==dfn[x]){
        ++Col;int cnn=0;
        while(st[top+1]!=x)
            col[st[top]]=Col,Vis[st[top]]=0,top--,cnn++;
    }
}
void Solve(){
    int l=-1,r=inf,u=-1,d=inf;
    for(int i=1;i<=n;i++){
        if(a[i].l>l) l=a[i].l,lu=a[i].u,ld=a[i].d;
        if(a[i].r<r) r=a[i].r,ru=a[i].u,rd=a[i].d;
        if(a[i].u>u) u=a[i].u,ul=a[i].l,ur=a[i].r;
        if(a[i].d<d) d=a[i].d,dl=a[i].l,dr=a[i].r;
    }
    for(int i=1,sum=0;i<=n;i++,sum=0){
        if(a[i].l<=l&&a[i].r>=l&&!(a[i].u>ld||a[i].d<lu)) sum++;
        if(a[i].l<=r&&a[i].r>=r&&!(a[i].u>rd||a[i].d<ru)) sum++;
        if(a[i].u<=u&&a[i].d>=u&&!(a[i].l>ur||a[i].r<ul)) sum++;
        if(a[i].u<=d&&a[i].d>=d&&!(a[i].l>dr||a[i].r<dl)) sum++;
        if(sum!=1) continue; 
        if(a[i].l<=l&&a[i].r>=l&&!(a[i].u>ld||a[i].d<lu)) chkmax(lu,a[i].u),chkmin(ld,a[i].d);
        if(a[i].l<=r&&a[i].r>=r&&!(a[i].u>rd||a[i].d<ru)) chkmax(ru,a[i].u),chkmin(rd,a[i].d);
        if(a[i].u<=u&&a[i].d>=u&&!(a[i].l>ur||a[i].r<ul)) chkmax(ul,a[i].l),chkmin(ur,a[i].r);
        if(a[i].u<=d&&a[i].d>=d&&!(a[i].l>dr||a[i].r<dl)) chkmax(dl,a[i].l),chkmin(dr,a[i].r);
    } 
    for(int i=1,sum=0;i<=n;i++,sum=0){ 
        if(a[i].l<=l&&a[i].r>=l&&!(a[i].u>ld||a[i].d<lu)) sum++;
        if(a[i].l<=r&&a[i].r>=r&&!(a[i].u>rd||a[i].d<ru)) sum++;
        if(a[i].u<=u&&a[i].d>=u&&!(a[i].l>ur||a[i].r<ul)) sum++;
        if(a[i].u<=d&&a[i].d>=d&&!(a[i].l>dr||a[i].r<dl)) sum++;
        if(sum==2) a[i].id=++cn;
        else continue;
        if(a[i].l<=l&&a[i].r>=l&&!(a[i].u>ld||a[i].d<lu)) chkmax(a[i].u,lu),chkmin(a[i].d,ld);
        if(a[i].l<=r&&a[i].r>=r&&!(a[i].u>rd||a[i].d<ru)) chkmax(a[i].u,ru),chkmin(a[i].d,rd);
        if(a[i].u<=u&&a[i].d>=u&&!(a[i].l>ur||a[i].r<ul)) chkmax(a[i].l,ul),chkmin(a[i].r,ur);
        if(a[i].u<=d&&a[i].d>=d&&!(a[i].l>dr||a[i].r<dl)) chkmax(a[i].l,dl),chkmin(a[i].r,dr);
    } 
    for(int i=lu;i<ld;i++) add(ridl(i),ridl(i+1));
    for(int i=lu+1;i<=ld;i++) add(rev_ridl(i),rev_ridl(i-1));
    for(int i=lu;i<=ld;i++) addd(ridl(i),rev_ridl(i)),add(idl(i),rev_idl(i));

    for(int i=ru;i<rd;i++) add(ridr(i),ridr(i+1));
    for(int i=ru+1;i<=rd;i++) add(rev_ridr(i),rev_ridr(i-1));
    for(int i=ru;i<=rd;i++) addd(ridr(i),rev_ridr(i)),addd(idr(i),rev_idr(i));

    for(int i=ul;i<ur;i++) add(ridu(i),ridu(i+1));
    for(int i=ul+1;i<=ur;i++) add(rev_ridu(i),rev_ridu(i-1));
    for(int i=ul;i<=ur;i++) addd(ridu(i),rev_ridu(i)),addd(idu(i),rev_idu(i));

    for(int i=dl;i<dr;i++) add(ridd(i),ridd(i+1));
    for(int i=dl+1;i<=dr;i++) add(rev_ridd(i),rev_ridd(i-1));
    for(int i=dl;i<=dr;i++) addd(ridd(i),rev_ridd(i)),addd(idd(i),rev_idd(i));

    S=4*(ld-lu+1)+4*(rd-ru+1)+4*(ur-ul+1)+4*(dr-dl+1);  
    for(int i=1,sum=0;i<=n;i++,sum=0){
        if(!a[i].id) continue;bool fl=0;
        add(rid(a[i].id,1),id(a[i].id,0));
        add(rid(a[i].id,0),id(a[i].id,1));
        if(a[i].l<=l&&a[i].r>=r&&!(a[i].u>ld||a[i].d<lu)){
            add(id(a[i].id,fl),ridl(a[i].d+1)),add(id(a[i].id,fl),rev_ridl(a[i].u-1));
            add(idl(a[i].d+1),rid(a[i].id,fl)),add(rev_idl(a[i].u-1),id(a[i].id,fl));
            add(id(a[i].id,fl),idl(a[i].d)),add(id(a[i].id,fl),rev_idl(a[i].u));
            add(ridl(a[i].d),rid(a[i].id,fl)),add(rev_ridl(a[i].u),rid(a[i].id,fl)),fl=1;
        }
        if(a[i].l<=r&&a[i].r>=r&&!(a[i].u>rd||a[i].d<ru)){
            add(id(a[i].id,fl),ridr(a[i].d+1)),add(id(a[i].id,fl),rev_ridr(a[i].u-1));
            add(idr(a[i].d+1),rid(a[i].id,fl)),add(rev_idr(a[i].u-1),id(a[i].id,fl));
            add(id(a[i].id,fl),idr(a[i].d)),add(id(a[i].id,fl),rev_idr(a[i].u));
            add(ridr(a[i].d),rid(a[i].id,fl)),add(rev_ridr(a[i].u),rid(a[i].id,fl)),fl=1;
        }
        if(a[i].u<=u&&a[i].d>=u&&!(a[i].l>ul||a[i].r<ur)){
            add(id(a[i].id,fl),ridu(a[i].r+1)),add(id(a[i].id,fl),rev_ridu(a[i].l-1));
            add(idu(a[i].r+1),rid(a[i].id,fl)),add(rev_idu(a[i].l-1),id(a[i].id,fl));
            add(id(a[i].id,fl),idu(a[i].r)),add(id(a[i].id,fl),rev_idu(a[i].l));
            add(ridu(a[i].r),rid(a[i].id,fl)),add(rev_ridu(a[i].l),rid(a[i].id,fl)),fl=1;
        }
        if(a[i].u<=d&&a[i].d>=d&&!(a[i].l>dl||a[i].r<dr)){
            add(id(a[i].id,fl),ridd(a[i].r+1)),add(id(a[i].id,fl),rev_ridd(a[i].l-1));
            add(idd(a[i].r+1),rid(a[i].id,fl)),add(rev_idd(a[i].l-1),id(a[i].id,fl));
            add(id(a[i].id,fl),idd(a[i].r)),add(id(a[i].id,fl),rev_idd(a[i].l));
            add(ridd(a[i].r),rid(a[i].id,fl)),add(rev_ridd(a[i].l),rid(a[i].id,fl)),fl=1;
        }
    } 
    tot=S+2*cn;
    for(int i=1;i<=tot;i++)
        if(!dfn[i]) Tarjan(i);
    for(int i=1;i<=n;i++){
        if(!a[i].id) continue;
        if(sta[col[id(a[i].id,0)]]!=2){
            if(a[i].l<=l&&a[i].r>=r&&!(a[i].u>ld||a[i].d<lu)) chkmax(lu,a[i].u),chkmin(ld,a[i].d);
            else if(a[i].l<=r&&a[i].r>=r&&!(a[i].u>rd||a[i].d<ru)) chkmax(ru,a[i].u),chkmin(rd,a[i].d);
            else if(a[i].u<=u&&a[i].d>=u&&!(a[i].l>ur||a[i].r<ul)) chkmax(ul,a[i].l),chkmin(ur,a[i].r);
            else if(a[i].u<=d&&a[i].d>=d&&!(a[i].l>dr||a[i].r<dl)) chkmax(dl,a[i].l),chkmin(dr,a[i].r);
            sta[col[id(a[i].id,0)]]=1;
        }else assert(sta[col[id(a[i].id,1)]]!=2),sta[col[id(a[i].id,1)]]=1;
        if(sta[col[id(a[i].id,1)]]!=2){
            int fl=0;
            if(a[i].l<=l&&a[i].r>=r&&!(a[i].u>ld||a[i].d<lu)&&fl<2) fl?chkmax(lu,a[i].u),chkmin(ld,a[i].d),fl++:fl++;
            if(a[i].l<=r&&a[i].r>=r&&!(a[i].u>rd||a[i].d<ru)&&fl<2) fl?chkmax(ru,a[i].u),chkmin(rd,a[i].d),fl++:fl++;
            if(a[i].u<=u&&a[i].d>=u&&!(a[i].l>ur||a[i].r<ul)&&fl<2) fl?chkmax(ul,a[i].l),chkmin(ur,a[i].r),fl++:fl++;
            if(a[i].u<=d&&a[i].d>=d&&!(a[i].l>dr||a[i].r<dl)&&fl<2) fl?chkmax(dl,a[i].l),chkmin(dr,a[i].r),fl++:fl++;
            sta[col[id(a[i].id,0)]]=1;
        }
    }
    printf("%d %d\n",Re1[l],Re2[lu]);
    printf("%d %d\n",Re1[r],Re2[ru]);
    printf("%d %d\n",Re1[ul],Re2[u]);
    printf("%d %d\n",Re1[dl],Re2[d]);
} 

int main(){
    n=read(),K=read(); 
    for(int i=1;i<=n;i++)
        a[i].l=read(),a[i].u=read(),a[i].r=read(),a[i].d=read();
    for(int i=1;i<=n;i++){
        b1[i]=a[i].l,b1[i+n]=a[i].r;
        b2[i]=a[i].d,b2[i+n]=a[i].u;
    }
    sort(b1+1,b1+1+n+n);
    sort(b2+1,b2+1+n+n);
    for(int i=1;i<=n+n;i++)
        if(i==1||b1[i]!=b1[i-1])
            M1[b1[i]]=++N,Re1[N]=b1[i];
    for(int i=1;i<=n+n;i++)
        if(i==1||b2[i]!=b2[i-1])
            M2[b2[i]]=++M,Re2[M]=b2[i];
    for(int i=1;i<=n;i++){
        a[i].l=M1[a[i].l],a[i].r=M1[a[i].r];
        a[i].d=M2[a[i].d],a[i].u=M2[a[i].u];
    }int l=-1,r=inf,u=-1,d=inf;
    for(int i=1;i<=n;i++){
        chkmax(l,a[i].l),chkmin(r,a[i].r);
        chkmax(u,a[i].u),chkmin(d,a[i].d);
    }
    if(l<=r){
        int ans[5]={0},j=0;
        sort(a+1,a+1+n,cmp1);
        for(int i=1;i<=n;i++){
            bool fl=0;
            for(int k=1;k<=j;k++)
                if(a[i].u<=ans[k]&&a[i].d>=ans[k]) fl=1;
            if(fl) continue;
            printf("%d %d\n",Re1[l],Re2[a[i].d]),ans[++j]=a[i].d;
        }
        for(int i=j+1;i<=K;i++) printf("100 100\n");
        return 0;
    }
    if(u<=d){
        int ans[5]={0},j=0;
        sort(a+1,a+1+n,cmp2);
        for(int i=1;i<=n;i++){
            bool fl=0;
            for(int k=1;k<=j;k++)
                if(a[i].l<=ans[k]&&a[i].r>=ans[k]) fl=1;
            if(fl) continue;
            printf("%d %d\n",Re1[a[i].r],Re2[u]),ans[++j]=a[i].r;
        }
        for(int i=j+1;i<=K;i++) printf("100 100\n");
        return 0;
    }
    if(!dfs(1)) Solve();
    return 0;
}