A. Apparently Make UTPC

考虑在 $C$ 当中 $A$ 和 $B$ 的位置关系，讨论每种情况，取其中字典序最小的即可：

• $A$ 完全被 $B$ 包含：可以用 KMP 判断。然后相当于把 $B$ 和剩下的字符排列使得字典序最小，也就是考虑 $B$ 的开头字符 $x$ 和第一个不等于 $x$ 的字符 $y$，如果 $y>x$，则所有小于等于 $x$ 的字符都应该排在 $B$ 之前；如果 $y< x$，则所有小于 $x$ 的字符都应该排在 $B$ 之前。

• $A$ 和 $B$ 不相交：也是把一些串排列使得字典序最小，一定是 $AB\le BA$ 时 $A$ 排在 $B$ 之前，剩下的字符和第一种情况类似。

• $A$ 和 $B$ 相交：不妨设 $A$ 的后缀和 $B$ 的前缀相交。满足条件的前后缀可以对 $BA$ 做 KMP 求出。首先需要满足 $C$ 当中有足够的字符，也就是这个 border 的长度必须大于某个值。接下来考虑如何比较两个 border 做为相交部分的字典序大小关系：

  • 根据之前的分析，一定存在某个 $x$ 使得小于等于 $x$ 的字符会排在 $A$ 之前（注意这里事实上有 $A$ 所有字符相同的情况，这时候只需要看 $B$ 中第一个不等于 $A_1$ 的字符），所以如果两个 border 相差的部分中有小于等于 $x$ 的字符，则较长的 border 一定更优。

  • 设两个 border 分别为 $S$ 和 $ST$，$B=STX$，如果 $T$ 当中没有小于等于 $x$ 的字符，则只需要比较 $TX$ 和 $X$ 的字典序大小（$X$ 可能是 $TX$ 的前缀，这时还需要往后比较，但这时多出来的字符一定可以拼出来等于 $TX$，所以选择 $X$ 不会更劣）。考虑 border 形成了 $O(\log |B|)$ 个等差数列，每一段当中要比较的串都形如 $T^kX$，字典序的最小值一定是在 $k$ 取最小或最大时取到。

    上述分析结合起来，可以得到统一的结论：当 border 长度满足字符数量的限制时，答案一定是在等差数列的端点处取到。

时间复杂度 $O((X+Y+Z)\log Y)$。还可以用 Z 函数实现 $O(1)$ 比较两个 border 的优劣（因为是 border，上面的 $S$ 一定是 $ST$ 的后缀，因此我们只需要比较 $STX=B$ 和 $SX$，其中 $SX$ 是 $B$ 的后缀，用 Z 函数即可 $O(1)$ 比较），做到线性复杂度。

B. Binary Tree Counting

有一个显然的 DP 做法是 $f(l_1,l_2,\mathrm{len})$ 表示先序编号在 $[l_1,l_1+\mathrm{len})$ 中的点对应中序编号 $[l_2,l_2+\mathrm{len})$，转移时枚举 $l_1$ 的中序编号，时间复杂度 $O(N^4)$。

观察：考虑二叉树和长度为 $2N$ 的合法括号序列的双射。合法括号序列可以唯一表示为 $(A)B$ 的形式，此时匹配的括号为根，$A$ 为根的左子树，$B$ 为根的右子树。在这个双射下，匹配的括号对应顶点，而第 $i$ 个左括号就是先序编号为 $i$ 的顶点，第 $i$ 个右括号就是中序编号为 $i$ 的顶点。问题转化为数长度为 $2N$ 的合法括号序列，满足第 $A_i$ 个左括号和第 $B_i$ 个右括号匹配。

我们可以根据 $A_i$ 和 $B_i$ 推出匹配括号之间的包含关系，建成一棵树，其中父亲包含孩子，孩子从左到右排序。在这棵树上树形 DP，求出 $f(x,i)$ 表示 $x$ 的子树内（通过添加一些括号）构成长度为 $2i$ 的合法括号序列（为了保证 $x$ 对应的左右括号是匹配的），且使得子树内的点都满足条件的方案数。对于每个 $f(x,i)$ 我们需要对所有孩子从左到右进行 DP，转移的系数就是两点之间向上或向右走且不能经过某条斜线 $y=x+d$ 的路径数，可以直接用组合数求出。

因为对孩子进行 DP 的复杂度是 $O(\mathrm{deg}_x\cdot N^2)$，所以总的复杂度是 $O(MN^3)$。但稍微分析一下会发现孩子的大小取值范围是有限的，如果相邻的两个孩子分别是 $(A_1,B_1)$ 和 $(A_2,B_2)$，那么 $(A_1,B_1)$ 的子树大小不能超过 $A_2-A_1-1$，$(A_2,B_2)$ 的子树大小不能超过 $B_2-B_1-1$，因此对一组 $(x,i)$ 进行 DP 的复杂度不超过 $O(\sum_{j}(A_{j+1}-A_j)(B_{j+1}-B_j))$。我们可以把它看成平面上的矩形 $[A_j,A_{j+1})\times[B_j,B_{j+1})$，会发现对于所有的 $x$，所有的矩形都是不交的，因此总的面积是 $O(N^2)$。还要考虑 $i$ 这一维，最终复杂度不超过 $O(N^3)$。

C. Convex Crusher

分类讨论凸包顶点数量 $m$：

• $m\le 2$：所有点共线，一定合法。

• $m\ge 4$：不合法。

• $m=3$：如果存在顶点以外的两个点 $P_i,P_j$ 满足直线 $P_iP_j$ 不经过任何一个凸包顶点，则选择这两个点和直线一侧的两个凸包顶点就是凸四边形。继续讨论：

  • 如果凸包内所有点共线：合法。

  • 如果不共线，设三个不共线的点是 $O,G,H$。不妨设 $OG$ 和 $OH$ 分别经过了 $A$ 和 $B$，则不可能 $G$ 在 $OA$ 上且 $H$ 在 $OB$ 上，否则 $ABHG$ 是凸四边形；都不在也不行。不妨设 $G$ 在 $OA$ 上，$H$ 在 $BO$ 的延长线上，则 $C,H,G$ 必须共线，否则 $BCHG$ 或者 $CAGH$ 是凸四边形。再这个基础上加任何一个点都会不合法，因此唯一的情况如下图所示：

    

除上图的情况以外，合法的集合可以看成选择一个点 $O$ 和三个方向，满足这三个方向不在同一个半平面（可以刚好差 $180^\circ$），选一个方向的所有点和另外两个方向的至多一个点。枚举点 $O$ 和选择所有点的方向 $v$，则另外两个方向一定是在 $v$ 两侧分别和 $v$ 的距离尽可能远，可以极角排序后双指针，时间复杂度 $O(N^2\log N)$。

上图的情况可以枚举 $O,G,H$，检查三条延长线上是否都有点，判断延长线上是否有点可以预处理，时间复杂度 $O(N^3)$。

D. Divisible by 11

观察：在十进制下，从低位数的所有偶数位（$10^0,10^2,\ldots$）的贡献是 $1$，所有奇数位的贡献是 $-1$，所以一个数模 $11$ 为 $0$ 当且仅当在模 $11$ 的意义下，奇数位的总和等于偶数位的总和。

先忽略首位非 $0$ 的限制，只需要再减去首位为 $0$ 的情况即可。设位数是 $N$，数字 $i$ 的出现次数是 $c_i$，数位和为 $s$，则要计算的就是 $$ \left\lceil\frac{N}{2}\right\rceil!\left\lfloor\frac{N}{2}\right\rfloor!\left[x^{\left\lfloor\frac{N}{2}\right\rfloor}y^{\frac{s}{2}\bmod 11}\right]\prod_{i=0}^{9}\left(\frac{1}{c_i!}\left(1+xy^i\right)^{c_i}\right)\bmod (y^{11}-1) $$ 注意我们先认为相同的数字是可以区分的，所以最后要除以 $c_i!$。模 $y^{11}-1$ 是因为总和是在模 $11$ 的意义下考虑的。

令 $F_i(x,y)=1+xy^i$，则关键的部分是求 $F(x,y)=\prod_{i=0}^9F_i(x,y)^{c_i}$。考虑对 $x$ 这一维递推，也就是对 $x$ 求导得到 $$ \frac{\partial F}{\partial x}=\sum_{i=0}^9 \frac{\partial F_i^{c_i}}{\partial x}\prod_{j\ne i}F_j^{c_j}=\sum_{i=0}^9c_i \frac{F}{F_i}\frac{\partial F_i}{\partial x}=\sum_{i=0}^9\frac{c_iy^iF}{1+xy^i} $$ 我们只需要同时维护 $F$ 和所有的 $\frac{c_iy^iF}{1+xy^i}$ 即可在 $O(10^2N)$ 的时间复杂度内计算答案。注意朴素实现的空间复杂度也为 $O(10^2N)$，但我们在递推中只需要保留最近的一项，可以优化空间到 $O(10^2)$。

E. Exchange or Not

观察：如果我们规定 $A_i=A_{i+1}$ 的时候不能交换，则每个不同序列对应唯一的操作方式。

现在相当于将原序列分成若干段，每一段的开头不断交换至结尾，因此要求段的开头只能出现一次。从后往前 DP，找到第 $i$ 个数右边第一个相同数的位置 $f_i$，则可以从 $[i+1,f_i]$ 转移到 $i$，用前缀和优化即可。时间复杂度 $O(N)$。

F. Finite Bracket Sequence

因为将左括号看作 $1$，右括号看作 $-1$ 时，合法括号序列总和一定为 $0$，所以当选择的区间总和非 $0$ 时，长度一定有上界。当总和等于 $0$ 时，端点选择前缀和最小值的位置即可找到任意长度的合法括号序列。只需要前缀和判断，时间复杂度 $O(N+Q)$。

G. Greatest Bracket Sequence

当长度有限时，设总和为 $s$，不妨设 $s>0$（通过翻转并取反），且除空前缀外的前缀和严格大于 $0$（通过循环移位）。这时如果一个子串跨过了两段的端点，则一定不可能是合法括号序列，因为端点之后的所有位置的前缀和都严格大于端点。因此这时合法括号序列子串直接就是原串的子串，不需要复制。

观察：这时极长的合法括号序列一定满足右端点是后缀最小值，左端点是下一个（靠左边的）后缀最小值 $+1$。

问题转化为了求所有后缀最小值之间的最大间隔，可以用倍增预处理后求解。注意上面考虑的都是循环移位之后的，实际我们可以看作将序列复制一遍之后求解，注意跨过端点的时候需要做一次特殊的询问（$R$ 之前第一个前缀和等于 $x$ 的位置），也可以用倍增求解。时间复杂度 $O((N+Q)\log N)$。

H. Heyawake-like Problem

如果我们将 $i-j\equiv 0\mod 3$ 的格子涂黑，则每一行和每一列的黑格数量就是 $N$ 或 $N+1$，我们考虑在这个基础上调整一下使得白格联通，且黑格数量满足要求。

当 $N$ 是偶数时，可以先考虑 $N=2,4$ 的解分别如下：

#..#..#
.#...#.
..#.#..
#.....#
..#.#..
.#...#.
#..#..#

...#..#..#..#
.#..#..#...#.
..#..#..#.#..
#..#..#.....#
.#..#...#.#..
..#..#.#...#.
#..#..#..#..#
.#...#.#..#..
..#.#...#..#.
#.....#..#..#
..#.#..#..#..
.#...#..#..#.
#..#..#..#..#

也就是我们先将副对角线也涂黑，和副对角线相邻的格子涂白，此时所有 $i\equiv 1\mod 3$ 的行和列有 $N+1$ 个黑格，其余行列有 $N$ 个黑格。要满足黑格的数量，只需要把副对角线上除首尾以外的满足 $i\equiv 1\mod 3$ 的格子涂白，但这会导致黑格和边界不连通。我们改为把副对角线上满足 $i\equiv 4\mod 6$ 的格子以及 $i+j=3N-10$ 且 $i\equiv 1\mod 6$ 的格子涂白即可。

当 $N$ 是偶数时，上面的构造就不成立了，我们考虑递归构造。事实上 $N$ 是偶数的情况也可以看作是递归构造，我们参考 $N$ 是偶数的情况，可以得到以下的构造方式：

• 如果有 $N$ 的解，满足倒数第 $7$ 行和最后一行是 $N+1$ 个黑格，并且这两行的第一个格子都是黑格，并且第一列和最后一行的黑格都在 $i\equiv 1\mod 3$ 的位置，我们在这个基础上向左和向下增加 $6$ 行和 $6$ 列，$i-j\equiv 0\mod 3$ 的格子用斜线铺满，其中左下角的部分用 $N=2$ 的解填充，最后将倒数第 $13$ 行的第一个格子涂白，就得到了一个 $N+2$ 的解且满足所有上述条件。

我们只需要找到一个合适的 $N=3$ 的解，例如：

#..#.....#
.#...#.#..
..#.#...#.
#..#..#..#
.#...#.#..
..#.#...#.
#.....#..#
..#.#..#..
.#...#..#.
#..#..#..#

I. Inversion Graph

J. Jelly

因为要求的是最大值，而幸福度也是取最大值，我们可以看作任选 $a-a'$ 和 $b-b'$ 的其中一个。这样的话所有食物有四种可能：$+a-a$，$+a-b$，$+b-a$，$+b-b$。也就是 $-a$ 之后必须是 $+a$，$-b$ 之后必须是 $+b$。

因为 $+a-a$ 和 $+b-b$ 的贡献都是 $0$，并且至少有一种可以插在任意位置，所以可以看作可以不选一些食品。剩下选了的食品一定是 $+a-b$ 和 $+b-a$ 交替，因此 $+b-a$ 的数量和 $+a-b$ 的数量至多差 $1$。把所有食品按照 $A_i-B_i$ 排序后，一定是最大的一些选 $+a-b$，最小的一些选 $+b-a$，并且一定是尽可能全选，因为如果剩至少两个，把它们选上的贡献是非负的。时间复杂度 $O(N\log N)$ 或者 $O(N)$。

K. Keep or Gamble

观察：最优策略是，设当前的分数是 $s$，把猫的分数看成 $-s$，则如果剩下的卡牌分数平均值为正选择操作 A，否则选择操作 B。

证明：操作 A 的贡献就是剩下卡牌的分数平均值，所以为正时一定选择操作 A。而注意到剩余卡牌分数总和一定是单调递减的，所以如果当前是负数，以后也是负数，所以选择操作 B。

分数为 $0$ 的熊猫可以直接忽略。最终答案可以看成每一步期望的总和，也就是 $$ \sum_{i=0}^U\sum_{j=0}^T\frac{{U\choose i}{T\choose j}}{U+T+C\choose i+j}\frac{\max\{0,2(U-i)+(T-j)-C(2i+j)\}}{U+T+C-i-j} $$ 枚举当前选了 $i$ 个独角兽和 $j$ 个老虎，乘积的第一项是到达这个局面的概率，第二项是这个局面下一次操作的期望。

枚举 $i+j=s$，则可以解出有贡献的部分是 $i\le t$，需要快速计算形如 $f(s,t)=\sum_{i=0}^t {U\choose i}{T\choose s-i}$ 的求和。注意到有递推式 $f(s+1,t)=\frac{f(s,t)\cdot (U+T-s)-{U\choose t+1}{T\choose s-t}\cdot (t+1)}{s+1}$。考虑组合意义，也就是在 $U+T$ 个物品里面选 $s$ 个，其中前 $U$ 个物品中至多选 $t$ 个。递推式的含义是，在选 $s$ 个的方案中，任意选择一个没选的物品，这时有可能导致前 $U$ 个物品中选了 $t+1$ 个，去掉这种情况后，剩下的每种方案恰好被算了 $s+1$ 次。由于限制 $t$ 关于 $s$ 是单调递减的，因此可以快速维护。还要计算形如 $g(s,t)=\sum_{i=0}^t{U\choose i}{T\choose s-i}i=U\cdot \sum_{i=0}^{t-1}{U-1\choose i}{T\choose s-1-i}$，维护方法和 $f(s,t)$ 一致。时间复杂度 $O(U+T)$。

N. Numerical Error

如果存在两个相同的数，则选择它们即可。否则所有数的总和不超过 $S=\sum_{i=1}^N\frac{1}{i}=O(\log N)$。枚举所有大小为 $\frac{N}{2}$ 的集合，如果集合数量至少是 $S\cdot 10^5+1$，则一定有两个的差不超过 $10^{-5}$。因此枚举足够多的集合，排序后判断即可。进一步发现有用的数的个数是 $O(\log( N\cdot 10^5))$，所以可以认为 $N$ 不超过 $O(\log (N\cdot 10^5))$。也就是可以认为 $N$ 不超过最小的 $N_0$ 满足 ${N_0\choose \frac{N_0}{2}}\ge H_{N_0}\cdot 10^5+1$，解出 $N_0=22$。

上面说明了当 $N\ge N_0$ 时一定有解，但我们还可以注意到，如果有解，则一定存在大小为 $\frac{N}{2}$ 的解：首先删除所有相同元素，这时大小不超过 $\frac{N}{2}$，然后添加一些相同元素即可。因此只需要枚举大小为 $\frac{N}{2}$ 的集合并排序，时间复杂度 $O(2^{N_0}\sqrt{N_0})$。也可以不排序，改为用大小为 $10^{-5}$ 的桶存放所有的总和，如果一个桶中有两个集合则找到一组解，否则最后只需要判断相邻的桶中的集合。

注意上述的复杂度都没有考虑比较，事实上存在极端数据使得两个集合的差值和 $10^{-5}$ 相差极小，但因为该题要求的是严格不超过 $10^{-5}$，理论上我们需要用精确的方法进行比较，这会带来至多 $\mathrm{poly}(N_0)$ 的因子。当然也可以先尝试用浮点数寻找不超过 $10^{-5}-\epsilon$ 的解，如果没找到再去判断浮点数差值不超过 $10^{-5}+\epsilon$ 的情况，实践中这并不会带来很大的开销。