UOJ496 新年的新航线

Orz rushcheyo 当场AC

contest link
link

题解

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

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

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

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

下面所有的+都是循环意义下。


命题 对于一个n边形($n\geq 4$)的三角剖分,必存在一个点x使得x到x+3有边或x到x+4有边。
证明:

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$时边数不够,无法最后得到一个三角形。

所以成立。


对于$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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
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;
}
# 构造

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×