A. Arrow a Row

一个串能通过操作得到的必要条件包括：

• 以 > 开头。
• 以 >>> 结尾
• 至少有一个 -。

而事实上上述条件也是充分的。如下是一个可能的构造：

• 当目标串不以 ->>> 结尾时，重复操作 $(n-4,5)$，这样可以视作删除了最后一个字符。最终目标串一定是以 ->>> 结尾。
• 枚举 $i$ 从 $1$ 到 $n-4$，如果 $s_i$ 为 - 则不操作，否则令 $j$ 为 $i$ 之后第一段连续的 - 的结尾位置，操作 $(i,j-i+4)$。

操作次数显然不超过 $n$，时间复杂度也为 $O(n)$。

B. Athlete Welcome Ceremony

先求出有 $x$ 个 a、$y$ 个 b、$z$ 个 c 的好序列，然后做一个三维前缀和，即可在 $O(1)$ 时间内回答询问。

令 $\mathrm{dp}(x,y,z,\mathrm{ch})$ 表示有 $x$ 和 a、$y$ 个 b、$z$ 个 c，且以 $\mathrm{ch}$ 结尾的好的前缀个数。因为前缀长度就是 $x+y+z$，枚举下一个字符即可 $O(1)$ 转移。

时间复杂度 $O(n^3+Q)$。

C. Chinese Chess

对状态集合（状态为 (位置，类型)）进行搜索，枚举询问的格点，然后根据距离分成若干个子集。实现后可以发现，即使对于全部位置都可行的情况，也只需要 $3$ 步即可确定类型。因此总的搜索节点数不超过 $90^3$，如果速度还是很慢，可以考虑打表 $3$ 步的所有决策，这样只需要搜索 $2$ 步以内的情况。搜索的时候可以顺便记录每个状态的决策。

实现时注意每种棋子的移动方式。

D. Closest Derangement

注意到当 $p_i\ne i$ 时，$\sum_{i=1}^{n}|p_i-i|\ge n$。

当 $n$ 是偶数时，最小值可以取到 $n$，且只在排列 $2,1,4,3,\ldots,n-1$ 取到。

当 $n$ 是奇数时，根据奇偶性，最小值为 $n+1$。可以在排列 $\ldots,2k+2,2k+3,2k+1,\ldots$ 和 $\ldots,2k+3,2k+1,2k+2,\ldots$ 取到（前后的部分和偶数时一样，相邻数两两对换）。这样的排列共 $n-1$ 个，现在我们要找到 $p_{q_1},p_{q_2},\ldots,p_{q_n}$ 的字典序第 $k$ 小，只需快速实现比较两个排列，然后调用 nth_element 即可。

比较两个排列 $p_1,p_2$ 只需找到最小的 $i$ 使得 $p_{1,q_i}\ne p_{2,q_i}$。注意到对于任意两个不同的好的排列，对应不同的位置一定是一个区间加上边界的 $O(1)$ 个零散点，只需在 $q^{-1}$ 上 RMQ，然后暴力统计零散点即可。

时间复杂度 $O(n\log n)$ 或 $O(n)$。

E. Disrupting Communications

要求的是和 $u$ 到 $v$ 的路径相交的连通块数。考虑用总的连通块数减去和 $u$ 到 $v$ 的路径不相交的连通块数。

令 $l=\mathrm{LCA}(u,v)$，则和 $u$ 到 $v$ 的路径不相交的连通块有以下两种：

• 完全在 $l$ 的子树外部。
• 完全在 $l$ 的子树内部，且连通块的根不在 $u$ 到 $v$ 的路径上。

令 $f(x),g(x)$ 分别表示以 $x$ 为根的连通块数和 $x$ 子树内的连通块数，则转移如下： $$ f(x)=\prod_{y\in \mathrm{ch}(x)}(1+f(y))\\ g(x)=f(x)+\prod_{y\in \mathrm{ch}(x)}g(y) $$ 同理，令 $f_o(x),g_o(x)$ 表示删除 $x$ 的子树，且以 $x$ 的父亲为根的树对应的答案。注意这里计算 $f_o(x)$ 不能使用除法（可能会有除以 $0$ 情况），而应该预处理前后缀乘积。

再令 $\mathrm{sum}_f(x)$ 为 $x$ 到根的路径上的所有点 $y$ 的 $f(y)$ 的和，则答案为 $$ g(1)-g_o(l)-g(l)+\mathrm{sum}_f(u)+\mathrm{sum}_f(v)-2\mathrm{sum}_f(l)+f(l) $$ 时间复杂度 $O(n+q\log n)$。

F. Double 11

对于一个分组方案，设每组的个数和总和分别为 $c_i$ 和 $s_i$。要在 $\sum_{i=1}^mk_i\cdot s_i\le 1$ 的前提下最小化 $\sum_{i=1}^m \frac{c_i}{k_i}$，一定有每组的 $\frac{\mathrm{d}(c_i/k_i)}{\mathrm{d}(k_i\cdot s_i)}$ 是相等的，即 $k_i$ 正比于 $\sqrt{\frac{c_i}{s_i}}$。令 $S=\sum_{i=1}^m \sqrt{c_is_i}$，则 $k_i=\frac{\sqrt{c_i/s_i}}{S}$，$\sum_{i=1}^m \frac{c_i}{k_i}=\sum_{i=1}^m \sqrt{c_i s_i}S=S^2$。因此题目所求的答案就是 $S$。

注意到确定每个分组的大小之后，每个系数 $\sqrt{c_i}$ 就确定了，因此一定是把较小的数分到较大的组。因此我们可以将数组排序，从而每一组一定是一个区间。

考虑排序后的三个区间 $(c_1,s_1),(c_2,s_2),(c_3,s_3)$（$s_1/c_1\le s_2/c_2\le s_3/c_3$）。事实上我们有如下不等式： $$ \sqrt{(c_1+c_2+c_3)(s_1+s_2+s_3)}+\sqrt{c_2s_2}\ge \sqrt{(c_1+c_2)(s_1+s_2)}+\sqrt{(c_2+c_3)(s_2+s_3)} $$ 一个证明如下：

• 移项，变为 $\sqrt{(c_1+c_2+c_3)(s_1+s_2+s_3)}-\sqrt{(c_1+c_2)(s_1+s_2)}\ge \sqrt{(c_2+c_3)(s_2+s_3)}-\sqrt{c_2s_2}$。
• 令 $c_1\gets c_1+c_2,s_1\gets s_1+s_2$，这不会改变作为前提的不等关系，只需证 $\sqrt{(c_1+c_3)(s_1+s_3)}-\sqrt{c_1s_1}\ge \sqrt{(c_2+c_3)(s_2+s_3)}-\sqrt{c_2s_2}$。
• 令 $a_i=s_i/c_i$，$f_i(x)=\frac{\partial\sqrt{(c_i+x)(s_i+a_3x)}}{\partial x}=\frac{a_3(1+2x)+a_i}{2\sqrt{(1+x)(a_i+a_3x)}}$，则上述不等式等价于 $\int_0^{c_3}f_1(x)\mathrm{d}x\ge \int_0^{c_3}f_2(x)\mathrm{d}x$，只需证明对任意 $x\ge 0$ 都有 $f_1(x)\ge f_2(x)$。再次求导会发现 $\frac{\partial f_i(x)}{\partial a_i}$ 在 $(0,a_3)$ 上恒为负，因此命题得证。

因此转移函数是 Monge 的，可以用 WQS 二分 + 决策单调栈在 $O(n\log n\log\epsilon^{-1})$ 的时间内求解。二分时需要注意精度问题，应当需要 long double。

G. Expanding Array

考虑序列中相邻的两个数 $x,y$。首先通过插入两个数的 XOR 可以得到序列 $x,y,x\oplus y,x,y$，也就是可以无限复制一对相邻的数，使得操作时不会将其消耗掉，因此我们可以把操作看成选中一对数 $(x,y)$，将 $(x,x\operatorname{op}y)$ 和 $(x\operatorname{op}y,y)$ 加入可能的相邻数的集合。不断重复这样的操作，最后就能得到所有可能出现的相邻数对，自然就能算出可能出现的不同数的个数。

接下来分析一下这样的数对的个数，序列中本身有 $n-1$ 对相邻的数，可以看作是独立的。对于相邻的两个数 $x,y$，因为进行的都是位运算，所以运算得到的任何一个数都可以看作两个位的一个函数 $f(x,y)$，其中 $x,y,f(x,y)\in\{0,1\}$，且 $f(0,0)=0$，因此至多有 $2^3=8$ 种可能。数对的数量自然不会超过 $8^2\cdot n$。事实上，打表可以发现这 $8$ 种可能的数都是可以产生的，因此直接枚举然后去重即可。

时间复杂度 $O(n)$ 或 $O(n\log n)$。

H. Friendship is Magic

先考虑如何计算一个 $f(x)$。当分割点向右移时，显然左侧单调递增，右侧单调递减。考虑找到最后一个左侧小于右侧的位置。即把 $x$ 划分为 $l,m,r$，其中 $m$ 是一个数位，满足 $10l+m\ge r$ 且 $l < m\cdot 10^{|r|}+r$，则 $f(x)=\min\{10l+m-r,m\cdot 10^{|r|}+r-l\}$。

现在考虑求 $f(x)$ 的和，枚举 $m,|r|$，然后枚举 $f(x)$ 取哪边，例如取 $10l+m-r$，则有限制 $$ 0\le l\le L\\ 0\le r\le R\\ 10l+m\ge r\\ l < m\cdot 10^{|r|}+r\\ 10l+m-r\le m\cdot 10^{|r|}+r-l $$ 把 $(l,r)$ 放到平面上，则这些限制都是半平面，且斜率只有 $0,\infty,10,1,\frac{11}{2}$ 这几种，通过分类讨论可以求出半平面交中所有点的 $l,r$ 之和，进而计算出答案。也可以直接枚举 $l$ 的奇偶性，使得斜率都是整数，然后找到半平面的所有交点并分段，每一段中固定 $l$ 的答案都是关于 $l$ 的二次函数，进而通过插值求总和。

时间复杂度 $O(|\Sigma|\cdot \log _{|\Sigma|}n)$，其中 $|\Sigma|=10$，且常数较大，需要精细实现。

I. Good Partitions

$k$ 是好的当且仅当对于任意 $i=1,2,\ldots,n-1$，如果 $i$ 不是 $k$ 的倍数，则 $a_{i+1}\ge a_i$。

也就是说，令所有满足 $a_{i+1}< a_i$ 的 $i$ 的 GCD 为 $d$，如果 $d=0$ 则 $k=1,2,\ldots,n$ 都是好的，否则只有 $d$ 的因子是好的。

单点修改会导致一些 $i$ 被插入或删除，可以使用线段树维护 GCD，并且预处理每个数的因子个数来快速回答询问。

时间复杂度 $O((n+q)\log n)$。

J. Grand Prix of Ballance

按照题意模拟即可。注意忽略掉非当轮比赛和消息和每位选手第二条及以后的消息。

时间复杂度 $O(n+m\log m+q)$。

K. Magical Set

令 $\Omega(x)$ 表示 $x$ 的质因子数量（计算重数）。设初始集合为 $S$，结束集合为 $T$，则总的操作次数不会超过 $$ \sum_ {x\in S}\Omega(x)-\sum_{x\in T}\Omega(x) $$ 而只要每次恰好除掉一个质因子，这个上界就是能够达到的。而事实上，只要 $S$ 和 $T$ 存在一个完美匹配（$x\in S$ 匹配 $y\in T$ 当且仅当 $y\mid x$），就一定存在达到这个上界的操作序列。具体来说，我们可以通过如下方法构造这个操作序列：

• 对于 $x\in S$，设 $M(x)$ 是完美匹配中和 $x$ 匹配的 $T$ 中的数。如果对于任意 $x\in S$，$M(x)=x$，则构造完成。否则找到 $M(x)\ne x$ 的最小的 $x$，令 $p$ 为 $x/M(x)$ 的任意一个质因子，然后重复以下过程：

  • 如果 $x/p\notin S$，则将 $x$ 变为 $x/p$，这就完成了一次操作。

  • 如果 $x/p\in S$，则说明 $M(x/p)=x/p$ 且 $M(x)\ne x/p$，我们可以交换 $M(x)$ 和 $M(x/p)$，然后令 $x/p$ 成为我们考虑的 $x$，重复这个过程。

    由于这个过程中 $x$ 不断变小，因此一定会终止。

因此，问题变成了为 $S$ 中的每个数 $x$ 选择一个因子 $y$，使得这些因子互不相同，且最小化它们的 $\Omega(y)$ 的和。我们找到每个数的所有因子，如果因子超过 $n$ 个，我们事实上只需要保留 $\Omega(y)$ 最小的 $n$ 个（即使有 $n-1$ 个被其他数选择，还会剩下一个），然后在 $x_S$ 和 $y_T$ 之间连一条边。

最终我们形成了一个左部 $n$ 个点，右部不超过 $n^2$ 个点，不超过 $n^2$ 条边的二分图，要找一个左部完美匹配，使得右部选择的点的 $\Omega(y)$ 之和最小。可以将右部的所有点按照 $\Omega(y)$ 从小到大排列，然后用匈牙利算法寻找匹配。这个算法的正确性来自于拟阵。而只要在未找到匹配时，不初始化算法中的 vis 数组，算法的复杂度就是 $O(|M|\cdot |E|)$，其中 $|M|$ 是匹配大小，$|E|$ 是边数。

时间复杂度 $O(n\sqrt {A}+n^3)$。

L. Recover Statistics

只需构造 $n=100$ 个数，前 $50$ 个数为 $a$，第 $51$ 到 $95$ 个数为 $b$，第 $96$ 到 $99$ 个数为 $c$，第 $100$ 个数为 $c+1$ 即可。

M. Two Convex Holes

注意到多边形的投影实际上只是多边形进行了平移和缩放，进行一些坐标变换后可以转化为两个多边形分别做匀速直线运动。进一步可以转化成多边形 $P_2$ 的速度为 $0$，$P_1$ 的速度为 $(0,1)$。

我们可以将多边形的面积以所有顶点的 $x$ 坐标分成 $O(n)$ 段，则每一段中多边形的上下边界都是线段。进一步容斥成 $($上边界 $-$ 下边界$)$，则只需要计算形如 $\min\{ax+b+t,cx+d\}$ 的函数的积分。这个函数可以按照 $t$ 分成三段，每段都是二次函数。因此面积可以表示成 $O(n)$ 段的分段函数，每一段都是二次函数。再预处理一下每一段的前缀和，询问时只需二分出端点所在的段，然后加上边界部分即可。

时间复杂度 $O((n+q)\log n)$。

A. Italian Cuisine

假设最后切的块是 $p_i$ 到 $p_j$，其中菠萝在直线 $p_ip_j$ 的左侧。

枚举 $i$，则 $j$ 应该在满足菠萝在直线 $p_ip_j$ 左侧的前提下尽可能大（我们认为 $p_{n+i}=p_i$，所以始终有 $j> i$）。这个 $j$ 要满足的条件具有单调性，并且当 $i$ 增大时，最大的 $j$ 也不降，所以可以用双指针维护这个过程。

算面积时只需求每条边的叉积的和。

时间复杂度 $O(n)$。

B. Generated String

考虑如果给的都是直接的串而不是一些子串的拼接怎么做。对所有串建立 Trie，则 $s$ 是 $t$ 的前缀当且仅当 $t$ 在 $s$ 的子树中，在 DFS 序上就是 $t$ 在一个区间内。对反串建立 Trie 就可以解决后缀。因此询问给定前缀后缀的串的个数实际上就是一个二维偏序，加上时间维度之后就是三维偏序，可以在 $O(n\log^2 n)$ 时间内解决。

现在变成给一个子串的拼接，唯一的区别就是没法直接建 Trie。只要我们能够把 Trie 建出来，后面的做法没有区别。事实上建立 Trie 也并不复杂，只需要将所有串按字典序排列，然后求出相邻两个的 LCP 长度，然后类似建虚树的方法，就能建出这些串的压缩 Trie。注意这里排序的时候，如果只是用后缀数组求 LCP 跳过一段，比较复杂度是 $O(k+l)$，其中 $k,l$ 分别是两个字符串的段数，则复杂度仍然可能达到 $\Omega (n^2)$。一个解决方法是，使用归并排序，并且递归过程中也计算相邻串的 LCP，然后在归并的过程中，利用已经计算的 LCP 避免重新从头开始比较。另一个解决方法是按照段数从小到大插入排序。在预处理后缀数组，支持 $O(1)$ 求 LCP 的前提下，两种方法的复杂度都是 $O(\sum k_i \log n)$。

总时间复杂度 $O(n\log n+q\log ^2q+\sum k_i\log q)$。

C. Permutation

考虑分治，每次将数列分成两半，然后确定每个数在哪一半。之后递归处理两个区间。

由于这道题的交互器是非适应性的，即排列是预先确定的，所以可以采用随机化。考虑将所有数 shuffle，然后每次询问两个数 $x,y$，前一半是 $x$，后一半是 $y$（区间以外的部分随便用 $x$ 或 $y$ 填充，不会有贡献）。答案有三种可能：

• 答案是 $0$，说明 $x$ 在后一半，$y$ 在前一半。
• 答案是 $1$，说明 $x,y$ 在同一侧，但不知道是哪一侧。
• 答案是 $2$，说明 $x$ 在前一半，$y$ 在后一半。

对于答案是 $0,2$ 的情况，能够直接确定两个数。对于答案是 $1$ 的情况，可以删掉 $x,y$ 的其中一个，用另一个继续进行询问。

分析一下询问次数，因为排列随机，近似可以看成每个数均匀独立在左右之间随机。每次询问有 $1/2$ 的概率确定 $2$ 个数，$1/2$ 的概率确定 $1$ 个数，因此每次期望确定 $3/2$ 个数，故期望询问次数约为 $2n/3$。

因此总的询问次数大约为 $\frac{2}{3}n\log n$。加上一些剪枝（例如当一侧已经满时不继续询问）后，实测 $n=1\,000$ 时大约需要 $6\,000$ 次询问。

D. Collect the Coins

二分答案，可以在线性时间内判断能否满足。

考虑按照时间从前往后，维护每个时刻，两个机器人可能的位置集合。事实上，一定可以表示成其中一个机器人在 $[l_1,r_1]$，另一个在 $[l_2,r_2]$（不区分两个机器人）。

初始时两个区间都是 $[1,10^9]$。对每个事件进行模拟：

• 当时间前进 $t$ 时，两个区间都往两侧扩展 $v\cdot t$。
• 当在位置 $c$ 出现一个硬币时：
  • 如果没有区间包含 $c$，则不可能。
  • 如果有一个区间包含 $c$，则对应区间变成 $[c,c]$。
  • 如果两个区间都包含 $c$，则任何一个机器人都可以收集硬币，而另一个机器人可能的位置是 $[l_1,r_1]\cup [l_2,r_2]$。因为两个区间有交，因此结果还是一个区间。

时间复杂度 $O(n\log C)$。

E. Normal Friends

不妨设线段树大小为 $n+1$，且根的分割点为 $n$。这样做的好处是，对于区间 $[1,x]$ 的翻转操作等价于找到 DFS 序第 $x+1$ 个叶子，然后将其到根的路径上的所有左子树整体翻转（最高的变到最低的，依此类推），并且内部所有左右儿子交换。

这样的操作实际上可以用 LCT 来完成。首先考虑怎么找到这条链，分成两步，分别是找到 DFS 第 $x+1$ 个叶子和对其进行 access 操作。

第一步需要在每条实链上用 splay 额外维护所有点的左/右子树（按照深度），以及哪些点有左/右儿子（当然是通过维护子树内有多少个点有左/右儿子）。这里我们假设每条实链的底端都是叶子。找 DFS 第 $k$ 个叶子的步骤如下：

• 令 $L=$ (所有左子树中叶子个数的和)。
• 如果 $k\le L$，则在所有左子树中找到第 $L$ 个叶子所在的子树，然后递归。
• 如果 $k=L+1$，则第 $k$ 个叶子就是这条链的底端。
• 如果 $k>L+1$，则在所有右子树中找到（自底向上）第 $L$ 个叶子所在的子树，然后递归找其中的第 $k-L-1$ 个叶子。

找到叶子之后，我们需要进行 access 操作，具体步骤如下：

• 我们不对每条链记录它的父亲（因为之后会有翻转操作，父亲没法维护），而是在找叶子的过程中，记录经过的路径，并且找到每条链切换时要接上的父亲。也就是找到链上第 $k'$ 个有左/右子树的结点。
• 自底向上，如果要把 $x$ 接上 $y$，首先要将 $y$ 和其目前的儿子 $z$ 断开。在这同时需要将左/右儿子同时分成两部分，对应断开之后的两条链，并把 $z$ 加入左/右儿子的列表（在这里更新 $z$ 的子树叶子数）。
• 将 $x$ 从 $y$ 所在链的左/右儿子列表中删除，将 $y$ 和 $x$ 所在链的左/右儿子列表拼接，并将 $x$ 接到 $y$ 上。

经过上面的两个步骤我们得到了一条链，询问的答案就是链的左子树的个数。下一步就是将链的左子树翻转，这又分成两个部分：

• 首先是将左儿子的列表整体翻转，这可以直接通过打翻转标记实现。
• 对每个左/右儿子，将其子树镜像，这对应着交换它所在链的左/右儿子列表，并且镜像它的所有左/右儿子，同时维护的信息（有多少个点有左/右子树）也需要交换。这里我们采用对链整体打标记，在找叶子的过程中处理标记。

注意翻转左儿子列表的操作会较大影响树的形态，但是 LCT 的 access 次数的分析并不会失效（每次操作只会影响 $O(\log n)$ 条轻边）。splay 的复杂度不再能沿用 LCT 的证明，但至少有上界 $O(\log n)$，总复杂度不超过 $O((n+q)\log ^2n)$，并且实际表现其实比较快。

F. Triangle

设三个串中字典序最大的为 $x$，其余两个为 $y,z$，则显然有 $xy>z$ 和 $xz>y$，因此只需要满足 $yz>x$ 或 $zy>x$。我们可以假设 $yz\ge zy$，这等价于 $y^\infty\ge z^\infty$，因此只是添加了一维偏序的限制。

现在要求 $yz>x$，而我们限制了 $y\le x$，因此 $y$ 一定是 $x$ 的一个前缀。我们可以枚举 $x,y$，总的枚举次数不会超过总串长。记 $x$ 去掉前缀 $y$ 后的串为 $y^{-1}x$，则 $z$ 只需要满足以下两个条件：

• $z^\infty\le y^\infty$。
• $x\ge z>y^{-1}x$。

对于后者，可以直接对所有串后缀排序。

对于前者我们需要将所有串按照这个规则排序。注意这里直接比较 $yz$ 和 $zy$ 的大小来排序，总的复杂度可以达到 $\Omega(n^2)$。一个复杂度正确的方法是，先判断两个串是否互为前缀，如果不是则可以直接比较，否则通过预处理的 $z$-函数/后缀数组，可以 $O(1)$ 求出 LCP 然后比较。这样单次比较复杂度是 $O(\min\{|y|,|z|\})$ 而不是 $O(|y|+|z|)$，总复杂度就是正确的 $O(\sum|S_i|\log n)$。

处理完这两个限制之后，就变成了二维偏序，可以在 $O(n\log n)$ 时间内解决。

需要注意的是，输入中会出现相同的串，所以我们需要记录每个串的出现次数，并且处理好三个串有相同的情况。

总时间复杂度 $O(\sum |S_i|\log n)$。

G. Stop the Castle 2

将问题转化为放 $m-k$ 个障碍，隔开尽可能多可以互相攻击的车。

只有在一行或者一列相邻的车才能互相攻击，这样的车只有 $O(n)$ 对。在它们之间的任意位置摆放障碍就能防止它们互相攻击。设有 $c$ 对能互相攻击的车之间能摆放障碍。

有的障碍可以阻挡两对车互相攻击（行列各一对），显然我们需要让这样的障碍尽可能多。假设我们能摆放 $x$ 个障碍，每个障碍都能阻挡互不相同的两对车，那么放 $m-k$ 个障碍就能阻挡 $\min\{c,m-k+\min\{m-k,x\}\}$ 对互相攻击的车。

把互相攻击的车看成点，如果一个障碍能阻挡两对车，就在对应的两个点之间连边，会形成一个二分图。$x$ 就是这张图的最大匹配。可以用 Dinic 算法或 Hopcroft-Karp 算法在 $O(m\sqrt n)$ 的时间中求解。

H. Intersection of Paths

如果 $k=1$，则所求的就是树的直径。当 $k$ 任意时，要求的其实就是只考虑两侧点数都不少于 $k$ 的边时树的直径。

注意所有询问互不相关，因此我们可以将询问按照 $k$ 从大到小的顺序重新排列。当 $k$ 减小时，会陆续加入边，这些边形成一个连通块，如果询问没有修改时，可以直接维护这个连通块的直径。当询问有修改

时有不同的做法，这里介绍其中的两个：

• 由于树的边权几乎不变，我们将询问中修改的边删除，分成两个连通块，分别求出两个连通块的直径，然后合并即可（整棵树的直径端点一定在这两条直径的端点中）。需要支持加点和求子树的直径，在按 DFS 序建立的线段树上合并直径即可。需要 $O(1)$ LCA。
• 直接使用修改边权的动态直径做法。直径等于在欧拉序上依次选 $3$ 个点（可以相同）$u,v,w$，$\mathrm{dep}_u-2\mathrm{dep}_v+\mathrm{dep}_w$ 的最大值。修改边权对欧拉序上深度的影响就是区间加。用线段树维护这个式子每一段的最大值即可。

时间复杂度 $O((n+q)\log n)$。

I. Find Yourself

首先注意到，任意的树都是能够确定的：

• 因为树是二分图，所以我们可以黑白染色，先确定怪物所在点的颜色，不妨设和根相同（否则走一步）。
• 假设怪物目前在 $x$ 的子树中且与 $x$ 颜色相同的一个结点（初始 $x$ 为根）。如果 $x$ 是叶子则游戏结束。否则，重复以下过程，直到 $x$ 只剩下一棵子树：
  • 询问 $x$，如果怪物在 $x$，那么游戏结束。否则，怪物只能走到 $x$ 的子树中，与 $x$ 颜色不同的结点。此时询问 $x$ 的一棵子树，如果怪物不在子树中，就可以删除这棵子树，否则可以删除所有其他子树。此时怪物又可能位于 $x$ 的子树中，未被删除的，和 $x$ 颜色相同的任意结点。
• 当只剩下一棵子树 $y$ 时，询问 $x$，如果怪物在 $x$，那么游戏结束。否则令 $x\gets y$，重复以上过程。

接下来考虑有环的情况。首先要注意到，如果图 $H$ 是不能确定的，则任意包含子图 $H$ 的图都是不能确定的。结合样例和打表观察，可以发现，以下的图都是不能确定的：

• 大小不为 $4$ 的环。
• 四元环，每个点都都和其他点有边。
• 四元环，相邻两个点分别连有长度为 $2$ 的链。
• 四元环，相邻三个点依次连有长度为 $2,1,2$ 的链。

此时可以看出，能确定的图的每一个点双都应该是四元环，或是多条长度为 $2$、起点终点相同的路径并起来的“纺锤”图。为了进一步地简化图的结构，我们还可以观察到如下性质：

• 如果存在两个二度点 $a,b$，它们的邻居相同，则可以删除其中的一个和其邻边，而不改变答案。
  • 证明：设原图为 $G$，$a,b$ 的邻居都是 $c,d$，删掉 $b$ 和其邻边之后的图为 $G'$。显然如果 $G$ 可以确定，则 $G'$ 可以确定。反过来，如果 $G'$ 可以确定，则使用相同的策略，可以在某一次询问后，确定怪物在 $a,b$ 其中的一个，然后怪物走一步之后只可能在 $c,d$，因此再询问一下 $c$ 即可确定怪物的位置。

经过上述变换之后，可以发现，能确定的图的每个点双都只能是四元环，且四元环不能有两个点都连有长度为 $2$ 的链，也不能四个点都和其他点有边。

事实上，上述必要条件也是充分的。

• 证明：满足上述条件的图，一定存在一个点，将这个点作为根时，每个四元环除了根以外的三个点中，至多有两个点连接了一个或多个叶子，另一个点没有和环外的点连边。设环上的点按顺序为 $a,b,c,d$，其中 $a$ 是根。我们可以先利用树的做法，将问题缩小到在 $a$ 的这个子树内确定怪物的位置。讨论两种情况：

  • $b,d$ 分别连有叶子 $b',d'$（可能多于一个）。先询问 $a$，如果不在 $a$，则下一步只可能在 $b,d$，再询问 $b$ 即可确定。

  • $b,c$ 分别连有叶子 $b',c'$（可能多于一个）。先询问 $a$，如果不在 $a$，则下一步只可能在 $b,d,c'$。再询问 $b$，如果不在 $b$，则下一步只可能在 $a,c$，再询问 $a$ 即可确定。

    因此满足上述条件的图都能够确定。

图的变换和判断上述条件都可以在 $O(n+m)$ 时间内完成，因此整个题可以在 $O(n+m)$ 时间内解决。

J. Sheriruth

如果一个点有两条出边 $u,v$，则 $u,v$ 会互相连边。如果 $u$ 或 $v$ 还有出边，会和 $u,v$ 整个连成一个团。以此类推，$u,v$ 可以到达的点都会形成一个团。不断合并这些团，最后整张图的每个连通块只有以下几种可能：

• 内向树。
• 内向基环树。
• 一个团，还有若干内向树，每棵树的根连向了团中的若干个点。

内向树的情况只需要判断祖先后代关系。内向基环树的情况还需要判断点在环上。

大小为 $s$ 的团的方案数就是 $\sum_{i=0}^{s-2}(s-2)^{\underline i}$。如果是从树根走到团上，要讨论走上来的点是否直接是 $v$，如果是则只有 $1$ 种方案。这个式子只需要对每个团单独计算，大小总和不超过 $n$。

总时间复杂度 $O((n+m+q)\log n)$，$\log n$ 在于排序和二分判断是否有某一条边，也可以做到线性。

K. Palindromic Polygon

首先将点复制一遍，变成 $2n$ 个点的序列。相当于可以选一个子序列 $i_1< i_2< \cdots< i_k$，要求 $i_k-i_1< n$，且 $f_{i_1},f_{i_2},\ldots,f_{i_k}$ 是回文序列，最大化凸包的面积。

考虑从两侧向中间 DP，设 $f(l,r)$ 是当前回文序列中对应位置是 $l,r$ 的最大面积。转移需要枚举 $i,j$，满足 $l< i\le j< r,f_i=f_j$，然后转移到 $f(i,j)$。这样做时间复杂度是 $O(n^4)$。

注意到如果 $(l,i)$ 和 $(j,r)$ 之间都有等于 $f_i$ 的点，那么把这两个点选上，面积一定不会变小（相当于凸包上多了两个三角形），因此有用的转移都满足 $i$ 是区间中第一个等于 $f_i$ 的点或 $j$ 是区间中最后一个等于 $f_i$ 的点。这样对于每个区间有用的转移减少到了 $O(r-l)$ 个，时间复杂度 $O(n^3)$。

L. Cosmic Travel

考虑查 $l=r$ 时如何查询。对所有 $a_i$ 建立 Trie，然后从根开始，如果 $l$ 的对应位为 $1$ 则交换了两棵子树，然后如果 $k\le$ (左子树大小)，递归左子树，否则递归右子树。

查询一个区间 $[l,r]$ 时，类似线段树的方式，按对应位分成两个区间，分别递归。我们只需要在 $[l,r]$ 恰好是一个完整的区间时快速回答。即对于每棵子树，对每个 $1\le k\le$ (子树大小)，预处理对 $j\in [0,2^d)$，$a_i\oplus j$ 的第 $k$ 小的和，其中 $d$ 是子树的位数。需要预处理的值，每个深度是 $O(n)$ 个，因此总共只有 $O(n\log C)$ 个。每个需要预处理的值都可以通过其孩子的值在 $O(1)$ 时间内得到。

总时间复杂度 $O((n+q)\log C)$。

M. The Quest for El Dorado

考虑 Dijkstra，将每个点的距离定义为 $(i,x)$，即最早在第 $i$ 轮才能到达，并且第 $i$ 轮至少走了 $x$ 的距离。显然我们希望 $i$ 尽可能小，并且 $i$ 相同的情况下 $x$ 尽可能小。

对于每条边 $(v,c,l)$，如果 $a_i=c$ 且 $x+l\le b_i$，那么新的距离是 $(i,x+l)$。

否则，我们需要找到最小的 $j>i$，满足 $a_j=c$ 且 $b_j\ge l$，新的距离就是 $(j,l)$。找这个 $j$ 可以用线段树或者二分 RMQ。

总时间复杂度 $O((n+m+k)\log (n+m+k))$。

A. An Easy Geometry Problem

令 $A_i'=A_i-i\cdot \frac{k}{2}$，则对于 $i$，$r$ 是好的半径当且仅当 $A'_{i+r}-A'_{i-r}=b$。

用线段树或树状数组维护正反两个方向的哈希值，询问时二分长度然后比较哈希值即可。

时间复杂度 $O(n+q\log^2n)$。

B. Counting Multisets

考虑 $p(S)$ 是奇数的条件，设 $\mathrm{cnt}(x)$ 是 $x$ 在 $S$ 中的出现次数，则 $p(S)=\frac{n!}{\prod_x \mathrm{cnt}(x)!}$。根据 Lucas 定理，$p(S)$ 是奇数当且仅当所有 $\mathrm{cnt}(x)$ 在二进制下相加没有进位。因此，合法的可重集就是对于 $n$ 的二进制中每个 $2^i$，任意选择一个 $x$ 重复 $2^i$ 次。

现在还要解决 $\mathrm{OR}_{x\in S}x=y$ 的条件。可以通过容斥将条件改写为 $\forall x\in S,\mathrm{bin}(x)\subset \mathrm{bin}(y)$（$x$ 的二进制中的 $1$ 是 $y$ 的子集）。

因此，对于固定的 $y$，只需要计算对于每个 $2^i\in \mathrm{bin}(n),2^j\in \mathrm{bin}(y)$，可以选或不选 $2^{i+j}$，总和等于 $x$ 的方案数。这可以通过数位 DP 解决，即 $f(i,j)$ 表示确定最低 $i$ 位，目前进位为 $j$ 的方案数，时间复杂度 $O(\log x\log n\cdot \mathrm{pcnt}(y))$。

总时间复杂度 $O(2^{\mathrm{pcnt}(y)}\mathrm{pcnt}(y)\log x\log n)$。

C. Counting Strings

（复读官方题解）

首先把条件改写成 $\gcd(r,r-l)=1$。建出 SAM，对于每个 $r-l$，假设保留所有 $\gcd(r,r-l)=1$ 的 $r$ 对应的结点，这样的串的个数就是这些结点到根的路径的并中深度为 $r-l$ 的点数。如果我们把这些结点按 DFS 序排序，则容易维护这些路径的并。

考虑通过搜索枚举 $r-l$ 包含质因子的集合来优化这个算法。在加入一个素数 $p$ 时，要删除所有 $p\mid r$ 的 $r$ 对应的结点，这样的删除对路径并的变化是删除一条链，可以用链表维护前驱后继，求两次 LCA 就能找到这条路径。回溯时撤销修改即可。为了统计答案，我们维护每个深度的点数，修改的影响是区间加，查询是单点求值，可以用 $O(1)$ 修改 $O(\sqrt n)$ 查询的分块维护。

接下来只需要分析这样搜索时需要修改的次数 $F(n)$。实测在 $n=10^5$ 时，修改的次数不超过 $2\cdot 10^7$。具体的分析是，修改次数等于 $\sum_{x=1}^{n-1}[\mu(x)\ne 0]\frac{n}{\mathrm{maxp}(x)}$，其中 $\mathrm{maxp}(x)$ 是 $x$ 的最大素因子。

时间复杂度 $O(F(n)+n\sqrt n)$。

D. Bracket Sequence

考虑 DP 计算一个给定字符串 $s$ 的方案数。$f(i,j)$ 表示 $S[0:i]$ 中等于 $\mathbb{()}^\infty[0:j]$ 的子序列的方案数，则答案就是 $f(|s|,2k)$。

令 $K=\max \{k\}$。对于第 $1$ 类区间询问，我们可以把这个 DP 写成 $v\cdot M_lM_{l+1}\cdots M_r$，其中 $M_i$ 是 $s_i$ 的转移矩阵。由于矩阵的特殊性质，可以在 $O(K^2)$ 的时间内计算一个矩阵乘上 $M_i$，因此只需要预处理 $M_1M_2\cdots M_i$ 和 $(M_1M_2\cdots M_i)^{-1}$，就可以在 $O(K)$ 时间内回答一个询问。

对于第 $2$ 类区间询问，首先可以添加一个 DP 状态，表示还没有进入子串，同时预处理 $M_1M_2\cdots M_i$ 的前缀和即可。

总时间复杂度 $O(nK^2+qK)$。

E. Dominating Point

令 $S(u)=\{v\mid (u,v)\in E\lor u=v\}$。点 $u$ 是支配点当且仅当不存在 $v\ne u$ 满足 $S(u)\subset S(v)$。

把所有点按度数从大到小排序，依次检查是否存在这样的 $v$。显然我们只需要检查已经确定是支配点的 $v$，而找到三个支配点后就可以直接返回，因此对于每个 $u$ 只需检查 $O(1)$ 个点，每次检查 $O(n)$。

总时间复杂度 $O(n^2)$。

F. An Easy Counting Problem

因为 $p$ 是素数，由 Lucas 定理可知组合数是 $p$ 进制下每一位组合数的乘积。$0\le b\le a< p$ 的组合数分布可以 $O(p^2)$ 暴力计算。

求出一位的组合数分布后，我们要计算其在 $i,j\to i\cdot j\bmod p$ 卷积意义下的 $k$ 次幂。通过找一个原根并将下标取离散对数的变换，我们可以将其转化为普通的循环卷积，可以用 FFT 优化。

时间复杂度 $O(p^2+p\log p\log k)$。

G. An Easy Math Problem

我们加上 $\gcd(p,q)=1$ 的限制，不同的 $(p,q)$ 就对应了不同的 $r$。考虑计算这样的 $(p,q)$ 的方案数。显然方案数是积性的，即每个素数独立，且 $p^k$ 的方案数是 $2k+1$（$(1,1),(p^i,1),(1,p^i)$）。分解 $n$ 之后直接计算即可。

可以预处理素数来加速分解，时间复杂度 $O(\sqrt N+q\frac{\sqrt N}{\log N})$。

H. Elimination Series Once More

我们对每个 $i$，和每个 $j=1,2,\ldots,n$，来计算 $i$ 能不能赢下第 $j$ 轮，也就是能不能让 $a_i$ 变成其所在的大小为 $2^j$ 的子树的最大值。

只需要判断两个条件：

• 所在子树中大于 $a_i$ 的不超过 $k$ 个。每次最多只能把一个换出去。
• $a_i\ge 2^j$。这是为了保证有足够多小的数放进子树。

这个条件可以在归并排序的过程中快速判断，时间复杂度 $O(n2^n)$。

I. Max GCD

我们枚举 $\gcd=d$，看是否能用 $d$ 的倍数满足条件。显然对于固定的 $j$，$i$ 应该越大越好，$k$ 在满足 $k-j\ge j-i$ 的前提下越小越好。

考虑从大到小枚举 $j$，找到对应的 $i$ 和 $k$。$i$ 可以直接找到，但 $k$ 并不单调。然而如果 $i$ 更小的时候 $k$ 更大，这样的三元组一定是不优的，因此仍然是只需要让 $k$ 单调下降。令 $A=\max\{a_i\}$，$d(A)$ 是 $1$ 到 $A$ 中约数个数的最大值，则可以在 $O(nd(A))$ 的时间中找到所有的三元组。

询问就是简单的二维偏序，为了平衡复杂度，可以使用 $O(1)$ 修改、$O(\sqrt n)$ 查询的分块，总时间复杂度 $O(nd(A)+q\sqrt n)$。

J. Graph Changing

考虑在 $G_1$ 中，两点有边当且仅当 $|u,v|\ge k$，如果 $u,v$ 可达，则最短路径长度一定不超过 $3$（$u\to 1\to n\to v$）。因此如果 $k>3$，$G_2$ 开始就是空图。

当 $k=3$ 时，显然当 $n$ 足够大时 $G_2$ 开始也是空图。

当 $k=2$ 时，显然当 $n$ 足够大时 $G_{i+1}$ 是 $G_i$ 的反图。

当 $k=1$ 时，显然 $G_1$ 开始就是完全图。

因此只需要预处理 $n$ 小的情况（例如 $n< 10$），特判 $k=1,2,3$，剩余的情况分类讨论答案是 $1,2,3$ 即可。

K. Penguins in Refrigerator

先求方案数，考虑从大到小插入数。首先大于 $M/2$ 的数相对顺序不改变，对于不超过 $M/2$ 的每个数 $a_i$，找到左右第一个大于 $M-a_i$ 的数，则 $a_i$ 只能插入到这个区间中。注意到这些区间形成一棵树形结构，因此方案数就是每个数插入的方案数相乘。

再求字典序最小的方案数。大于 $M/2$ 的数相对顺序不改变，可以连一条链。对于不超过，对于不超过 $M/2$ 的每个数 $a_i$，找到左右第一个大于 $M-a_i$ 的数，只需要它们之间的相对顺序不改变即可（因为其他的顺序关系都通过链确定了）。之后用堆维护，求字典序最小的拓扑排序即可。

时间复杂度 $O(n\log n)$。

L. Prism Palace

所求的就是随机旋转一个角度，有一条边在 $y$ 轴上的投影是整个凸包的概率。对于相邻的两个内角 $a,b$，这条边满足条件的角度范围是 $\max\{0,\pi-a-b\}$。对这些角度求和然后除以 $2\pi$ 即可。时间复杂度 $O(n)$。

M. Random Variables

考虑对每个 $k$ 计算每种数出现次数不超过 $k$ 的方案数。其等于 $$ n![x^n]\left(\sum_{i=0}^k\frac{x^i}{i!}\right)^m $$ 注意由于模数不一定是素数，所以不一定有阶乘逆元，但 EGF 的卷积只需要乘上组合数。

考虑容斥，即把 $\sum_{i=0}^k\frac{x^i}{i!}$ 写成 $e^x-\sum_{i=k+1}^\infty \frac{x^i}{i!}$。如果能够预处理所有 $\left(\sum_{i=k}^\infty \frac{x^i}{i!}\right)^m$，就能够在 $O(n^2\log n)$ 时间内计算答案（因为 $mk\le n$）。

这里 $m$ 的范围是 $\frac{n}{k}$，按照 $k$ 从大到小预处理，每次只需给内部的式子加上一项，展开后是 $O(m)$ 项已知的式子求和。因此可以在 $O\left(\sum_{k=1}^n \frac{n^3}{k^2}\right)=O(n^3)$ 时间内预处理所有的值。对于每组数据，还要对 $0\le i\le n$ 计算 $m\choose i$，可以通过快速幂计算 $(1+x)^m\bmod x^{n+1}$ 在 $O(n^2\log m)$ 的时间内计算。因此总复杂度是 $O(N^3+\sum n^2(\log n+\log m))$。

对于整数 $B$，我们只预处理 $k\ge B$ 的值，复杂度是 $O\left(\frac{n^3}{B}\right)$。对于 $k< B$，我们要计算的是一个短多项式的幂，可以通过 ODE（$f'g=mg'f$）来计算，注意 EGF 的求导就是移位，所以不需要除法，复杂度是 $O(nk)$。总时间复杂度 $O\left(\frac{N^3}{B}+\sum n B^2+\sum n^2(\log n+\log m)\right)$。

官方题解里有 $O(\sum n^2\log n)$ 的做法。

N. Python Program

外层循环直接模拟，内层循环用等差数列求和。

时间复杂度 $O(|a-b|)$。

A. Bus Analysis

不妨将价格除以 $2$，变为 $1$ 和 $3$，最后将答案乘 $2$ 即可。

先考虑对于给定的 $t_1,t_2,\ldots,t_n$，如何计算最小代价。

设 $\mathrm{dp}(i,j)$ 表示用 $j$ 的代价覆盖了前 $i$ 个点，最多还能覆盖多长的距离。设覆盖前 $i$ 个点的最小代价为 $x$，则只有 $f(i,x),f(i,x+1),f(i,x+2)$ 的值有用。这是因为在如果前 $i$ 个点花费了至少 $x+3$ 的代价，一定不比“花费 $x$ 的代价覆盖前 $i$ 个点，然后再买一张 $3$ 元的票”优。

于是，在 DP 的过程中我们只需要记录 $x,f(i,x),f(i,x+1),f(i,x+2)$ 这些值。现在变为计数问题，只需要将这些值记在状态里面。并且注意到，我们只需要求代价的和，所以不需要将 $x$ 计入状态，只需在代价变大时统计进答案。

时间复杂度 $O(n\cdot 75^3)$。实际上，状态数的常数非常小，有用的三元组 $(a,b,c)$ 都满足 $0\le a\le a+20\le b\le b+20\le c\le 75$。

B. Missing Boundaries

首先，对于已经确定两个端点的区间，它们一定不能相交。

对于已经确定一个端点的区间，确定的端点一定不能包含在已经确定的区间里面，且互不相同。

剩下的区间可以任意填，我们可以计算出最小和最大的可能区间数量，判断输入的区间数量是否在范围内即可。

最大的区间数量就是（$L-$ 两端点确定的区间的长度和 $-$ 一个端点确定的区间个数）。

最小的区间数量就是相邻且差大于 $1$ 的右端点和左端点的对数（包括开头和结尾）。

时间复杂度 $O(N\log N)$。

C. Price Combo

考虑最终方案中每个物品是在商店 A 购买还是商店 B 购买。注意到如果 $a_i>a_j$ 且 $b_i< b_j$，那么在商店 A 购买物品 $i$ 、商店 B 购买物品 $j$ 一定是不优的（交换之后一定不劣）。因此，假设我们把一个物品看做点 $(a_i,b_i)$，那么一定存在一条右上到左下的折线，折线上以及左上方的物品在商店 A 购买，折线右下方的物品在商店 B 购买。我们对这条折线进行 DP。

不妨设 $a_i,b_i$ 互不相同。我们考虑从右上到左下确定折线，当折线向左的时候，加入折线上方的 $a_i$ 产生的贡献；折线向下的时候，加入折线右方的 $b_i$ 产生的贡献。注意因为是买一送一，因此只有第 $1,3,5,\ldots$ 个会产生贡献。

显然我们只需要将 $(a_i,b_i)$ 作为折线的关键点。为了方便起见，我们可以加入 $(+\infty,+\infty),(-\infty,-\infty)$。

设 $\mathrm{dp}(i,p,q)$ 是折线走到了 $(a_i,b_i)$，选择的 $a$ 个数奇偶性是 $p$，$b$ 个数奇偶性是 $q$ 的最小代价。那么假设 $(a_i,b_i)$ 从 $(a_j,b_j)$ 转移来（$a_i< a_j,b_i< b_j$），则需要加上的贡献是 $a_i< a_k< a_j$（$b_k>b_j$）和 $b_i< b_k< b_j$（$a_k>a_i$），以及 $a_i$ 的贡献。

考虑按照 $a_i$ 从大到小扫描线，用线段树维护转移。线段树以 $b$ 作为下标，维护 DP 值加上 $a_k$ 的贡献的最小值。对于 $a_k$ 的贡献，只需在扫描线时在线段树上做前缀加（$b_j< b_k$）。注意这里的加法标记实际上是（$0$ 位置加上的值，$1$ 位置加上的值，加的数的个数）三元组。对于 $b_k$ 的贡献，考虑直接在线段树上维护，即每个结点维护 $\mathrm{dp}(j)$ 加上小于 $b_j$ 的 $b$ 的贡献后的最小值，以及 $b$ 的贡献。这里 $b$ 的贡献本质上和 $a_k$ 的加法标记一样。合并时，DP 值应当是左区间的 DP 值以及（右区间的 DP 值加上左区间 $b$ 的贡献）的较小值。这样，要求 $\mathrm{dp}(i)$，只需要在线段树上查询后缀 $(b_i,+\infty)$。

时间复杂度 $O(N\log N)$。

D. Data Determination

不妨设 $a_1\le a_2\le \cdots\le a_n$。

当 $k$ 是奇数时，需要存在 $i$，满足 $a_i=m,i-1\ge\frac{k-1}{2},n-i\ge\frac{k-1}{2}$。

当 $k$ 是偶数时，需要存在 $i< j$，满足 $a_i+a_j=2m,i-1\ge \frac{k}{2} -1,n-j\ge\frac{k}{2}-1$。注意对于相同的 $(a_i,a_j)$，$i$ 和 $j$ 离得越近越好，这样的 $(i,j)$ 只有 $O(n)$ 对。

时间复杂度 $O(n\log n)$。

E. Express Eviction

解法 1

最小割。注意到存在路径当且仅当不存在左下区域到右上区域、每个格子都有居民、且相邻格子行列差都不超过 $2$ 的路径。我们认为左下边界和左下区域是相邻的，右上边界和右上区域是相邻的。

因此我们可以对每个有居民的格子建两个点 $(a_u,b_u)$，如果它是左下边界则连边 $(S,a_u,+\infty)$，右上边界则连边 $(b_u,T,+\infty)$，同时连边 $(a_u,b_u,1)$ 代表可以花费 $1$ 的代价删除这个格子。对于行列差都不超过 $2$ 的每对格子 $u,v$，连边 $(b_u,a_v,+\infty)$。这个图的最小割即为答案。

时间复杂度 $O(\mathrm{Maxflow}(HW,HW))$。

解法 2

最短路。考虑普通的最短路在什么时候会得不到最优解。

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

如这个例子，只需删除第三行的第四个格子。我们注意到这样的路径实际上是经过了一个格子相对的两个角，但我们的状态中并没有记录经过的格子，所以导致重复计算代价。

考虑所有经过两次的格子，如果一个有居民的格子 $u$ 的两次经过在另一个格子 $v$ 的两次经过之间，我们不如额外花费 $1$ 的代价直接穿过格子 $v$。因此可以假设没有这样的两个格子 $(u,v)$。在这个前提下，我们可以发现路径上的每一个点至多在两个格子的两次经过之间（路径的两侧各一个），通过在状态中记录这两个格子，我们可以做到 $O(H^3W^3)$ 的时间复杂度。

进一步地，假设我们依次经过了格子 $u,v$，那么下一步一定是从 $v$ 走到格子 $u$ 的对角。并且如果在下一次经过 $u$ 之前我们花费了额外的代价，也是不如直接穿过 $u$ 的。因此我们只需要记录一个之前经过的格子，并加一种额外的转移，即当前位置是 $x$，经过了 $v$，对于 $v$ 的每个对角相邻的点 $w$，如果 $x$ 可以不花费额外代价到达 $w$，则可以直接转移到位置 $w$，经过了 $x$。转移可以通过从每个点 BFS 预处理。

时间复杂度 $O(H^2W^2)$。

F. Fibonacci Fusion

不妨设 $a_1\le a_2\le \cdots\le a_n$。

枚举 $j$，则 $a_j< a_i+a_j\le 2a_j$，满足这样条件的斐波那契数只有至多两个，假设我们能求出这两个斐波那契数，就只需要求某个数的出现次数。

由于 $a_i$ 非常大，对应的斐波那契数也非常大，所以我们计算斐波那契数对大素数取模的值（避免碰撞），同时需要估算对应的数的下标。

因为 $F_n=\frac{1}{\sqrt5}\left(\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n\right)\approx \frac{1}{\sqrt 5}\left(\frac{1+\sqrt5}{2}\right)^n$ ，所以可以用 $n\approx \log_{\frac{1+\sqrt 5}{2}}{\sqrt 5a_i}$ 来估算。

时间复杂度 $O(n\log n+\sum\log a_i)$。

G. Game of Geniuses

答案等于 $\max_i\min_j a_{ij}$。

设答案为 $x$，答案大于等于 $x$ 是平凡的，先手可以删除除最小值等于 $x$ 的行以外的其余行。

要证明答案小于等于 $x$，我们只需要证明每轮后，后手都能保证每行都有小于等于 $x$ 的数。不妨设先手删除了第一行，则后手找到剩余 $n-1$ 行中各一个小于等于 $x$ 的数，标记其所在列，然后删除未被标记的列即可。

时间复杂度 $O(n^2)$。

H. Henry the Plumber

因为每个水管都必须立即转弯，所以答案至少是 $2$。

而答案不超过 $4$，因为可以分别连平行于 $z$ 轴的水管，到同一个 $z$ 之后垂直于 $z$ 轴连接起来（如果两点连线平行于 $z$ 轴则直接连）。

分类讨论：

• 如果 $(x_1,y_1,z_1)-(x_2,y_2,z_2)$ 垂直于 $(p_1,q_1,0)$ 和 $(p_2,q_2,0)$，则答案为 $2$。
• 否则答案至少为 $3$。答案为 $3$ 当且仅当存在一个中间点 $P$，和 $(x_i,y_i,z_i)$ 的连线垂直于 $(p_i,q_i,0)$。即 $P$ 在经过 $(x_i,y_i,z_i)$ 且垂直于 $(p_i,q_i,0)$ 的平面上。
• 如果这两个平面平行，则答案为 $4$。
• 否则找到这两个平面的交，设为 $(x_0,y_0,z)$（一条平行于 $z$ 轴的直线）。现在要确定 $z$ 的值，使得 $P$ 的夹角为直角，即 $(x_0-x_1,y_0-y_1,z-z_1)$ 和 $(x_0-x_2,y_0-y_2,z-z_2)$ 的点积为 $0$。
• 如果 $(x_0,y_0)$ 和某个 $(x_i,y_i)$ 重合，则满足条件的 $P$ 就是 $(x_i,y_i,z_{j})$，如果 $z_1\ne z_2$ 则答案为 $3$，否则答案为 $4$（因为水管长度不能为 $0$）。
• 否则，条件是一个关于 $z$ 的二次方程，只需判断判别式是否大于等于 $0$。大于等于 $0$ 则答案为 $3$，否则答案为 $4$。

时间复杂度 $O(1)$。

I. ICPC Inference

枚举获得金银铜牌的队伍。铜牌一定是通过了一个题目，且罚时尽量大。金牌一定是通过了尽量多的题目，且罚时尽可能小。

我们可以将分数设为 $M\cdot \mathrm{num}-\mathrm{penalty}$，其中 $M$ 是一个非常大的数。则分数越大的人排名越高。

考虑银牌可能的分数，因为铜牌只通过一个题，银牌分数应当在不小于铜牌的前提下尽可能小，因此有用的分数只有通过一个题的情况以及通过两个题且罚时最大。设这些可能的分数是 $s_1< s_2< \ldots< s_k$，则满足 $s_i<\mathrm{bronze}\le\mathrm{gold}< s_{i+1}$ 的金铜牌是不合法的（当然还有小于 $s_1$ 和大于 $s_k$ 的情况）。

我们可以在 $O(\log N)$ 的时间里面对每一个区间计算答案，但是区间的数量可以是 $O(N^2)$ 的。注意到罚时 $K=20$ 比较小，而可能的罚时都形如 $t_i+K\cdot c$（$0\le c< i$），因此可能的罚时可以写成 $O(N)$ 个段，每个段以 $K$ 为周期。对于跨段的区间我们可以 $O(\log N)$ 计算。而对于段内我们可以抽象成 $O(K)$ 个以下询问：

• 有多少对 $(\mathrm{bronze},\mathrm{gold})$ 满足 $\mathrm{bronze}\bmod K=i$，$l\le \mathrm{bronze}\le r$ 且 $\mathrm{gold}-\mathrm{bronze}\le j$。

这样的 $(\mathrm{bronze},\mathrm{gold})$ 也只有 $O(NK)$ 对，预处理之后可以 $O(\log N)$ 回答询问。

注意金银铜牌必须互不相同，因此需要做一些容斥。

时间复杂度 $O(NK\log N)$。

J. Juliet Unifies Ones

数据范围很小，所以做法很多。

一个线性的做法是分成三段，分别是 $0,1,0$，设 $\mathrm{dp}(i,j)$ 表示考虑 $i$ 个字符，目前在第 $j$ 段，至少要删几个字符。

K. Routing K-Codes

如果 $K(b)=\left\lfloor\frac{K(a)}{2}\right\rfloor$ 则我们将边定向为 $a\to b$。因为所有 $K(x)$ 互不相同，因此每个点的出度都不超过 $1$，入度不超过 $2$，且图中不存在环，因此只可能是内向二叉树。因此如果 $m\ne n-1$ 则无解。

假设确定了根，则根的值为 $0$ 或 $1$（度数小于 $2$ 则为 $0$，等于 $2$ 则为 $1$），深度不超过 $32$ 或 $31$，每个孩子的值是 $2K(x)$ 或 $2K(x)+1$。最小的代价和可以通过 DP 求出。使用换根 DP 即可求出每个点作为根的答案。

时间复杂度 $O(n+m)$。

L. Random Numbers

注意到长度为 $k$ 的区间的和的期望是 $k\cdot \frac{n+1}{2}$，因此当 $k$ 距离 $\frac{n}{2}$ 较近时才有较大的概率存在合法区间。当 $k$ 较小的时候，因为总的组合数量不多，因此也有一定的概率存在合法区间。

因此只需设置常数 $B$，枚举所有长度在 $[1,B]$ 或 $\left[\frac{n}{2}-B,\frac{n}{2}+B\right]$ 中的区间检查即可。

时间复杂度 $O(nB)$。例如 $B$ 取 $500$ 可以通过此题。

M. Mathematics Championships

答案等于前 $2^i$（$0\le i\le k$）大数和的最大值。排序后即可计算。

时间复杂度 $O(n2^n)$。

A. Coprime Array

注意到我们只关心 $s\bmod x$ 的值（答案绝对值要求在 $10^9$ 以内，但是任何一组解都可以通过调整符合这个范围，所以可以忽略这个限制），将 $x$ 分解后，只需要求出每个 $p^k$ 的解，就能通过 CRT 合并出 $x$ 的解。

显然答案等于 $1$ 当且仅当 $\gcd(s,x)=1$。

剩下的情况，除了 $s$ 是奇数且 $x$ 是偶数的情况，都能构造出长度为 $2$ 的解。

$s$ 是奇数且 $x$ 是偶数的情况可以先分出一个 $1$，因此可以构造出长度为 $3$ 的解。

实现时其实可以利用随机避免分解和 CRT，随机到一个解的概率至少是 $\prod_{p|x}\frac{\max\{1,p-2\}}{p}$。

B. Square Locator

因为点 $A$ 在 $y$ 轴上，所以点 $A$ 的坐标可以直接算出。枚举 $ABCD$ 是逆时针还是顺时针，设点 $B$ 的坐标是 $(x,y)$，则可以通过点 $B$ 和点 $C$ 到原点的距离列出两个方程，从而直接解出 $x,y$ 并判断。

C. -is-this-bitset-

对于深度 $d\le 11$ 的点 $i$，将 $a_i$ 设为 $2^{20-d}$。因为树是二叉树，所以至多改变 $2^{12}-1=4\,095$ 个点的 $a_i$。

改变之后，每条链上的前 $12$ 个点就可以凑出 $[0,2^{21})$ 中所有 $2^9=512$ 的倍数。因此对于 $d>11$ 的点，只需要考虑模 $512$ 的每种余数能凑出的最小的数，可以在 $O(512)$ 的时间 DP 求出。

为了进一步减小空间消耗，注意到每条链上 DP 的改变量不会超过 $\max\{b_i\} < 2^{21}$，因此只需记录 DP 数组发生的改变，回溯时撤销即可。

设 $V=\max\{b_i\},k=5\,000$，则时间复杂度为 $O(nV/k)$，空间复杂度为 $O(n+V)$。

D. Cycle Game

我们认为最外圈边界都是白格子，则存在一个内部非空的环当且仅当存在一个格子，将这个格子视为白格子后白格子的八连通块至少有两个（即存在一个白格子和边界不连通）。

加入一个黑格子后，如果存在这样的格子，那么其中的一个一定与新加入的格子相邻。因此只需使用线段树分治和可撤销并查集维护连通性，在每个时刻枚举周围的所有格子并判断这次操作是否应该进行。

时间复杂度 $O(nm\log ^2 (nm))$。

E. Sum of Squares

F. Alternating Cycle

G. Touching Grass

如果询问的是直线，则问题可以转化为直线和点集的上凸包是否相交，只需在凸包上二分。

线段询问可以通过线段树转化为直线询问，即按 $x$ 排序建线段树，对线段树上的每个区间都求凸包。

这样的空间复杂度是 $O(n\log n+m)$，采用类似分治的方式离线回答询问可以优化为 $O(n+m)$。

将线段按斜率排序后可以避免二分，改用双指针，总时间复杂度 $O((n+m)\log n)$。

H. Game Design

将 $i$ 到 $p_i$ 连边，可以看作每个点入度和出度都是 $1$ 的有向图。设 $f(i,j)$ 为考虑前 $i$ 个点，有 $j$ 条入边和出边的另一端还未确定（大于 $i$）。

考虑 $i$ 的连边，有如下四种转移。

• 入边和出边都向后，转移到 $j+1$，方案数 $1$。
• 入边向后，出边向前，转移到 $j$，方案数 $j$。
• 入边向前，出边向后，要求 $s_i=1$，转移到 $j$，方案数 $j$。
• 入边和出边都向前，要求 $s_i=1$，转移到 $j-1$，方案数 $j^2$。

时间复杂度 $O(n^2)$。

I. Geometry Hacking

J. Non-Interactive Nim

A. Counting Permutations

对于所有满足条件的排列，二元组序列 $(a_{p_i}\bmod m_1,a_{p_i}\bmod m_2)$ 一定是相同的，也就是按 $a_i\bmod m_1$ 为第一关键字，$a_i\bmod m_2$ 为第二关键字升序排序。

如果这个序列不合法则无解，否则方案数为每个 $(a_i\bmod m_1,a_i\bmod m_2)$ 二元组出现次数的阶乘乘积。

时间复杂度 $O(n\log n)$。

B. Bookshelf Tracking

如果只有 E 操作，则维护每本书的位置，就可以 $O(1)$ 进行交换。

如果有 R 操作，注意到 R 操作的本质是将位于前一半的书按编号降序排序，后一半的书按编号升序排序。因此，在最后一次 R 操作之前，只需维护每本书是在前一半还是后一半。排序后再处理最后的一段 E 操作即可。

时间复杂度 $O(n+q)$。

C. Painting Fences

最优解一定是从一个极大全黑矩形开始扩展。这样的矩形共有 $O(nm)$ 个，可以通过枚举底端然后笛卡尔树求出。

考虑求从一个矩形扩展到全部的步数。显然两维是独立的，因此只需要考虑 $[l,r]$ 扩展到 $[0,n]$ 的最少步数。

如果 $l=0$ 或者 $r=n$，显然最优解是长度每次翻倍。

对于一般情况，枚举 $l=0$ 和 $r=n$ 哪个先满足。不妨设 $l=0$ 先满足。设初始时 $d=\left\lceil \frac{l}{r-l}\right\rceil$，则至少需要 $\left\lceil\log_2{(d+1)}\right\rceil$ 步。但是一直向左对称可能会导致一些浪费。事实上，最优解是：第 $i$ 轮，如果 $d$ 的二进制从低到高第 $i$ 位是 $1$，则向左对称，否则向右对称。

因此从一个矩形开始扩展的最小步数可以在 $O(\log nm)$ 甚至 $O(1)$ 的时间内求出。

总时间复杂度 $O(nm\log nm)$ 或 $O(nm)$。

D. Function with Many Maximums

首先要注意到，假设 $a_i$ 是降序排序，则 $f(a_i)=\sum_{j=1}^ia_j+ia_i$。如果不考虑 $a_i$ 必须是整数的条件，令 $a_i=\frac{1}{i(i+1)}$ 可以使所有 $f(a_i)$ 相同。

考虑找一个大数 $M$（大约为 $Cn^4$ 级别），然后令 $a_i=\left\lfloor \frac{M}{i(i+1)}\right\rfloor$，然后对其进行调整。我们希望使得 $f(a_{n}),f(a_{n-2}),f(a_{n-4}),\ldots,f(a_{n-2(b-1)})$ 是最大值，因此对于 $i< n-2(b-1)$，只需令 $a_i=a_{i+1}+1$。注意这时 $a_1$ 也就是 $a_i$ 的最大值不超过 $O(Cn^2)$，符合题目要求。

对于后面部分的调整，首先需要将 $f(a_i)$ 调整成递增，这只需将函数值下降位置的 $a_i$ 增加 $O(n)$ 的值。这是因为原来相邻函数值的差是 $O(n)$ 的，所以调整后累计的差是 $O(n^2)$，而将 $a_i$ 增加 $1$ 会使得 $f(a_i)$ 增加 $i+1$。

调整后，相邻函数值的差仍然是 $O(n)$ 的，而相邻 $a_i$ 的差是 $\Theta(Cn)$，因此将 $a_{2i+1}$ 的值减少 $f(a_{2i+2})-f(a_{2i})$ 就能使得 $f(a_{2i+2})=f(a_{2i})$。

E. Building a Fence

分类讨论。不妨设 $w\le h$。

• 如果 $s\le w\le h$，那么从一个角开始贪心铺放，不可能出现一个 $s$ 被分成三段的情况，因此答案可以取到下界 $\left\lceil \frac{2(w+h)}{s}\right\rceil$。
• 如果 $w\le h< s$，那么答案可能是 $2,3$ 或 $4$。
  • 要答案为 $2$，只可能是两个 $s$ 都被分成了两段，即 $w+h=s$。
  • 要答案为 $3$，肯定有 $k$ 个 $s$ 恰好拼了 $k+1$ 条边。
    • $k=1$，即 $2w=s$ 或 $2h=s$。
    • $k=2$，即 $2w+h=2s$ 或 $2h+w=s$。
    • $k=3$，即 $2(w+h)=3s$。
  • 否则答案为 $4$。
• 如果 $w< s\le h$。
  • 如果 $2w+h\ge 2s$，那么可以先拿两个 $s$ 分出两个 $w$，剩下部分拼到同一个长边，然后从这条边开始贪心，能取到下界 $\left\lceil \frac{2(w+h)}{s}\right\rceil$。
  • 否则答案为 $3$ 或 $4$，分析同上，但因为大小关系的限制只可能 $k=3$，即 $2(w+h)=3s$。

F. Teleports

注意到经过任意的操作后，我们都知道可能的宝藏位置是一个区间。设 $f(l,r)$ 是已知宝藏在第 $l$ 个到第 $r$ 个箱子时，找到宝藏的最小代价。

转移如下。

• 枚举选择的传送器 $x$，则新的可能的宝藏范围是 $[2x-r,2x-l]$。
  • 如果 $1\le 2x-r\le 2x-l\le n$，则 $f(l,r)\le f(2x-r,2x-l)$。
  • 如果 $2x-r< 1$，则 $[2x,r]$ 中的宝藏无法传送，$f(l,r)\le \max\{f(1,2x-l),f(2x,r)\}$。
  • 如果 $2x-l>n$，则 $[l,2x-n-1]$ 中的宝藏无法传送，$f(l,r)\le \max\{f(2x-r,n),f(l,2x-n-1)\}$。

注意到转移图是一个关于区间长度 $r-l$ 的分层图，每一层中只有第一类转移。因此可以从小到大枚举 $r-l$，执行所有的第二、三类转移，然后使用 Dijkstra 进行第一类转移。这里是稠密图所以可以使用 $O(n^2)$ 的 Dijkstra（当然堆优化的 Dijkstra 也很快）。

时间复杂度 $O(n^3)$。

G. Exponent Calculator

因为只有加法、减法和乘法，因此不考虑牛顿迭代。考虑用 $e^x=\sum_{n=0}^\infty \frac{x^n}{n!}$ 来逼近。但是这样在 $|x|$ 较大时收敛较慢。因此考虑先将 $x$ 除以 $2^B$，然后展开到 $x^T$ 项，最后将结果平方 $B$ 次。实验可以发现 $T=7,B=10$ 时较优，可以在 $x=20$ 时达到 $10^{-12}$ 以下的相对精度。

H. Ancient Country

考虑所有城市的顶点，不可能出现 $i < j < k < l$ 满足 $P_i$ 和 $P_k$ 在同一个城市，并且 $P_j$ 和 $P_l$ 在同一个城市（否则 $P_iP_k$ 和 $P_jP_l$ 就会相交或是在国家范围之外）。因此这些城市的顶点形成一个树形结构。即设包含最小顶点的城市的顶点为 $P_{i_1},P_{i_2},\ldots,P_{i_k}$，那么剩余的城市顶点一定分布在 $[i_1+1,i_2-1],[i_2+1,i_3-1],\ldots,[i_k+1,n]$ 这些区间中。

因此我们可以设计区间 DP，即 $f(l,r)$ 表示只是用下标在 $l$ 到 $r$ 的顶点，所构造城市的最大保护级别。转移如下。

• 假设 $P_l$ 不属于某个城市，则 $f(l,r)\gets f(l+1,r)$。

• 否则我们要选一个包含 $P_l$ 的凸包，然后用凸包的权值加上凸包顶点间的区间的 $f$ 值之和来更新 $f(l,r)$。这一步也可以用 DP 进行。

  • 首先枚举 $i$ 连的第一条边 $P_iP_s$，然后令 $g(j,k)$ 表示凸包最后一条边是 $P_jP_k$ 的最大权值。转移是枚举下一条边 $P_kP_e$，然后转移到 $g(k,e)$。最后检查一下连回 $l$ 是否合法并更新答案。需要枚举第一条边是因为要检查 $P_kP_iP_s$ 这个角是否合法。注意这里判断凸包只需要相邻三个点的夹角，因为下标递增，必然是不会自交的。

具体实现时，可以从大到小枚举 $l$，然后进行 DP。枚举 $l,s$ 后，DP 的复杂度是 $O(n^3)$。注意到转移可以用极角序优化，即枚举 $k,e$，可以转移到 $g(k,e)$ 的 $i$ 是极角序上的一段。事实上，我们不需要记录极角序，因为下标递增，每个点所连出的边按下标排序就是极角序，因此枚举 $k,e$ 后，可以转移的 $i$ 是一个前缀，用双指针维护即可。

总时间复杂度 $O(n^4)$。

I. Marks Sum

如果长度小于 $2\,000$，可以直接返回 $d=info=0$。

如果长度大于等于 $2\,000$，我们一定能找到一个前缀，使得剩余字符数小于 $2\,000$，且总和是 $2\,000$ 的倍数或其加 $1$。我们令 $info=2x+y$（$0\le y\le 1$）表示前缀的总和等于 $2\,000x+y$。因为字符串长度不超过 $10^6$，因此 $x< 1\,000$，是足够的。

第二次时只需根据 $info$ 计算出前缀的总和，在加上输入串的总和即可。

J. Prefix Divisible by Suffix

枚举选择最短的后缀。如果后缀有前导 $0$，则去掉之后仍然满足条件。因此满足条件的最短后缀长度不超过 $7$（如果大于 $7$ 则前缀小于后缀）。

因为我们钦定枚举的后缀是最短的一个，需要枚举更短的一些进行容斥。若干后缀都满足的数形如 $km+a$，可以用扩展欧几里得算法求出。

时间复杂度 $O(10^7\cdot 2^7\cdot \log n)$。但是注意到在后缀较长时，对于很多的集合，满足条件的数的大小都超过了 $n$。我们在枚举的时候对这种情况直接剪枝，总枚举次数实际上远小于这个上界。

K. Train Depot

首先可以把所有列车转化为 $s_i$ 到 $t_i$ 的路径（$t_i$ 是 $s_i$ 的祖先），价值为 $c_i$，然后选择若干条点不相交的路径使得总价值最大。

设 $f(x)$ 为在 $x$ 的子树里面选择路径的最大价值。如果 $x$ 不是某条路径的顶端则 $f(x)\gets \sum_{y\in ch(x)}f(y)$。

如果选择了 $x\to y$ 的路径，那么 $y$ 到 $x$（不包括 $x$）的路径上的每一个点的兄弟以及 $y$ 的所有孩子 $z$ 会贡献 $f(z)$。反过来考虑，每个点 $x$ 会对底端是 $x$ 的父亲或 $x$ 的兄弟子树中的点的路径有贡献，在 DFS 序上即 $[in_{parent_x},in_x)$ 和 $[out_x,out_{parent_x})$ 这两个区间。使用线段树或树状数组维护这个贡献即可。

时间复杂度 $O((n+\sum k_i)\log n)$。

L. Array Spread

二分答案 $x$，如果有一种序列满足每个区间的总和在 $[1,x]$ 中，说明答案不大于 $x$。

设 $s_i$ 是前 $i$ 个数的和，则限制为 $s_i\ge s_{i-1}$ 和 $1\le s_{r_i}-s_{l_i-1}\le x$，显然是差分约束的形式。离散化之后点数和边数都是 $O(m)$，因此判断负环的时间复杂度是 $O(m^2)$。这里也可以看出答案是分子和分母不超过 $O(m)$（分母不超过简单环长度也就是图中点数，分子不超过图中除 $x$ 外的边权和）的分数。因此二分次数是 $O(\log m)$，二分之后可以根据实数值还原答案。也可以直接对这 $O(m^2)$ 个分数二分。

总时间复杂度 $O(m^2\log m)$。

事实上，我们可以去掉二分。将边权为 $x$ 的边称为特殊边，剩下的是普通边。令 $f(i,v)$ 表示从任意点开始，经过恰好 $i$ 条特殊边，到达 $v$ 的路径的普通边边权和的最小值。则答案等于 $$ \max_v\min_{i=0}^{n-1}\frac{f(i,v)-f(n,v)}{n-i} $$

其中 $n$ 是顶点数。

证明见此论文。

M. Uniting Amoebas

每次将最大值和相邻的合并就可以做到 $\sum_{i=1}^n a_i-\max_{i=1}^n\{a_i\}$。

显然这是最优解，因为每次花费 $v$ 的代价至多使得最大值增加 $v$。

A. Arrested Development

动态规划，$f(i,j)$ 表示考虑前 $i$ 个任务，第一个人总时间为 $j$ 时，第二个人总时间的最小值。

时间复杂度 $O(n^2\max\{a_i,b_i\})$。

B. Champernowne Substring

讨论以下情况：

• 对于位置不超过 $100\,000$ 的情况暴力判断，以下都假设串中出现的都至少是五位数。

• 特判串中出现 $10^k$ 或 $10^k-1$ 的情况，以下都假设串中所有数的长度相等。

• 串中只包含一个数。问号一定贪心填 $0$（首位是 $1$），如果首位是 $0$ 还需要在前面补 $1$。

• 串中包含超过一个数。枚举这个数的开始位置和长度，以及进位的位数（因为串长不超过 $25$ 且都至少是五位数，因此至多有一次进位）。那么进位的部分全部填 $0$ 或 $9$，前一位枚举 $0$ 至 $9$，再之前的位每个数都一样，问号同样贪心填 $0$ 或 $1$。对于每种可能性都检查一遍。

C. Comparator

首先注意到，表达式只有两个输入，我们可以直接枚举这两个输入后求表达式的值。从而，每条语句的效果都可以拆分为不超过 $4$ 条：如果 $x$ 的第 $a$ 位为 $u$ 且 $y$ 的第 $b$ 位为 $v$，则返回 $r$。当两条语句的 $(a,u,b,v)$ 四元组相同时，靠后的语句实际上没有任何效果，因为它所能作用的输入已经全部返回了。因此，我们实际上只需要考虑不超过 $4k^2$ 条语句，每条语句的效果可以在 $O(2^{2k})$ 的时间内暴力处理。

当我们得到了所有 $f(x,y)$ 的值后，就可以统计答案。前两个答案都可以暴力统计，最后的答案枚举 $x,y$ 后使用 bitset 优化即可。

时间复杂度 $O\left(\sum|expr|+k^22^{2k}+2^{3k}/w\right)$。

D. Dihedral Group

二面体群的操作对应到字符串其实就是翻转和循环移位，只需要判断未翻转/翻转的 $d+d$ 是否包含 $t$ 作为子串。

时间复杂度 $O(n)$。

E. House Deconstruction

1. $n=m$ 的情况

首先考虑 $n=m$ 的情况，即人的数量和房子的数量一样多时，如何求最小代价。对于一个方案，设 $c_i$ 表示经过了 $i$ 到 $i+1$ 这条边的人数（这里模 $x$ 相等的下标表示同一个位置，例如 $x+1$ 代表 $1$）。如果是从 $i+1$ 到 $i$ 则 $c_i$ 是经过人数的相反数，显然最优解中不会有一条边两个方向都有人经过。则方案对应的代价是 $\sum_{i=1}^x|c_i|$，需要满足的限制如下：

• 如果 $i$ 位置是人，则 $c_i=c_{i-1}+1$。
• 如果 $i$ 位置是房子，则 $c_i=c_{i-1}-1$。
• 如果 $i$ 位置是空，则 $c_i=c_{i-1}$。

容易发现，$c_i$ 序列几乎是确定的，除了可以整体加上一个任意整数。设一个合法的序列是 $c_i'$，则最小代价为对于任意 $k$，$\sum_{i=1}^x|c_i+k|$ 的最小值。这个函数关于 $k$ 是下凸的，因此可以用三分求出答案。（事实上，$k$ 一定是 $c_i$ 的中位数的相反数。）

2. $n< m$ 的情况：最优解

延续 $n=m$ 的思路，我们可以稍微修改 $c_i$ 的定义，即如果 $i$ 位置是房子，$c_i$ 可以等于 $c_{i-1}-1$ 或 $c_{i-1}$（表示该房子未被选择）。我们可以猜测以下的引理：

引理 1 设 $g(k)$ 为 $c_x=k$ 时的最优解，则 $g(k)$ 是下凸函数。

有了引理 1 之后，对于 $n< m$ 的情况我们同样可以三分 $k$，之后只需解决固定 $c_x$ 之后的问题，即可求出最优解。

引理 1 的证明 只需证明 $2g(k)\le g(k-1)+g(k+1)$。设 $k-1$ 和 $k+1$ 对应的序列分别为 $c_i^{(k-1)}$ 和 $c_{i}^{(k+1)}$。则令 $c_i^{(k)}=\frac{c_i^{(k-1)}+c_i^{(k+1)}}{2}$。该序列几乎满足我们的需求，包括 $c_x^{(k)}=k$ 以及相邻 $c_i$ 之间的关系，并且因为三角形不等式 $|a+b|\le |a|+|b|$，该序列的代价不超过 $\frac{g(k-1)+g(k+1)}{2}$。唯一有问题的地方是当某一处房子只在 $k-1$ 和 $k+1$ 中的一个方案中被选择时，我们会算出 $c_i=c_{i-1}-1/2$。然而，对于每一个极长的小数部分为 $1/2$ 的连续段，整体加上或减去 $1/2$ 就是合法的序列，且其中的一种不会使得代价变大（只需比较正数和负数的数量）。从而我们证明了 $2g(k)\le g(k-1)+g(k+1)$。$\blacksquare$

对于证明中存在小数部分的调整，事实上，即使我们把 $i$ 位置是房子时的限制改为 $c_i\in[c_{i-1}-1,c_i]$，最优解仍然会在所有数都是整数时取到。（提示：仍然可以考虑调整，也可以直接把原问题写成费用流，这样也能得到原问题的凸性。）

接下来只需要考虑固定 $k$ 时如何求最优解。我们可以使用 DP。

设 $f(i,j)$ 表示考虑了前 $i$ 个位置，$c_i=j$ 的最小代价。初始值为 $f(0,k)=0$。转移如下：

• 如果 $i$ 位置是人，则 $f(i,j)= f(i-1,j-1)+|j|$。
• 如果 $i$ 位置是房子，则 $f(i,j)= \min \{f(i-1,j+1),f(i-1,j)\}+|j|$。这里代表房子可选可不选。
• 如果 $i$ 位置是空，则 $f(i,j)=f(i-1,j)+|j|$。

最终的答案即为 $f(x,k)$。

注意到 $f(i,j)$ 对于固定的 $i$，关于 $j$ 是下凸的，很容易维护。实现中，为了方便，可以把状态改为 $f(i,j)$ 表示前 $i$ 个位置选了 $j$ 个房子的最小代价，这时最小值的位置一定是单调不降的，可以用差分维护最小值之后的斜率，对于房子只需插入一个 $0$ 的斜率。

把空的位置一起处理，就能做到 $O(m)$ 的时间复杂度。

因此，我们可以在 $O(m\log n)$ 的时间内求出最优解。

3. $n< m$ 的情况：方案数

为了计算方案数，我们还需要以下的引理：

引理 2 一个全局最优解 $S$ 只会在唯一的 $k$ 处取到最优解。

证明 注意到对于一个全局最优解的匹配方案，每个未选择的房子 $i$ 都应该满足 $c_i=0$，即没有匹配经过该房子，否则用该房子替换这个匹配中的房子，代价严格变小。如果一个全局最优解 $S$ 在两个不同的 $k$ 处取到最优解，那么一定有一个 $k$ 使得某个未选择的房子 $i$ 满足 $c_i\ne 0$，矛盾。因此， 一个全局最优解 $S$ 只会在唯一的 $k$ 处取到最优解。$\blacksquare$

根据引理 2，我们只需对每个 $g(k)$ 取到最小值的 $k$ 分别计算方案数并求和即可。

我们还需要以下引理：

引理 3 至多有两个 $k$ 满足 $g(k)$ 是最小值。

证明 采用反证法，假设 $g(k-1),g(k),g(k+1)$ 都是最小值。根据引理 1 的证明过程，$g(k)=\frac{g(k-1)+g(k+1)}{2}$ 的必要条件是 $c_i^{(k-1)}\cdot c_i^{(k+1)}\ge 0$（否则三角形不等式严格不等），以及对于每个极长的小数部分为 $1/2$ 的连续段，正数的个数等于负数的个数（从而无论加还是减 $1/2$，都不会改变代价）。因此不妨设 $k-1\ge 0$（$k+1\le 0$ 是对称的），找到最小的 $j$ 满足 $c_j^{(k-1)}\ne c_j^{(k+1)}-2$，则 $j$ 位置是房子。这样的 $j$ 一定存在，否则两个方案对应相同的 $S$，根据引理 2，一定不是全局最优解。此时 $c_j^{(k-1)}=c_j^{(k+1)}-3$ 或 $c_j^{(k-1)}=c_j^{(k+1)}-1$，且 $c_j^{(k-1)}\ge 0$。无论如何，我们都可以令 $c_{j}^{(k)}=c_{j-1}^{(k)}>0$，同时调整极长的连续段。但是因为 $j$ 是未选择的房子，所以这一定不是全局最优解。因此至多有两个 $k$ 满足 $g(k)$ 是最小值。$\blacksquare$

根据引理 3，我们只需要对至多两个 $k$ 分别计算方案数并求和。因此这不会增加我们的复杂度。

至于计算方案数，可以在 DP 的过程中同时进行。我们维护 DP 取到最小值的位置，并且最小值至多有两个。最小值之后的部分的方案数只需进行一个平移。因为最小值的位置单调不降，方案数也很容易维护，时间复杂度仍然为 $O(m)$。

综上，我们可以在 $O(m\log n)$ 的时间复杂度内解决该问题。

F. Magic Bean

我们只需要构造出能够交换两个环内的豆子的操作，之后每次找到 $a$ 环内的 $b$ 豆子，和 $b$ 环内非 $b$ 的豆子交换，即可在不超过 $30$ 次交换内完成复原。

构造的操作如下：把 $a$ 环内要交换的豆子移至 $1$，$b$ 环内要交换的豆子移至 $4$，$a$ 环转到 $b$ 环，$b$ 环逆时针转一格，$b$ 环转到 $a$ 环。

G. Manhattan Walk

由于每个格子的状态是均匀独立随机的，并且到一个格子之前无法得知该格子的状态，因此可以看做到每个格子时再均匀随机状态。

设 $f(i,j)$ 表示从 $(i,j)$ 开始，到达终点的期望最小时间。如果 $i=r$ 或 $j=c$，则可以直接转移，否则设两个方向的 $f$ 值分别为 $a$ 和 $b$（$a\le b$）。

讨论两种情况：

• $b\ge a+p$，那么无论如何都会选择 $b$，期望为 $a+p/4$。
• $b < a+p$，那么只有当离能走 $a$ 还有超过 $b-a$ 的时间才会选择走 $b$，期望为 $(p-b+a)/2p\cdot b+a/2+(b-a)/2p\cdot (a+b)/2$。（三项分别代表选择走 $b$、可以走 $a$ 时走 $a$、等待后走 $a$ 的期望。）

时间复杂度 $O(rc)$。

H. MountainCraft

注意到斜线的长度等于横向覆盖的长度乘以 $\sqrt 2$。而横向覆盖的长度就是所有 $[x-y,x+y]$ 的并。使用线段树维护即可（维护区间最小值和最小值个数；或者因为减法只是加法的撤销，维护每个结点的覆盖次数）。

时间复杂度 $O(q\log q)$。

I. Not Another Constructive!

我们可以在字符 A 的位置计算贡献，也就是前缀中 N 的数量和后缀中 C 的数量的乘积。因此设 $f(i,N,C,k)$ 表示考虑了长度为 $i$ 的前缀，前缀中 N 的数量为 $N$，后缀中 C 的数量为 $C$，是否能恰好有 $k$ 个 NAC 子序列。可以用 bitset 优化。

时间复杂度 $O(n^3k/w)$。

J. Passport Stamps

第 $i$ 趟旅行可能无法进行的条件是 $p\le \sum_{j=1}^{i-1}c_j+i\cdot (c_i-1)$，也就是在前面每个章之间留恰好 $(c_i-1)$ 的间隔。

时间复杂度 $O(n)$。

注意，直接计算可能会超过 long long 的范围，需要使用 __int128 或改用除法。

K. Shadow Line

注意到要判断是否只有一片影子，只需要知道每个端点在墙上的位置的相对关系。而这些相对关系只会有 $O(n^2)$ 次变化，也就是在两两的连线与 $x$ 轴交点的位置。算出这些变化的位置之后就可以进行模拟。

只有一片影子的充要条件是对于每个真前缀，下端点的数量大于上端点的数量。因为每次都是交换位置相邻的端点，因此这个条件可以在 $O(1)$ 时间内维护。

要注意的细节包括在有三点共线时的交换顺序，以及 $x$ 轴上的下端点应该始终排在上端点之前。

时间复杂度 $O(n^2\log n)$。

L. Square of Triangles

M. Training, Round 2

设 $f(i,j,k)$ 表示考虑前 $i$ 个题，是否能恰好加 $j$ 次实现水平和 $k$ 次思维水平。注意这里当某个 $(j,k)$ 能达到时，之后都能达到。因此我们对每个 $j$ 维护两个集合：已经能达到的 $k$ 的集合以及已经更新过的 $k$ 的集合。对于每个问题，我们只需找到矩形中能达到但还未被更新过的 $(j,k)$，将 $(j+1,k)$ 和 $(j,k+1)$ 都加入能达到的集合。因为每个 $(j,k)$ 只会被更新一次，所以时间复杂度是 $O(n^2\log n)$。

回顾对于给定递增序列 $a_1\le a_2\le \cdots\le a_n$ 求答案的过程：

• 找到最小的 $i$ 使得对所有的 $j\le i$，$a_i\ge a_j-a_1-a_2-\cdots-a_{j-1}+k$。
  • 注意如果 $i$ 满足条件，则 $i+1$ 也满足条件。
  • 只有这些满足条件的 $i$ 才可能在吃掉 $1,2,\ldots,i-1$ 后继续吃掉 $i+1$；同时，如果无法继续吃掉 $i+1$，则 $i+1$ 一定可以依次吃掉 $1,2,\ldots,i$。
  • 如果不存在满足条件的 $i$，根据上述性质，只有 $n$ 可能获胜。
• 令 $x=i$，枚举每个史莱姆 $j=i+1,\ldots,n$，如果当前 $x$ 能够吃掉 $j$（$a_1+a_2+\cdots+a_{j-1}\ge a_j+k$），那么吃掉 $j$，否则 $1,2,\ldots,j-1$ 都不可能获胜，因此令 $x=j$。
• 能够获胜的史莱姆即为 $x,x+1,\ldots,n$。

考虑利用值域 $[2^j,2^{j+1})$ 分段的技巧优化上述过程。

对于第一步，只有每一段中的第一个数可能是 $a_j-a_1-a_2-\cdots-a_{j-1}+k$ 的前缀最大值，因此先判断每一段的最后一个数是否满足条件，如果满足，则二分出第一个满足条件的数。

如果找不到满足条件的 $i$，容易判断最后一个数是否能够获胜（如果能获胜，它一定是所在段中的唯一一个数）。

接下来我们从 $i$ 所在的段开始，枚举每一段，先判断能否吃掉这一段中的第一个数 $y_1$，如果可以，则可以吃掉这一段中的所有数（因为 $(2^j+k)+2^j=2^{j+1}+k$）；否则，令 $x$ 为 $y_1$，注意此时不一定能吃掉所有数，因此还要判断是否能吃掉第二个数 $y_2$（如果存在），如果不能，则令 $x=y_2$，此时就一定可以吃掉这一段的所有数了。

注意最开始 $i$ 所在的段已经有一些数被吃掉了，但处理的方式完全类似于后面的段。

需要支持的操作是区间求值域段中的最小值、次小值、最大值，以及区间后继。每次询问需要 $O(\log W)$ 次 RMQ 和一次后继查询，因此可以做到 $O((n+q)(\log n+\log W))$ 的复杂度。