A Colourful Graph
给定一个不超过100个点的无向图，点有颜色，现在要改点的颜色，每次可以进行以下几种操作中的若干种。
- 将若干条边两边的节点的颜色交换
- 某条边两头的一个节点的颜色变成另一个节点的颜色
求在两万步内完成这些操作
解法
Tag: 暴力
按照下面顺序完成操作即可：
- 暴力交换某条链两端的颜色（至少有一边的颜色为对面的目标颜色）
- 暴力将某条链一端的颜色变成另一端的颜色（要求不能进行前面一种操作）
任意一项操作之后，颜色不对的点数至少减少1，同时每条操作至多产生200次交换，因而可以解决此题。
B Doors
题目大意
平面上有两堵墙，长度为无穷大，分别在\(y=0\)和\(y=w\)的位置上，每堵墙上\(x=[0, l]\)的地方上有一扇门，门的轴在\(x=l\)处，\(y=w\)与\(y=0\)的门开门的角度分别为\(A\)与\(B\)
现在有一个圆在\((-\infty , +\infty)\)的位置上，需要将它移动到\((+\infty , \frac{w}{2})\)处，问它的半径的最大值。
解法
Tag: 计算几何
分情况讨论：
Case 1: 两扇门的角度均大于90度。此时第一扇门仅需考虑门框，同时计算第二扇门与上面那堵墙的距离即可，答案为\((w - l\sin B)/2\)
Case 2: \(0\le A \le \frac{\pi}{2} \le B \le \pi\)，此时需要考虑的是第一扇门的门缝和第二扇门与上面那堵墙的距离，在1的基础上，答案还应与\((l\sin A)/2\)取小
Case 3: \(0\le A, B \le \frac{\pi}{2}\)，此时需要考虑门B与门A的距离，和门A转轴与门B的距离
Case 4: \(0\le B \le \frac{\pi}{2} \le A \le \pi\)，此时需要考虑门A转轴与门B的距离
C Playing with Numbers
题目大意
给定50000个形如\(2^a3^b, (0\le a, b\le 1000)\)的数，现在要对其进行以下两个操作：
- 取两个数A, B将gcd(A, B)放回去
- 取两个数A, B将lcm(A, B)放回去
现在要进行\(k\)次操作1，和\(N-k-1\)次操作2，顺序任意。你的任务是对于所有可能的\(k\)，求出最后得到的数的最大值与最小值。
做法
Tag: 数学
猜想1: 最大值与最小值最多只有3种
猜想2: 最大值的取得，一定是先进行若干次gcd，再进行若干次lcm，最小值的取法相反。
**猜想1的证明: ** 设\(A = \max(a), B = \max(b), A' = \min(a), B' = \min(B)\)，则最大值一定是\(2^A3^B\)，取得这个值最多需要两次lcm操作，而最小值一定是\(2^{A'}3^{B'}\)，取得这个值同样最多只需要两次gcd操作，因此显然最大值与最小值的取值最多只有3种。
**猜想2的证明: ** 如果某次lcm操作不在最后，那么将其放在最后答案不会变小，如果某次gcd操作不在最后，那么把它放在最后答案不会变大。
通过这两个猜想，我们发现问题在于，如果只进行一次gcd或者一次lcm，如何取得最小值与最大值。
解决这个问题并不难，只需要枚举最后gcd的那个数，或者lcm的那个数，进行计算即可。同时计算的时候只需要取\(log\)，因为通过枚举可以发现\(\forall a, b \in\{1, 2, \ldots, 1000\}, \mid a \log(2) - b \log(3)\right \mid \ge 10^{-3}\)
D Peak Tram
(TBD)
E Peak Tower
(TBD)
F Perfect k-ary Tree
(TBD)
G Scaffolding
(TBD)
H Slim Cut
(TBD)
I Special Tour
(TBD)
J Taboo
题目大意
给定若干个长度和不超过20000的字符串集合\(\{s_i\}\)，求一个最长的字符串\(S\)，使得任何\(s_i\)不为\(S\)的子串。
做法
Tag: 字符串, 数据结构
考虑AC自动机
对于此题，可以将\(\{s_i\}\)构建AC自动机，同时答案就是这个AC自动机删掉危险节点之后得到的图上的最长链，如果这个自动机上有环，那么答案就是无穷大。
找到这个最长链很简单，只需要bfs即可，我的做法是用SPFA找最长路。
K Team Up
题目大意
给定有300000个集合组成的一个有重集，集合之间只有包含关系和相等关系。
现在要求这个有重集的尽量多的不相交子集，使每一个子集的并集为全集。
做法
Tag: 大力出奇迹, 数据结构
注意到集合之间只有包含关系和相等关系，这提醒我们，集合之间是一个树形结构，考虑使用树的方式实现。
仍然注意到集合之间是树形结构，这提醒我们，可以对叶子节点打标记，从而得出每个集合的最小超集，即可构建出这个树。
现在将每一个集合安放在这棵树上，然后用并查集维护每一个节点，同时暴力维护即可，可以证明，最差的复杂度是\(O(n)\)的（考虑近似于一条链的情况，在这种情况下，每一个节点的元素个数相等，此时要合并\(O(n)\)次，同时注意到每一层处理完之后的元素个数是单调不增的，但同时我们也发现，对于其它的情况，复杂度也是类似的）
虽然这么说，但是比赛的时候谁会想那么多，不要怂就是干大不了20啊（比赛时候，可以认为整个过程类似于归并排序，复杂度不会大于\(O(n\log n)\)）