DisjointSemicircles

作者：穆皓远

关键词：分类讨论 异或 二分图染色

题目简述

给出2n个点，坐标分别为$(i,0)(0\le i<2n)$

有一些点对之间已经有连边

现在要给剩下的点配对

求是否存在一种方案，以配对的点为直径画n个半圆，使得所有半圆两两不交

$1\le 2n\le 50$

算法一

首先简化一下条件，半圆不交当且仅当所有同向（上/下）半圆的端点所组成的线段不交或包含

当未配对的点比较少的时候，我们可以强行枚举连边，然后做二分图染色

时间复杂度$O(\binom{m}{m/2}*(m/2)!*n^2)$（m为未配对的点的数量）

空间复杂度$O(n^2)$或$O(n)$

算法二

当未配对的点较多时，已配对的点较少，考虑强行枚举已配对点的半圆方向

对于未配对点，直接定方案比较有难度，我们考虑先定方向

下面给出一个定理：一个未配对点的方向方案能够成为合法的连边方案，当且仅当所有已配对点的半圆下，与它同向的点的个数为偶数（包括整个线段，可以假定外面有一个更大的圆）

证明：

充分性：

已配对点的半圆之间必然不交，只会相离和包含

如果相离，递归考虑即可

如果包含，对于一个半圆可以直接去掉它包含的半圆中的点，因为里面的点和外面的点肯定不能连边(删掉后点数仍是偶数)

然后只剩下一些未配对的点，从左到右贪心匹配即可（已经删掉的半圆不会对这一步造成影响）

必要性：

对于一个半圆，删掉包含的半圆中的点后，剩下的点只能两两配对，所以必为偶数

可以归纳出，半圆中的点数也为偶数，所以对于任意一个半圆，在它下面与它同向的点的个数为偶数

证毕。

有了这个定理，我们就只需定方向，问题可转化为：

有一个01序列$a_i$,给定一些形如$i,j,k$的条件，表示$a_i$到$a_j$的异或和为$k$

转为前缀和之后做二分图染色即可

时间复杂度$O(2^{m/2}*n^2)$（m为已配对的点的数量）

如果注意实现的细节可以做到$O(2^{m/2}*n)$,由于$m/2$最多为$25$,可以直接通过本题

算法三

结合以上两种算法，在$m \geq 38$时使用算法1否则使用算法2即可通过本题全部测试点