[ARC076E] Connected? 题解

zhanglile · 2023-07-22 13:35:48 · 题解

分析

不难发现题目给出的线可以分成三种:

1. 两点都不在边框上。
2. 一点在边框上。
3. 两点都在边框上。
   又因为题目给出的线是曲线所以第 1 种和第 2 种对答案没有影响，所以我们只需要讨论第 3 种。

第一种情况。 第二种情况。

随便画两个图就可以发现只要没有两条线相交，那么这个图就是合法的。
我们再把每条线的两端标上序号。

就能发现一个序列 112332
是不是很像括号序列 \texttt{( ) ( ( ) )}
那么我们只需要判断这个序列是不是合法的括号序列就能找出答案。
这不就是 P1944 最长括号匹配 的简化版。

code:

#include<bits/stdc++.h>
#define int long long
#define R read()
#define P printf
using namespace std;
inline int read(){
    int x = 0,f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f = - f;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - 48;ch = getchar();}
    return x * f;

} 
int n, m, p, st[1000005], top, tot;
struct node{
    int x, y, id, l;//分别表示 x 坐标 y 坐标编号顺时针离起点的距离 
}a[1000005];
bool cmp(node a, node b){return a.l < b.l;}
int len(int x,int y){
    if(y == 0) return x;//在左边 
    if(x == n) return n + y;//在下边 
    if(y == m) return n + m + n - x;//在右边 
    return n + m + n + m -y;//在上边 
}
signed main(){
    n = R;m = R;p = R;
    for(int i = 1;i <= p;++ i){
        int x1 = R, y1 = R, x2 = R, y2 = R;
        if(! ((x1 == 0 || y1 == 0 || x1 == n || y1 == m) && (x2 == 0 || y2 == 0 || x2 ==n || y2 == m))) continue; //排除第 1,2 种情况 
        a[++ tot] = node {x1, y1, i, len(x1, y1)};
        a[++ tot] = node {x2, y2, i, len(x2, y2)};
    }
    sort(a + 1, a + tot + 1, cmp);
    for(int i = 1;i <= tot;++ i)//使用栈判断序列合法 
        if(st[top] == a[i].id) -- top;
        else st[++ top] = a[i].id;
    if(top) P("NO");
    else P("YES");//朴实无华的输出 
    return 0;
}

蒟蒻第一次写题解，求过！