P8216 [THUPC2022 初赛] 画图 题解

· · 题解

随便写了一发，交上来看一圈提交记录发现是最短解，看一圈题解区，怎么全是搜相交线段联通块，我不理解。所以来点无脑好写做法。

读题不需要理解题目给的那一大段条件是什么，先跳过。发现题目要求合并同向有交线段，两种方向可以只写一遍调用两次。为了可读性，分类型写。

注意到最后必然留下 7 条水平线和 8 条竖直线否则无解。于是考虑计算量为 7!\cdot8!\cdot O(chk) 的枚举全排列做法。发现将两个方向的线段分别重标号会好写很多，把题目的判断条件拉下来手改。最后还有个非同一字母不能有线段交的限制，直接统计总交点数与字母内交点数的差是否为零。

写完发现样例跑了 5s，于是将竖直线段之间单独的条件判断放在外面，用时直降到 100ms-。直接过了。

思考+编码时间：1.25h（花了 0.5h 考虑类型转化怎么写的简单点/qd ）
代码长度：1.81K 主播码风本来就这样没有刻意压行。
看不惯可以左转：LOJ 格式化 ver.

#include<bits/stdc++.h>
#define N 100005
#define F for(int i=1;i<=ns;i++)
using namespace std;
int n,nh,nv,ns,ih[N],iv[N];
struct hr{int l,r,y;}a[N];
struct vt{int d,u,x;}b[N];
struct sg{int s,t,p;}c[N];
bool operator<(const sg &a,const sg &b){if(a.p^b.p)return a.p<b.p;
    if(a.s^b.s)return a.s<b.s;return a.t>b.t;}
int s(){stable_sort(c+1,c+1+ns);int t=1;
    F if(c[i].p^c[t].p||c[i].s>c[t].t)c[++t]=c[i];
    else c[t].t=max(c[t].t,c[i].t);return t;}
int l[9],r[9],d[9],u[9],x[9],y[9];
int crs(int i,int j){return d[j]<=y[i]&&y[i]<=u[j]
&&l[i]<=x[j]&&x[j]<=r[i];}
int C(int lh,int rh,int lv,int rv){int c=0;for(int i=lh;i<=rh;i++)
    for(int j=lv;j<=rv;j++)c+=crs(i,j);return c;}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cin>>n;
    for(int i=1,s;i<=n;i++){cin>>s;
        if(!s)++nh,cin>>a[nh].l>>a[nh].r>>a[nh].y;
        else ++nv,cin>>b[nv].d>>b[nv].u>>b[nv].x;}
    ns=nh;F c[i]=(sg){a[i].l,a[i].r,a[i].y};nh=s();F a[i]=(hr){c[i].s,c[i].t,c[i].p};
    ns=nv;F c[i]=(sg){b[i].d,b[i].u,b[i].x};nv=s();F b[i]=(vt){c[i].s,c[i].t,c[i].p};
    if(nh^7||nv^8)cout<<"No\n",exit(0);
    for(int i=1;i<=8;i++)ih[i]=iv[i]=i;
    do{
        for(int i=1;i<9;i++)
            d[i]=b[iv[i]].d,u[i]=b[iv[i]].u,x[i]=b[iv[i]].x;
        if(d[2]^d[3]||u[2]^u[3]||d[4]^d[5]||u[4]^u[5])continue;
        do{
        for(int i=1;i<8;i++)
        l[i]=a[ih[i]].l,r[i]=a[ih[i]].r,y[i]=a[ih[i]].y;
        if(y[1]==u[1]&&l[1]<x[1]&&x[1]<r[1]
        &&d[3]<y[2]&&y[2]<u[2]&&x[2]==l[2]&&r[2]==x[3]
        &&d[5]==y[3]&&x[4]==l[3]&&r[3]==x[5]&&d[6]<y[5]
        &&y[5]==d[7]&&u[6]==y[4]&&y[4]==u[7]&&x[6]==l[4]
        &&l[4]==l[5]&&r[4]==r[5]&&r[5]==x[7]&&d[8]==y[7]
        &&u[8]==y[6]&&x[8]==l[6]&&l[6]==l[7]&&r[6]==r[7]
        &&!(C(1,7,1,8)-C(1,1,1,1)-C(2,2,2,3)-C(3,3,4,5)
        -C(4,5,6,7)-C(6,7,8,8)))cout<<"Yes\n",exit(0);
        }while(next_permutation(ih+1,ih+8));}
    while(next_permutation(iv+1,iv+9));
    cout<<"No\n",exit(0);
    return 0;
}