网站首页
编程语言
数据库
系统相关
其他分享
编程问答
Chords
2024-08-15
[ABC338E] Chords
原题链接题解对于\(a_i,b_i\),如果存在一个\(j\),使得\(a_j\in[a_i,b_i],b_j\notin[a_i,b_i]\),则存在交叉点即对于\([a_i,b_i]\)这一匹配,其内部的点也必然一一匹配,否则存在一个匹配点在外面,会导致交叉有点像括号匹配,我们可以用栈解决在这个思路下,我们要确保\(a_i<b_i\)
2024-07-16
[ABC338E] Chords 题解
思路思路还是很显然的,简单总结一下思路:首先,将圆环从点\(1\)到\(2N\)切开,并将其拉直成一条直线。在切开状态下,原来的弦变成了直线上的曲线。我们需要判断这些曲线之间是否存在交点。在切开状态下,曲线之间的交点等价于满足\(A_i<A_j<B_i<B_j\)的不同曲线\(i\)和