题解：AT_abc432_d [ABC432D] Suddenly, A Tempest

· · 题解

居然没场切

注意到 1\le N\le 14，所以连通块个数较少。\ 我们可以把连通块分成几个矩形，最后合并即可。

处理每个风暴的时候，遍历每个现有的矩形：

处理完所有风暴后，遍历每对矩形。如果这对矩形相邻，用并查集合并。（对于判断相邻，稍微分类讨论一下即可）\ 最后，分别把每个连通块里的矩形面积相加，输出即可。（显然矩形不会重叠）

:::warning[注意]{open} 记得排序答案！ :::

Code

这里手写了并查集，在 AtCoder 提交时也可以用 AtCoder Library。

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define eb emplace_back
#define mkp(x,y) make_pair((x),(y))
#define pii pair<int,int>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define fir first
#define sec second
#define il inline
#define re register
#define rep(x,st,en) for(int x=st;x<=en;++x)
#define down(x,st,en) for(int x=st;x>=en;--x)
//#define mp(x,y) make_pair((x),(y))
//#define int long long
using namespace std;
struct rect{//矩形 
    ll x,y,xx,yy;
    rect(ll a,ll b,ll c,ll d):x(a),y(b),xx(c),yy(d){}
};
int n;
ll x,y;
vector<rect> now;//所有的矩形 
int fa[114514];//并查集 
vector<int> g[114514];//分连通块用的 
il int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
il void merge(int x,int y){
    x=find(x),y=find(y);
    if(x!=y){
        fa[y]=x;
    } 
}
il bool touch(rect a,rect b){//判断矩形是否相邻 
    if(b.x==a.xx+1){
        if(!(b.y>a.yy||b.yy<a.y))return 1;
        else return 0;
    }else if(b.xx==a.x-1){
        if(!(b.y>a.yy||b.yy<a.y))return 1;
        else return 0;
    }else if(b.y==a.yy+1){
        if(!(b.x>a.xx||b.xx<a.x))return 1;
        else return 0;
    }else if(b.yy==a.y-1){
        if(!(b.x>a.xx||b.xx<a.x))return 1;
        else return 0;
    }else return 0;
}
signed main(){
    scanf("%d %lld %lld",&n,&x,&y);
    now.eb(0,0,x-1,y-1);//最初矩形 
    rep(i,1,n){
        vector<rect> v;
        char c;
        ll a,b;
        scanf("\n%c %lld %lld",&c,&a,&b);
        for(rect j:now){//遍历矩形 
            if(c=='X'){
                if(j.xx<a){
                    v.eb(j.x,j.y-b,j.xx,j.yy-b);
                }else if(j.x>=a){
                    v.eb(j.x,j.y+b,j.xx,j.yy+b);
                }else if(j.x<a&&j.xx>=a){//分成两半 
                    v.eb(j.x,j.y-b,a-1ll,j.yy-b);
                    v.eb(a,j.y+b,j.xx,j.yy+b);
                }
            }else if(c=='Y'){//Y的操作同上 
                if(j.yy<a){
                    v.eb(j.x-b,j.y,j.xx-b,j.yy);
                }else if(j.y>=a){
                    v.eb(j.x+b,j.y,j.xx+b,j.yy);
                }else if(j.y<a&&j.yy>=a){
                    v.eb(j.x-b,j.y,j.xx-b,a-1ll);
                    v.eb(j.x+b,a,j.xx+b,j.yy);
                }
            }else throw 1145141919810ll;
        }
        now=v;
    }
    rep(i,1,(int)now.size()){
        fa[i]=i;
    }
    rep(i,0,(int)now.size()-1){
        rep(j,i+1,(int)now.size()-1){
            if(touch(now[i],now[j])){
                merge(i+1,j+1);//相邻，合并 
            }
        }
    }
    rep(i,1,(int)now.size()){
        g[find(i)].eb(i);//把相同连通块的矩形分在一起 
    }
    vector<ll> ans;
    rep(i,1,(int)now.size()){
        if(g[i].empty())continue;
        ll tot=0;
        for(int j:g[i]){
            tot+=(now[j-1].xx-now[j-1].x+1ll)*(now[j-1].yy-now[j-1].y+1ll);//面积加在一起 
        }
        ans.eb(tot);
    }
    sort(ans.begin(),ans.end());//排序答案 
    printf("%d\n",(int)ans.size());
    for(ll i:ans){
        printf("%lld ",i);
    }
    return 0;
}

AC Submission