题解 P6677 【[COCI2019-2020#2] Checker】

☯☯枫☯☯ · 2021-04-27 15:50:14 · 题解

题目传送门

~~恶心的题目……~~

题目翻译有误：

第一行 T 不是数据组数，而应是该数据点属于哪个子任务。

题目分析：

其实这题没什么算法或者数据结构，主要考一个想法。

提供一个 \mathcal{O}(nlog(n)) 的算法。

问题1：能否构成三角剖分？

有两种做法：

第一种：时间复杂度：\mathcal{O}(nlog(n))

用 vector 邻接表存边，然后对于每一个点 i，按另一点的编号将边从小到大排序。我们称排序后从节点 i 出发的边中序号相邻的边为从 i 出发的相邻两边。

引理1：对任意凸多边形（后面的多边形均指凸多边形），一个合法三角剖分从任意一点 i 出发的任意相邻两边一定是该三角剖分中一个三角形的两边（即从点 i 出发的任意相邻两边必定能找到对应的第三边构成三角形）。

说明：

当这个剖分为合法的三角剖分时，根据合法三角剖分的定义，正确性显然。

当该剖分不合法时，此时一共只有 n-3 条对角线。我们从合法的三角剖分的基础上对边进行改变得到这个不合法的剖分。

在合法三角剖分的基础上改变部分的对角线，必定至少有一个三角形被破坏。因此存在一点 j，满足存在从 j 出发的相邻两边不能找到对应的第三边构成三角形。

得证。

综上所述，我们直接扫一遍所有的点，对以上条件进行判断即可。

注意：

由于已经对边排序，在找是否存在第三边时，可以二分。复杂度从 \mathcal{O}(n^2) 降至 \mathcal{O}(nlog(n))。

code:

inline int check(int x,int y){
    reg int l=0,r=f[x].size()-1,mid;
    while(l<=r){//二分查找 
        mid=l+r>>1;
        if(f[x][mid].d==y)return f[x][mid].col;//找到了 
        f[x][mid].d<y?l=mid+1:r=mid-1;
    }
    return 0;
}
inline int solve(){
    reg int ok=1;
    F(i,1,n){
        for(reg int j=1;j<f[i].size();++j){
            reg int col=check(f[i][j-1].d,f[i][j].d);//相邻两边 
            if(!col)return 0;//不存在第三边 
        }
    }
    return ok;
}

第二种：时间复杂度：\mathcal{O}(nlog(n))

记录边时同时记录开头和结尾。然后将所有边以开头（编号较小端点）为第一关键字，以结尾（编号较大端点）为第二关键字从小到大排序，用堆在线维护。

（由于本人没有这样写，就不贴代码了）

问题2：该三角剖分是否是“非常好”的？

引理2：若该多边形的三角剖分是“非常好”的，那么对于所有点 i 的所有相邻两边，颜色必定不同。

反证法:

假设有一个“非常好”的三角剖分，其中点 i 的一组相邻边 (x,y) 的颜色相同。

根据引理1，必存在对应的第三边 z，使得 x,y,z 三点构成一个三角形。在该三角形中至少有两边 x,y 颜色相同，与题意中“非常好”的三角剖分定义矛盾。

得证。

综上，对所有的点判断是否有相邻两边颜色相同即可。

code:

#define is_love(x,y,z) (1+((x)==(y) or (y)==(z) or (x)==(z)))
//判断是否有相同的颜色 
#define _max(x,y) ((x)>(y)?(x):(y))//手写的似乎比较快 
inline int solve(){
    reg int ok=1;
    F(i,1,n){
        for(reg int j=1;j<f[i].size();++j){
            ok=_max(ok,is_love(col,f[i][j-1].col,f[i][j].col));
        }
    }
    return ok;
}

时间复杂度：\mathcal{O}(n)

总时间复杂度：\mathcal{O}(nlog(n))

注意：

有没有发现上面问题1和问题2的代码很像？实际上，两个过程合并一下就好了（下面代码中会给出）。
第一行 T 不是数据组数，而应是该数据点属于哪个子任务……（考试的时候被坑死了……）
连边的时候应从编号小的连向编号大的。
记得把原多边形的边加进去！

终于到了~~喜闻乐见的~~代码时间：

#include<bits/stdc++.h>
#define reg register
#define F(i,a,b) for(reg int i=(a);i<=(b);++i)
inline int read();
using namespace std;
const int N=2e5+10;
int n;
char c[N];
struct P {
    int d,col;
    bool operator <(const P& a)const {
        return d<a.d;
    }
} ;
vector<P>f[N];//领接表 
inline int check(int x,int y){
    reg int l=0,r=f[x].size()-1,mid;
    while(l<=r){ //二分查找 
        mid=l+r>>1;
        if(f[x][mid].d==y)return f[x][mid].col; //找到了 
        f[x][mid].d<y?l=mid+1:r=mid-1;
    }
    return 0;
}
#define is_love(x,y,z) (1+((x)==(y) or (y)==(z) or (x)==(z))) 
//判断是否有相同的颜色 
#define _max(x,y) ((x)>(y)?(x):(y)) //手写的似乎比较快 
inline int solve(){
    reg int ok=1;
    F(i,1,n){
        for(reg int j=1;j<f[i].size();++j){
            reg int col=check(f[i][j-1].d,f[i][j].d); //相邻两边 
            if(!col)return 0; //不存在第三边 
            ok=_max(ok,is_love(col,f[i][j-1].col,f[i][j].col));
        }
    }
    return ok;
}
int main() {
    n=read(),n=read();
    scanf("%s",c+1);
    reg int x,y,z;
    F(i,1,n-3) {
        x=read(),y=read(),z=read();
        if(x>y)swap(x,y);//从编号小的连向编号大的 
        f[x].push_back({y,z});
    }
    F(i,1,n) {
        f[i].push_back({i==n?1:i+1,c[i]^48});
        //原多边形的边 
        sort(f[i].begin(),f[i].end());
        //按另一个端点的编号排序 
    }
    int ok=solve();
    if(!ok)puts("neispravna triangulacija");
    else if(ok==1)puts("tocno");
    else puts("neispravno bojenje");
    return 0;
}
inline int read() {
    reg int x=0;
    reg char c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x;
}

欢迎交流讨论，请点个赞哦~