A. Acronym

枚举每个单词判断即可。

B. Baggage

考虑两个包裹分别从 $u$ 运到 $v$，中途没有同时运送两个包裹，则方案形如：

• 包裹 1 $u\to a_1$，空手 $a_1\to u$，包裹 2 $u\to b_1$，空手 $b_1\to a_1$，包裹 1 $a_1\to a_2$，空手 $a_2\to b_1$，包裹 2 $b_1\to b_2$，……，包裹 1 $a_k\to v$，空手 $v\to b_k$，包裹 2 $b_k\to v$。

可以发现这样的方案可以重新排列成：

• 包裹 1 $u\to a_1\to a_2\to\cdots\to a_k\to v$。
• 空手 $v\to b_k\to a_{k-1}\to b_{k-2}\to \cdots\to a_1\to u$。
• 包裹 2 $u\to b_1\to b_2\to\cdots\to b_k\to v$。

因此代价不小于 $2\mathrm{dis}_1(u,v)+\mathrm{dis}_0(v,u)$，其中 $\mathrm{dis}_c(x,y)$ 是从 $x$ 到 $y$，只能经过容量不少于 $c$ 的边的最短距离。

而 $2\mathrm{dis}_1(u,v)+\mathrm{dis}_0(v,u)$ 显然是一个合法方案，因此只需将 $u$ 到 $v$ 连上距离为 $2\mathrm{dis}_1(u,v)+\mathrm{dis}_0(v,u)$、容量为 $2$ 的边，然后求容量 等于 $2$ 的最短路即可。

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

C. Cows

二分答案，转化为判定是否能够在 $x$ 分钟内吃完所有的草。

按照 $i$ 从小到大的顺序，维护如下的状态：考虑下标在 $[i,n]$ 中的牛，且满足下列状态之一

• 存在不超过 $2$ 个时间区间，牛 $i-1$ 会在这些时间区间内帮牛 $i$ 吃草。有两种情况：
  • 如果在时间 $t$ 吃完了所有了牛 $i$ 的所有草，则牛 $i$ 可以在 $[t,x]$ 时间内帮牛 $i+1$ 吃草。
  • 否则，设剩余的草的数量为 $a$，则牛 $i+1$ 需要在 $[x-a,x]$ 时间内帮牛 $i$ 吃草。
• 存在一个时间区间 $[l,r]$，牛 $i$ 需要帮牛 $i-1$ 吃草。有两种情况：
  • 如果牛 $i$ 自己能够在 $l$ 时间之前吃完所有草，设吃完草的时间为 $t$，则牛 $i$ 可以在 $[t,l]$ 和 $[r,x]$ 时间帮牛 $i+1$ 吃草。
  • 否则，设在 $l$ 时刻剩余的草的数量是 $a$，则牛 $i+1$ 需要在 $[l-a,l]$ 时间内帮牛 $i$ 吃草。

如果最终牛 $n$ 不能吃完所有的草则说明答案大于 $x$。

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

D. Diminishing Fractions

分数的分母显然不超过 $M=\mathrm{lcm}\{1,2,\ldots,n\}$，而分子最小是 $1$，因此可能的最小值是 $1/M$。我们考虑通分，在 $\bmod M$ 意义下构造 $1$，然后只需减去整数部分即可（因为已知分子是 $1$，可以直接用浮点数计算）。

设 $\le n$ 的所有极大素数幂分别为 $p_1^{e_1},p_2^{e_2},\ldots,p_k^{e_k}$，则 $M=\prod_{i=1}^k p_i^{e_i}$。现在我们想要找到 $a_i\in [0,p_i^{e_i})$ 满足 $\left(\sum_{i=1}^k a_i(M/p_i^{e_i})\right)\bmod M=1$。

这可以通过 CRT 构造：我们希望 $x\bmod p_i^{e_i}=1$，所以令 $a_i$ 为 $M/p_i^{e_i}$ 在模 $p_i^{e_i}$ 意义下的逆元即可。

因为 $\sum n$ 很大但 $N=\max n$ 不大，我们在每组数据中分别进行求逆，则只需按照 $n$ 从小到大的顺序维护 $\prod_{j\ne i}p_j^{e_j}\bmod p_i^{e_i}$。每次增加一个素数幂时，都可以在 $O(k)=O(n/\log n)$ 的时间内完成维护。

总时间复杂度 $O\left(\frac{N^2}{\log^2N}+\sum n\right)$。

E. Express Rotations

考虑一个指向序列开头的指针，初始在 $a_1$ 之前。这样操作可以转化为指针循环向前移动、循环向后移动和删除指针之后的第一个数。

考虑设 $\mathrm{dp}(v,i)$ 表示删除了所有 $\ge v$ 的数，指针的位置在 $i$ 的最小代价。我们可以认为只有需要删除一个数时需要移动指针，因此有用的状态一定满足 $a_i=v$，因此总状态数是 $O(n)$ 的。

从 $v+1$ 到 $v$ 的转移，首先从之前所有有用的位置转移到所有 $a_i=v$ 的位置，这只需要先转移到前后相邻两个位置，然后再正反分别扫两遍更新。计算从位置 $i$ 向后移动到位置 $j$ 的代价，也就是计算 $[i,j)$ 中所有 $\ge v$ 的数的总和，可以用树状数组在 $O(\log n)$ 时间内计算。

接下来考虑删除所有等于 $v$ 的数。可以发现指针的移动要么是先往前再往后，要么是先往后再往前。如果是先往前再往后，可以认为所有数都是在往后的过程中被删除，因此直接用指针移动的代价减去所有 $=v$ 的数的总和来更新即可。如果是先往后再往前，因为往后移动的过程中，删除一个数不需要代价，但往前移动的过程中需要先移动到数之前再删除，所以有 $v$ 的代价。我们可以将少的代价在往后移动的过程中计算，即从 $i$ 移动到 $j$ 的代价是 $[i,j)$ 中所有 $>v$ 的数的总和减去 $v$。这会导致一个问题：移动的代价可能是负数，导致一直在环上绕圈。这是因为，我们只有在第一次删除一个数的时候会带来总代价的减少，但直接在环上转移忽略了这个限制。一个解决方案是使用单调队列，限制只能往后移动 $\mathrm{cnt}_v-1$ 次。

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

F. Frogs

考虑计算 $p=n$ 的答案。令 $b_i=a_{i+1}-a_i$（下标都是 $\bmod n$ 意义下的），即青蛙 $i$ 要追的青蛙和它坐标的差。如果 $b_i\ge 0$，则青蛙 $i$ 会向右跳，否则会向左跳。考虑 $b_i$ 的变化，当 $b_i\ge 0$ 且 $b_{i+1}< 0$ 时会减去 $2k$，当 $b_i< 0$ 且 $b_{i+1}\ge 0$ 时会加上 $2k$。可以发现，在有限轮之后，所有的 $b_i$ 都会落入 $[-2k,2k)$ 内。此后 $\{b_i\}$ 一定会进入一个循环，我们希望判断在一个循环内，青蛙的坐标是否不变。注意到当所有 $b_i\in[-2k,2k)$ 时，$b_i$ 的符号（负数还是非负）只和上一个时刻 $b_{i+1}$ 的符号有关，因此在循环中负数的个数是始终不变的，因此我们只需判断负数的个数是否等于非负数的个数。

我们只需判断是否有 $n/2=\sum[b_i< 0]=\frac{1}{2k}\sum(b_i\bmod 2k-b_i)$。注意到 $\sum b_i=0$，而 $\sum (b_i\bmod 2k)$ 是常数，因此只需判断是否有 $\sum(b_i\bmod 2k)=\sum((a_{i+1}-a_i)\bmod 2k)=nk$ 即可。

对于所有的 $p$ 计算答案，也只需要在 $p$ 增大的时候维护这个和。

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

G. Game MPO

将所有的 M 和 P、O 和 O 连边，则只需从所有大写字母开始 BFS 即可得到最终状态。

H. High Jump

最优策略可以表示成 $a_1< a_2<\cdots< a_k$，依次挑战高度 $a_1,a_2,\ldots,a_k$。分数的期望是 $p_{a_1}a_1+p_{a_1}p_{a_2}(a_2-a_1)+p_{a_1}p_{a_2}p_{a_3}(a_3-a_2)+\cdots$。令 $a_0=0$，这个式子也可以写成 $f(i)=(f(i+1)+(a_{i+1}-a_i))p_{a_{i+1}}$，答案即为 $f(0)$。

考虑从后往前 DP，则 $\mathrm{dp}(i)=\max_{j>i}\{(\mathrm{dp}(j)+j-i)\cdot p_j\}$，可以用凸包优化转移。

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

I. Imbalanced Teams

显然最大值等于前 $k$ 大的和减去前 $k$ 小的和。在确定了选择的数的可重集后，只需乘上对应的组合数即可。注意如果两个队伍有相同的数，还需要计算分组的方案数，并且当所有数全相等时，两组是本质相同的，方案数需要除以 $2$。

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

J. Just Zeros

考虑维护 $f(S)$ 表示翻转的行的集合是 $S$ 的情况下，还需要多少步能够将所有数变成 $0$。也就是翻转行后，每一列的 $\min\{c,1+h-c\}$ 之和。通过 $f(S)$ 可以在 $O(2^h)$ 时间内计算答案。

如何在操作后维护 $f(S)$：

• P 和 K 操作都只会影响一列，可以对每个 $S$ 重新计算该列的贡献。
• R 操作只需将 $f(S)$ 和 $f(S\oplus \{i\})$ 交换。注意需要打一个第 $i$ 行取反的标记，在另外两种操作中需要用到。

时间复杂度 $O((w+q)2^h)$。

K. Kindergarten Square

通过两行的差可以求出 $w$，而 $h$ 越大越好，然后判断是否满足条件即可。

L. Looping RPS

考虑对 $s_i^\infty$ 建立 Trie，则三个人形成一个环当且仅当它们在同一个点的三个不同子树内。因此建立 Trie 后可以直接枚举 LCA 计算贡献。

建立 Trie 分为两步：排序，然后计算相邻串的 LCP 并建立笛卡尔树。

难点主要在于排序，直接按照 $a+b< b+a$ 比较可能导致时间复杂度变为 $\Omega(n|s|)$。我们希望比较两个串的复杂度是 $O(\min\{|a|,|b|\})$，则总复杂度为 $O(\sum|s_i|\log n)$。不妨设 $|a|\le |b|$。如果 $a$ 不是 $b$ 的前缀则可以直接比较，否则我们需要求 $b$ 和 $b[|a|:]$ 的 LCP，这可以通过预处理每个串的 Z 函数后 $O(1)$ 得到。

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