Orz rushcheyo 当场AC

contest link
link

题解

对于n=3的情况显而易见无解。

对于n=4或n=5的情况,图必有一个点直接连接其它所有点,可以直接得到一个菊花子图。

对于n更大的情况,可以通过一些方式来缩小这个图。

如果有解,容易发现每个点度至少为1。

下面所有的+都是循环意义下。
<details>
<summary>命题 对于一个n边形($n\geq 4$)的三角剖分,必存在一个点x使得x到x+3有边或x到x+4有边。</summary>
证明:

n=4或5显然。

考虑每次取一个最外层的三角形并把它切下来,会增加一条新边。

在还没有出现x到x+3的边或x到x+4的边的情况下,

如果另两条边都是切完新增的边,那么会切出一条x到x+4的边。

如果另两条边有恰好一条是切完新增的边,那么会切出一条x到x+3的边。

所以每次切三角形一定两条边都是原来的边,会减少两条边和一个点。

$\lfloor \frac{n}{2}\rfloor \geq n-3$,在$n\leq 6$时成立。

对于$n=6$的情况最后会得到一个由切下来的边构成的三角形,易知最后一次切的三角形可以当作切另一个三角形从而得到x到x+4的边

对于$n\gt 6$时边数不够,无法最后得到一个三角形。

所以成立。

</details>


对于$n\ge 5$的情况下,每次在剩余的图上重新编号。

找一条x到x+3的边,那么x,x+1,x+2,x+3这四个点会得到一个四边形,如果是x到x+2有边,那么生成树中x到x+1,x+2连一条边,否则x+3到x+1,x+2连边,最后删掉x+1和x+2。

或者找一条x到x+4的边,如果x到x+3,x+1到x+4没边,那么显然x+2到x,x+4都有边。此时生成树中加上x+1,x+2和x+2,x+3两条边,删掉x+1和x+3两个点。

每次删点,其它点要么度数不变,要么+2。易知剩下的图生成树上每个点度数>1,所以度数+2不会使得剩下图中可行方案变为不可行。于是图的规模会-2,归纳可得一定有解。

那么复杂度在于如何找到一个x。

考虑把所有点按顺序串成一个循环链表,在链表上遍历,找到满足条件的x后,加好边,删好点之后x向前跳3次,继续遍历。

由于找到x后,x+1对应的点会变,而(x-1)+1对应的点不会变。于是(x-4)+3,(x-4)+4都不会变。而(x-3)+4会变。

这样起始每个点最多会被遍历一次,而每次找到符合条件的x会有4个点可能多遍历一次,总共遍历复杂度为O(n),用set判断边是否存在,复杂度为$O(n\log n)$,如果用哈希表复杂度为$O(n)$。

//实际测试中set吊打tr1::unordered_set

set<int> e[500005];
int l[500005],r[500005];
void del(int x){
    x[l][r]=x[r];
    x[r][l]=x[l];
}
void work3(int &at){
    if(e[at].count(at[r][r])){
        write(at,' ',at[r],'\n');
        write(at,' ',at[r][r],'\n');
    }
    else{
        write(at[r][r][r],' ',at[r],'\n');
        write(at[r][r][r],' ',at[r][r],'\n');
    }
    del(at[r][r]);
    del(at[r]);
    at=at[l][l][l];
}
void work4(int &at){
    write(at[r][r],' ',at[r],'\n');
    write(at[r][r],' ',at[r][r][r],'\n');
    del(at[r][r][r]);
    del(at[r]);
    at=at[l][l][l];
}
signed main(){
#ifdef QAQAutoMaton 
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
#endif
    int n,u,v;
    read(n);
    if(n==3)return write("-1\n");
    for(int i=1;i<=n-3;++i){
        read(u,v);
        e[u].insert(v);
        e[v].insert(u);
    }
    for(int i=1;i<=n;++i){
        r[i]=(i%n)+1;
        l[(i%n)+1]=i;
    }
    int at=1;
    while(n>5){
        while(1){
            if(e[at].count(at[r][r][r])){
                work3(at);
                break;
            }        
            if(e[at[r]].count(at[r][r][r][r])){
                at=at[r];
                work3(at);
                break;
            }        
            if(e[at].count(at[r][r][r][r])){
                work4(at);
                break;
            }        
            at=at[r];
        }
        n-=2;
    }
    if(n==4){
        while(!e[at].count(at[r][r]))at=at[r];
        write(at,' ',at[r],'\n');
        write(at,' ',at[r][r],'\n');
        write(at,' ',at[r][r][r],'\n');
    }
    else{
        while(!(e[at].count(at[r][r]) && e[at].count(at[r][r][r])))at=at[r];
        write(at,' ',at[r],'\n');
        write(at,' ',at[r][r],'\n');
        write(at,' ',at[r][r][r],'\n');
        write(at,' ',at[r][r][r][r],'\n');
    }
    return 0;
}

标签: 构造

添加新评论