A. Anthill/Honeypot Simulator

（注意，题解中的数学推导可能并不严谨。）

随机游走的结论是，两维的坐标是独立的，均值为 $0$，方差为 $\frac{T}{2}$ 的正态分布。即 $(x,y)$ 点的概率密度函数为 $$ f(x,y)=\frac{1}{\pi T}e^{-\frac{x^2+y^2}{T}} $$ 所求的概率即为 $f(x,y)$ 在一个半径为 $R$，圆心离原点距离为 $d$ 的圆内的积分。用格林公式得到上述积分等于 $\frac{1}{2\pi}\frac{1-e^{-\frac{x^2+y^2}{T}}}{x^2+y^2}(x\mathrm d y-y\mathrm dx)$ 在圆周上的积分。直接使用自适应 Simpson 积分在 $[0,2\pi]$ 上积分即可。注意当 $x^2+y^2\to 0$ 时，需要用到 $\frac{1-e^{-\frac{x^2+y^2}{T}}}{x^2+y^2}$ 的极限等于 $\frac{1}{T}$。

第二项则是上述的结果关于 $T$ 再做一个积分。如果再套一层自适应积分，效率可能太低，所以我们交换顺序，先对 $T$ 进行积分，然后进行相同的自适应 Simpson 积分。即要求 $$ \int_0^T \frac{1-e^{-\frac{r^2}{t}}}{r^2}\mathrm dt $$ 这个积分不是初等函数，结果是 $$ \frac{T}{r^2}\left(1-e^{-\frac{r^2}{T}}\right)-\mathrm{Ei}\left(-\frac{r^2}{T}\right) $$ 其中 $\mathrm{Ei}$ 是指数积分，可以用 C++ 标准库 `std::expint` 来计算。注意这个函数在 $r\to 0$ 时是发散的，因为当 $x\to 0$ 时 $$ \mathrm{Ei}(x)\sim \gamma+\ln|x|+O(x^2) $$ 但是其在 $x\in(-\epsilon,\epsilon)$ 处的积分是 $O(\epsilon |\ln\epsilon|)$ 的，我们可以合理地排除掉 $r^2$ 很接近于 $0$ 的部分。事实上，只要保证自适应 Simpson 积分时不会恰好命中 $r=0$ 导致算出 $+\infty$ 从而无限迭代，就能够计算出正确的结果。而考虑到浮点数自带的误差，不需要任何特殊处理也能够通过。

B. Missing Number

观察：只要值域大于数的个数，那么就一定存在一个数没有出现。

我们可以根据这一点对值域进行二分，二分的轮数恰好是 $\lceil\log_2(n+1)\rceil=8$。每一轮我们需要记录当前的左右端点以及在左半边的数的个数，总的状态数是 $O(n)$ 的，因此 $\log n$ 轮总共的状态数是 $O(n\log n)$。

C. String Workshop

观察：每次交换最左边的相邻逆序对，即插入排序，得到的就是最优解。

证明：设第 $i$ 个数左边比它大数的个数是 $c$，最终位置是 $j$，则它至少需要向左移动 $c$ 步，向右移动 $j-i+c$ 步，而插入排序一定是先左移再右移，是代价最小的。因此每个数的移动代价之和也是最小的。

上述的代价还可以用以下式子计算： $$ {n+1\choose 3}-\sum_{i=1}^n{c_i+1\choose 2} $$ 其中 $c_i$ 是第 $i$ 个数之前小于等于它的数的个数。可以考虑每个数先向左再向右，向左最终的位置就是 $c_i$，所以省掉了左边的部分。

因为值域（字符集）很小，用线段树维护区间中每个数的出现次数，出现次数前缀和，以及对于每个 $x$，所有满足 $s_i=x$ 的位置的 $c_i$ 和 ${c_i\choose 2}$ 之和，就可以在 $O(|\Sigma|)$ 的时间内合并。

对于修改操作 3，只需要打标记表示将区间依次赋值为 $a_1$ 个 $\tt A$，$a_2$ 个 $\tt B$，以此类推。打标记时也可以在 $O(|\Sigma|)$ 的时间内更新维护的信息。

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

D. Distinguishable Distributions

当 $t=1$ 时，我们可以构造一个只产生 $\tt H$ 的分布，然后如果字符串是 $\tt T$ 就认为是均匀分布，否则不是。这样的做法有 $\frac{3}{4}$ 的正确率，是满足要求的。

当 $t= 3$ 时，$t$-close 对概率误差的限制缩小到了 $\frac{3}{8}$，这时如果我们仍然令 $n=t$，其中 $3$ 个字符串不会产生，剩下的均匀分布，是达不到预期的正确率的。事实上，如果我们事先决定好要询问的下标，则策略一定形如当 $S$ 属于某个集合 $T$ 时认为是均匀分布，否则是我们构造的分布，而根据 $t$-close 的定义，我们的正确率不可能高于 $\frac{1+2^{-t}t}{2}$。也就是说，我们的策略必须依赖已经询问得到的结果。

以下我们都考虑 $01$ 串而不是 $\tt HT$ 串。沿用 $t=1$ 的思路，我们希望在我们构造的分布中保证正确，而在均匀分布中达到 $\frac12$ 的正确率。如果不要求 $t$-close，只需要让 $t$ 个字符不独立，例如要求其中有偶数个 $1$。这可以看成先随机 $(t-1)$ 位，再直接让最后一位是 $0$ 或者 $1$。现在有这个限制，我们可以依赖之前的 $(t-1)$ 位来决定后面的某一位。具体的，令 $n=(t-1)+2^{t-1}$，我们先均匀随机 $(t-1)$ 位，这些位组成了 $2^{t-1}$ 位的二进制数 $x$，我们要求后面的第 $x$ 位必须为 $1$，其余位均匀随机。查询时同样先询问前 $(t-1)$ 位，再查对应的位是否为 $1$ 即可。接下来只需要证明这样构造的分布是 $t$-close 的。

证明：设生成的字符串 $s$ 前 $(t-1)$ 位为 $x$，则 $s$ 的第 $(t-1)+x$ 位必然为 $1$，我们将这一位设为 $0$ 得到字符串 $\bar s$，则 $s$ 和 $\bar s$ 两两匹配。因为 $p_s+p_{\bar s}=\frac{2}{2^n}$，和均匀分布一样，所以如果选择的下标 $i_1,\ldots,i_t$ 不包含 $(t-1)+x$，则这一对 $s$ 和 $\bar s$ 不会造成 $s_{i_1}\cdots s_{i_t}$ 在均匀分布和我们构造的分布中概率的区别；而如果下标包含 $(t-1)+x$，则当 $s_{i_1}\cdots s_{i_t}\in T$ 而 $\bar s_{i_1}\cdots\bar s_{i_t}\notin T$ 时会导致概率比均匀分布大 $\frac{1}{2^n}$。对每个 $x\in[0,2^{t-1})$，有 $2^{n-t}$ 对这样的 $s$ 和 $\bar s$，最多有 $t$ 个下标，因此概率至多差 $\frac{1}{2^n}\cdot 2^{n-t}\cdot t=2^{-t}t$。

E. Four Sages Around an Oak Tree

猜测时的信息总共只有 $4\cdot 3\cdot 3=36$ 种情况，因此策略也只有 $3^{36}$ 种。考虑直接搜索正确的策略，正确的策略需要在所有 $3^4$ 种情形中都存在猜测正确的位置。也就是说，如果有一种情形已经存在三个位置猜测错误，则最后一个位置必须是正确的，我们可以利用这一点进行剪枝。除此之外，搜索时优先搜索同一种情形中的不同位置的猜测，这样可以尽快利用上面的观察进行剪枝。经过剪枝后，已经可以在时限内搜出策略，但为了更快可以将策略直接编入代码。

搜索的结果还表明，不存在关于颜色轮换对称的策略，这也说明要手动构造一个策略是相当困难的。

F. Pluses and Minuses

从后往前 DP，设 $f(i,j)$ 表示当前长度是 $i$，加号个数和减号个数的差是 $j$ 的方案数。则转移是 $f(i,j)=f(i-1,j+1)+f(i-1,j-1)$，然后如果 $i-1$ 在集合中，则 $f(i,i-2)$ 增加 $1$。要求的则是所有 $f(2n,0)$。

令 $F_i(x)=\sum_{j}f(i,j)x^j$，分治计算 $\{F_i(x)\}$。假设当前分治到区间 $[l,r]$，则 $F_l(x)$ 次数大于 $r-l$ 的部分不会对区间中的答案产生贡献，因此只需要乘上 $(x+x^{-1})^{r-l}$ 加到 $F_r(x)$ 即可。剩下的部分递归处理，返回的值由两部分组成：$F_l(x)$ 传入的部分对于 $F_r(x)$ 的贡献，以及 $[l,r]$ 中间新增加的部分，两部分的长度都不超过 $O(r-l)$，所以每次递归只需要进行 $O(r-l)$ 长度的卷积，总时间复杂度 $O(n\log^2n)$。

另一个做法

我们设 $f(i,n)$ 表示加减号各 $n$ 个且后缀至少有 $i$ 个减号的串的数量，$F_i(x)=\sum_{n} f(i,n)x^n$，则我们要计算的就是 $$ \sum_{i\in S}(F_i(x)-F_{i+1}(x)) $$ 而我们可以推出 $$ F_i(x)=\left(\frac{1-\sqrt{1-4x}}{2}\right)^i\frac{1}{\sqrt{1-4x}} $$ 这个式子可以这样考虑：首先末尾的 $i$ 个字符是减号，然后每次我们往前找到最短的且加号恰好比减号多一个的段，这一段一定是合法括号序列；当找到 $i$ 段后剩下的部分只要加减个数相等就可以。然后结合卡特兰数的生成函数就能得到上式。

令 $A(x)=\sum_{i\in S}(x^i-x^{i+1})$，则我们要求的就是 $A\left(\frac{1-\sqrt{1-4x}}2\right)\frac{1}{\sqrt{1-4x}}$，这可以通过以下几个步骤完成：

• 将 $A$ 右复合 $\frac{x}{2}$ 得到 $A\left(\frac{x}{2}\right)$。

• 将 $A$ 右复合 $1-x$ 得到 $A\left(\frac{1-x}{2}\right)$，这一步只需要卷积。

• 将 $A\left(\frac{1-x}{2}\right)$ 右复合 $\sqrt{1-4x}$ 得到 $A\left(\frac{1-\sqrt{1-4x}}2\right)$，令 $A\left(\frac{1-x}{2}\right)=A_0(x^2)+xA_1(x^2)$，则 $$ A\left(\frac{1-\sqrt{1-4x}}2\right)=A_0(1-4x)+\sqrt{1-4x}A_1(1-4x) $$ 仍然只需要卷积。

• 最后卷积上 $\frac{1}{\sqrt{1-4x}}$ 即可。

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

G. Traffic Lights

因为 $v$ 已经是黄色，我们只需要找一个红色点和一个绿色点在 $v$ 的不同子树，并且距离最短。也就是只需要找到和 $v$ 距离最近的两个在不同子树的红色点和绿色点。$v$ 子树内的情况只需要用线段树维护 DFS 区间的最小深度。$v$ 子树外的情况可以用点分树维护（官方题解做法）或者树上动态 DP，使用树链剖分或者 LCT，时间复杂度 $O((n+q)\log^2n)$ 或者 $O((n+q)\log n)$。

H. Sweet Remainders!

观察：当 $n>1$ 时，度数序列 $\{d_i\}$ 合法当且仅当 $d_i\ge 1$ 且 $\sum d_i=2n-2$。

如果存在 $a_i=-1$，只需要度数的最小值之和不超过 $2n-2$ 即可。否则还需要满足最小值之和和 $2n-2$ 的差是 $m$ 的倍数。

构造完度数序列之后，按照度数从大到小，每次在之前的点当中为当前点选一个父亲即可。时间复杂度 $O(n)$。

I. Wooden Checker

检查第一个条件很简单，只需要无向图没有环并且每个点的入度不超过 $1$。

对于第二个条件，当加入 $u$ 到 $v$ 的边之后，假设 $v$ 可达的区间是 $[l,r]$，那么对于 $u$ 的每个祖先 $x$（包括 $u$），$x$ 在之前可达的区间必须与 $[l,r]$ 相邻。这也就是说，要么 $u$ 的子树包含了该连通块的最小值且最小值等于 $l+1$，要么包含了最大值且等于 $r-1$。考虑每个连通块的两条路径：从根开始不断走向编号最小（且比自己小）的孩子得到的路径 $L$ 和不断走向编号最大（且比自己大）的孩子得到的路径 $R$。上述条件也就相当于 $u$ 需要位于对应的路径上，加边之后路径上在 $u$ 之后的点会被删除，替换成 $v$ 的子树中对应的路径。

上述条件可以用并查集和链表快速维护，时间复杂度 $O((n+q)\alpha(n))$。

J. Euler Line

欧拉线上包含了外心、垂心、重心和九点圆的圆心，其中重心的坐标是容易求的：$G=\frac{A+B+C}{3}$。将重心的坐标带入直线的表达式得到 $$ k(A_x+B_x+C_x)+l(A_y+B_y+C_y)+3m=0 $$ 由于坐标是整数，我们能够立刻得到一个必要条件：$\gcd(k,l)\mid 3m$。接下来我们给出对于满足上述条件的任意情况的构造。

构造的思路是从一些已知的三角形和其欧拉线出发，通过相似变换，也就是旋转、缩放和平移，最终得到想要的直线。

为了保证坐标仍然是整数，我们希望最终的变换是以下的形式：

• 先乘上矩阵 $M=\begin{pmatrix}p&-q\\q&p\end{pmatrix}$，其中 $p,q$ 是整数且 $p^2+q^2\ne 0$。这个 $M$ 表示旋转和缩放（考虑一般的旋转形如 $R_\theta=\begin{pmatrix}\cos\theta&-\sin\theta\\\sin\theta&\cos\theta\end{pmatrix}$）。
• 然后平移 $(t_x,t_y)$。

我们希望从简单的直线，例如 $3x+r=0\pod{r=0,1,2}$ 出发，通过上述变换得到想要的直线。带入上面变换的结果，我们得到这个直线的方程应该是 $$ k(px-qy+t_x)+l(qx+py+t_y)+m=0 $$ 化简一下得到 $$ (kp+lq)x+(lp-kq)y+(kt_x+lt_y+m)=0 $$ 对比系数，可以列出方程 $$ kp+lq=3a\\ lp-kq=0\\ kt_x+lt_y+m=ra $$ 令 $g=\gcd(k,l),p=\frac{k}{g},q=\frac{l}{g}$，则第二个方程能够满足，第一个方程可以解出 $a=\frac{(p^2+q^2)g}{3}$。第三个方程化为 $$ 3pt_x+3qt_y+\frac{3m}{g}=(p^2+q^2)r $$ 我们只需要选择合适的 $r$ 使得 $(p^2+q^2)r-\frac{3m}{g}\equiv 0\mod 3$，然后再选择合适的 $t_x,t_y$ 即可。而因为 $\gcd(p,q)=1$，所以 $p^2+q^2\not\equiv0\mod 3$，因此一定存在这样的 $r$。

最后还有两个细节需要处理：

• 找到欧拉线为 $3x+r=0$ 的三角形：只需要枚举所有坐标小的情况并检验即可。
• 坐标范围：假设基础三角形坐标范围是 $O(1)$，乘上矩阵 $M$ 之后的坐标范围则是 $O(p+q)$；平移的时候找到合适的 $t_x,t_y$，例如当 $|p|>|q|$ 时优先让 $t_y$ 的绝对值尽可能小，可以使得最终的坐标范围是 $O(|k|+|l|+|m|)$。

K. Traversal of a Triangular Grid

可以直接把图建出来跑欧拉回路，或者手动构造：先一直走到左下，然后每一层先直线走到最右边，再沿着斜线走一条锯齿状的路径到左边的上一层。

如图所示：

L. Triangles

观察：答案的上界是每一维的前 $\frac{n}{3}$ 大之和减去前 $\frac{n}{3}$ 小之和的两倍。

我们可以直接把所有坐标排序后三等分，变为 $0,1,2$，则要达到上界，每个三角形都必须包含横坐标为 $0,2$ 的点和纵坐标为 $0,2$ 的点。事实上我们可以做到每个三角形中横纵坐标的集合分别是 $\{0,1,2\}$ 的排列。我们只需要证明在每个横坐标的纵坐标的出现次数都是 $\frac{n}{3}$ 的前提下，能够选出这样的三个点，则递归构造即可。实际上这就是正则二分图完美匹配这个经典问题，结论是完美匹配一定存在。因此这个题目可以从三个点推广到任意 $k$ 个点。

实现时可以直接暴力枚举 $3!$ 种排列。时间复杂度 $O(n)$。

M. Construction Company

观察：一组工作能被 $a$ 个工人完成当且仅当任意时刻同时进行的工作数量不超过 $a$。

我们先把工作分配给清醒工人，满足以下两个条件：

• 所有困难工作都被完成。
• 每个时刻未完成的简单工作数量不超过 $b$。

我们用一条长度 $2m$ 的链表示时间，流过链上的边 $i\to i+1$ 表示一个工人在 $[i,i+1)$ 这段时间是空闲的。每个工作 $[l,r)$ 连边 $l\to r$，容量为 $1$；并且如果是困难工作，则这条边的下界也为 $1$。源点连向链首和链尾连向汇点的边容量为 $a$。

对于第二个限制，如果 $[i,i+1)$ 时间段有 $c_i$ 个工作需要完成，则其中至少有 $c_i-b$ 个需要被清醒工人完成，也就是说在 $[i,i+1)$ 这段时间空闲的工人数量不能超过 $a-(c_i-b)$，因此 $i\to i+1$ 的容量就是 $a-(c_i-b)$。

建图后跑一个上下界可行流，流量、点数、边数都是 $O(m)$，因此复杂度不超过 $O(m^2)$。