【3】做题心得 - 2025 NOIP #68 - T2【链表】【神人】

ExFish · 2025-11-25 22:14:20 · 题解

你首先考虑把合并变为分裂。然后就可以分治去做，把矩形集合分为两部分。因为问题问的是是否有方案，所以切多少刀都是无所谓的。所以就有一个 n^2 的做法是不停递归并判定是否可以切割成功。这个东西如何优化呢？你会发现你不一定每一次都要找到所有分割线，所以就考虑使用链表维护这个东西。然后就成为了一坨答辩，但是代码还是比较好懂的。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct cast{ int ax,ay,bx,by; }a[N];
int n,lasted,deleted,si[N];
bool cmpAX(int x,int y){ return a[x].ax<a[y].ax; }
bool cmpBX(int x,int y){ return a[x].bx>a[y].bx; }
bool cmpAY(int x,int y){ return a[x].ay<a[y].ay; }
bool cmpBY(int x,int y){ return a[x].by>a[y].by; }
struct mlist{ int nxt[N],prv[N],hd; }axl,ayl,bxl,byl;
void Push(mlist &x,int val){
    x.prv[val]=0;
    x.nxt[val]=x.hd;
    x.prv[x.hd]=val;
    x.hd=val;
}
void Pop(mlist &x,int val){
    x.prv[x.nxt[val]]=x.prv[val];
    x.nxt[x.prv[val]]=x.nxt[val];
    if(x.hd==val) x.hd=x.nxt[val];  
}
bool cutter(){
    if(lasted==1) return 1;
    int updated=0;
    int ax=axl.hd,ay=ayl.hd,bx=bxl.hd,by=byl.hd;
    int rx=0     ,ry=0     ,lx=1e9   ,ly=1e9   ;
    for(int i=1;i<=lasted/2;i++){
        rx=max(rx,a[ax].bx); ax=axl.nxt[ax]; if(rx<=a[ax].ax){ updated=1, deleted=i; for(int j=1,p=axl.hd;j<=i;j++,p=axl.nxt[p])si[j]=p; break; }
        ry=max(ry,a[ay].by); ay=ayl.nxt[ay]; if(ry<=a[ay].ay){ updated=1, deleted=i; for(int j=1,p=ayl.hd;j<=i;j++,p=ayl.nxt[p])si[j]=p; break; }
        lx=min(lx,a[bx].ax); bx=bxl.nxt[bx]; if(lx>=a[bx].bx){ updated=1, deleted=i; for(int j=1,p=bxl.hd;j<=i;j++,p=bxl.nxt[p])si[j]=p; break; }
        ly=min(ly,a[by].ay); by=byl.nxt[by]; if(ly>=a[by].by){ updated=1, deleted=i; for(int j=1,p=byl.hd;j<=i;j++,p=byl.nxt[p])si[j]=p; break; }
    }
    if(!updated) return 0;
    lasted-=deleted;
    for(int i=1;i<=deleted;i++)
        Pop(axl,si[i]),
        Pop(bxl,si[i]),
        Pop(ayl,si[i]),
        Pop(byl,si[i]);
    if(!cutter()) return 0;
    axl.hd=0; sort(si+1,si+deleted+1,cmpAX); for(int i=deleted;i>=1;i--) Push(axl,si[i]);
    ayl.hd=0; sort(si+1,si+deleted+1,cmpAY); for(int i=deleted;i>=1;i--) Push(ayl,si[i]);
    bxl.hd=0; sort(si+1,si+deleted+1,cmpBX); for(int i=deleted;i>=1;i--) Push(bxl,si[i]);
    byl.hd=0; sort(si+1,si+deleted+1,cmpBY); for(int i=deleted;i>=1;i--) Push(byl,si[i]);
    lasted=deleted;
    return cutter();
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].ax>>a[i].ay>>a[i].bx>>a[i].by, si[i]=i;
    axl.hd=0; sort(si+1,si+n+1,cmpAX); for(int i=n;i>=1;i--) Push(axl,si[i]);
    ayl.hd=0; sort(si+1,si+n+1,cmpAY); for(int i=n;i>=1;i--) Push(ayl,si[i]);
    bxl.hd=0; sort(si+1,si+n+1,cmpBX); for(int i=n;i>=1;i--) Push(bxl,si[i]);
    byl.hd=0; sort(si+1,si+n+1,cmpBY); for(int i=n;i>=1;i--) Push(byl,si[i]);
    lasted=n;
    cout<<(cutter()?"YES\n":"NO\n");
    return;
}
int main(){
    freopen("kingdom.in","r",stdin);
    freopen("kingdom.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve(); 
    return 0;
}