题解 - The 4th Universal Cup. Extra Stage 5: Shenzhen

A

枚举长度 $l$，那么有解的一个必要条件是 $97l\le n\le 122l$，其中 $97$ 和 $122$ 分别是 a 与 z 的 ASCII 码。

可以用 zzzzz...caaaaa 这种方式来构造，考虑把第一个字母从 a 变为 z，第二个字母从 a 变为 z，一直这样重复下去，显然这可以满足 $97l\sim 122l$ 内任意的 $n$。

至多需要枚举 $\lfloor n/97\rfloor$ 次，因此复杂度为 $O(n)$。

B

如果我们可以给所有距离 $<d$ 的点连一条无向边，那么这就是一个二分图染色问题。

类比平面最近点对，令 $D=\lceil d/2\rceil$，那么按照 $(\lfloor x_i/D\rfloor, \lfloor y_i/D\rfloor, \lfloor z_i/D\rfloor)$ 给所有点分组。

同一组内最大距离为 $\cfrac{\sqrt{3}}{2} D < d$，所以每一组不能有超过三个点，否则无法二分图染色；其次，同一组内的点至多与周围 $5^3$ 个组内的点距离 $<d$，所以我们可以 $O(n)$ 给所有点对连边。

假设一个连通的二分图内有 $a$ 个白点，权值之积为 $w_a$；$b$ 个黑点，权值之积为 $w_b$。那么 $F(z)=w_az^a+w_bz^b$。

分治 NTT 把所有的 $F$ 乘起来即可，复杂度 $O(n\log^2n)$。

C

对于两个人的情况，可以查看官方题解，这里主要会对调整一次后 “边数减少” 这个事情进行说明。

令有向边 $i\to j$ 存在当且仅当 $w_i(S_i)<w_i(S_j)$，考虑增量构造，将 $1\sim m$ 依次分配。

1. 如果当前图内没有环，也就存在一个 $0$ 入度的点，我们直接把当前物品分配给这个点。

2. 否则，假设我们找到了一个简单环 $p_1\to p_2\to \cdots \to p_k \to p_1$，将它们的 $S_{p_1},S_{p_2},\dots, S_{p_k}$ 调整为 $S_{p_2},S_{p_3},\dots, S_{p_1}$，那么所有人的 $w_i(S_i)$ 都会增加。

   对于调整之前的所有边 $i\to j$，我们将它们分为四类。

   • 如果 $i,j$ 都不在环上，那么这条边依旧存在。
   • 如果 $i$ 在环上，$j$ 不在环上，那么这条边可能存在，也可能不存在。
   • 如果 $i$ 不在环上，$j$ 在环上，那么这条边会向前循环移动一个位置。比如 $i\to p_3$ 变为 $i\to p_2$，$i\to p_1$ 变为 $i\to p_k$。
   • 如果 $i,j$ 都在环上，那么这条边向前循环移动一个位置后，可能存在也可能不存在，但是不会产生自环。比如 $p_1\to p_3$ 变为 $p_1\to p_2$，但是 $w_1(S_1)$ 本身也变大了，这条边可能不存在；但是 $p_1\to p_2$ 不会变成 $p_1\to p_1$。

   反过来看，如果调整之后存在一条边 $i\to j$，通过上面类似的分类讨论，它一定可以对应到调整前的一条边上。

   所以边数每次至少减少了 $k$，我们反复调整直到这个图里没有环为止。

这样的话，我们对每次新增的集合询问 $n$ 个人对它的权值，恰好询问 $nm$ 次。

每次新增边至多 $n-1$ 条，每一条环边我们会以 $O(n^2)$ 的代价消掉，因此最终的复杂度 $O(n^3m)$。

D

如果每次都可以重分配，假设有 $W$ 个工人，我们一定会让他们去 $x_i$ 前 $W$ 大的工厂。

但是只有当一次添加工人操作可以重分配，剩下的时间并不能重分配。

我们考虑一次 w 操作后跟着若干个 f 为一组，假设这一组内的工厂为 $y_1,y_2,\dots, y_k$，之前的工厂为 $x_1,x_2,\dots, x_m$，都是从大到小排序，并且有 $W$ 个工人。

假设我们规定有 $l$ 个工人最终被分配去这一组内的工厂，那么它们带来的利润是 $\sum_{j} (k-j+1)y_j$，那么我们会把 $(k-j+1)y_j$ 从大到小排序后选前 $l$ 大的，剩下的的 $W-l$ 个工人会选择前 $W-l$ 大的 $x$。

因此我们可以把 $x$ 离散化后存到树状数组中，每次枚举所有的 $l$，树状数组二分找前 $W-l$ 大的 $x$ 之和即可。

由于所有的 $l$ 之和是 $O(n)$ 的，复杂度 $O(n\log n)$。

E

农民获胜有两种情况，要么是 $A$ 出完了所有的牌，要么是 $B$ 出完。

1. 如果是 $B$ 出完了所有的牌，那么它只能在最后一次出牌时出 $<p_c$ 的单牌。

   如果 $B$ 只有一张这样的牌，那么我们的流程就是 $A$ 将主动权传递给 $B$，然后 $B$ 出完自己所有的牌。

   传递主动权可以通过对子传递，也可以通过单张牌传递。如果通过单张牌传递，那么 $B$ 不能用 $<p_c$ 的单牌接受，除非 $B$ 只有这一张牌。

2. 如果是 $A$ 出完了所有的牌，那么我们只需要考虑 $A$ 手中 $<p_c$ 的单牌。

   存在两种情况：

   1. $B$ 用一张 $\ge p_c$ 的单牌接受，然后 $A$ 用一张更大的牌回收主动权，并且本轮结束。
   2. $B$ 用一张 $\ge p_c$ 的单牌接受，然后 $B$ 出一个对子，并且 $A$ 回收主动权，并且本轮结束。

   虽然我没有办法严谨证明，但是 $B$ 如果不结束本回合的话，他手里的牌会更少，不会优于直接结束本轮。

这样用 set 维护，复杂度 $O(n\log n)$。

F

定义 $dp(u,v)$ 表示 $u\to v$ 这个子树的 SG 值，每次 DFS 所有满足 $dis(v, x) \le k$ 的点 $x$ 并把相连的所有子树的 SG 值异或起来就是当前局面的 SG 值。

这里可以类似换根 DP 的处理方式在 DFS 的过程中维护当前所有子树的异或，代码如下：

int sg(int u, int f);

void dfs2(int u, int f, int d, vector<int>& out, int m = 0) {
  for (int to: go[u]) {
    if (to == f) continue;
    m ^= sg(to, u);
  }

  out.push_back(m);
  if (d >= k) return;
  for (int to: go[u]) {
    if (to == f) continue;
    dfs2(to, u, d + 1, out, m ^ sg(to, u));
  }
}

在一轮 DFS 结束后把 out 中的数求 MEX 就是当前子树的 SG，因此记忆化搜索即可，复杂度 $O(n^2)$。

G

对于 $n,m$ 其中之一是偶数的情况，可以构造出一条哈密顿回路；对于 $n,m$ 均为奇数的情况，并不能构造出来。

但是，我们并不是真的需要一条哈密顿回路，可以构造出来只是左上角一个点会变化的回路，我能构造出来的和官方题解一样，所以图我就不放了。

对于这个构造出来的两条变化的回路，它们只有一个点是不一样的，所以根据贪吃蛇的规则，这个蛇不可能在所有格子都被铺满之前咬到自己的尾巴。

构造出来之后就可以无脑让蛇头沿着图走了，复杂度 $O((nm)^2)$。

我在赛后让 Codex 造了一个可视化页面，有兴趣的读者可以看一下。

H

官方题解的括号匹配我没看懂，这里给出一个利用元素之和传递信息的做法。

假设 $a_1,a_2,\dots,a_k$ 是给定的 $S$，$b_1,b_2,\dots,b_{n-k}$ 是 $[n]\setminus S$，其中 $a,b$ 均升序排序。

假设插入之后的升序数组为 $a_1,a_2,\dots, a_i,b_j$，那么我们有 $b_j=i+j$，即 $i=b_j-j$。

我们希望通过 $\sum_{i=1}^k a_i + b_j$ 得到 $b_j-j$，于是我们选择 $j=n-k-\left(\sum_{i=1}^k a_i\right)\bmod (n-k)$。

这样 $\sum_{i=1}^k a_i+b_j \equiv b_j-j\pmod{n-k}$，又因为 $n-k>k$，所以 $i$ 可以被唯一还原出来。

复杂度 $O(n\log n)$，瓶颈在于排序。

I

本地 DFS 可以得知，由 $0\sim 6$ 构成的长度为 $6$ 的无序数组只有 $3000$ 个左右。

那么我们直接 $3000^2\times 36$ 打表即可，之后可以 $O(1)$ 回答询问。

实测直接提交打表程序也是可行的。

J

对于每一条横线，它们的代价是相同的，因此我们可以通过调整法说明从 $(0,0)$ 到达 $(a_i,b_j)$ 只会走一条竖线，但是我们无法得知走哪一条竖线。

基于上面这个观察，我们可以给出一个显然的式子：

$$\begin{aligned} f_{ij}&=\min\left\{\min_{k\le i}\{t_0a_i+t_kb_j\},\min_{k>i}\{2t_0a_k-t_0a_i+t_kb_j\}\right\}\\ &=-t_0a_i+\min\left\{2t_0a_i+\left(\min_{k\le i}t_k\right)b_j,\min_{k>i}\{2t_0a_k+t_kb_j\}\right\} \end{aligned}$$

令 $pre_i=\min_{k\le i}t_k$，$F_i(x)=\min_{k>i}\{2t_0a_k+t_kx\}$，那么我们枚举 $i=n$ 到 $i=1$ 的过程中维护 $F_i(x)$ 这个凸包。由于 $a_i$ 是单调递减的，那么 $y$ 轴上的截距就是单调递减的，相当于我们每次用一条直线去更新这个凸包，这是可以直接用栈维护的。

具体地说，我们用线段树维护一个数组 $C_1,C_2,\dots,C_m$，每次更新 $i$ 的时候从栈中获取到分界点，在分界线左边的我们进行 $C_j\gets 2t_0a_i+t_ib_j$。

我们再维护一个答案 $A_1,A_2,\dots,A_m$，每次需要额外对这个凸包用直线 $2t_0a_i+pre_i x$ 找到一个分界点，左边进行 $A_j\gets A_j+2t_0a_i+pre_i b_j$，右边进行 $A_j\gets A_j+C_j$。

如果你无脑使用矩阵维护，是会 TLE 的，就算你循环展开了也是不行。

所以我们维护修改操作 $(u,v,w,p,q,r)$ 表示 $(A_j,b_j,C_j) \gets (A_j+ub_j+vC_j+w, b_j,pb_j+qC_j+r)$，然后展一下式子看两个修改操作如何进行合并即可。

这样复杂度 $O(n\log n+n\log m)$。

K

有加法是及其难做的，所以我们对这个式子变形得到 $(a-k)(b-k)\equiv k^2\pmod n$。

在模 $n$ 意义下枚举所有的 $a-k,b-k$ 等价于枚举所有的 $a,b$，因此式子可以被化简：

$$\begin{aligned} f(n,k)&=\sum_{a=0}^{n-1}\sum_{b=0}^{n-1}[ab\equiv k^2\pmod n]\\ &=\sum_{a=0}^{n-1}\sum_{b=0}^{n-1}[(a,n)\mid k^2][\frac{a}{(a,n)}b\equiv \frac{k^2}{(a,n)}\pmod{\frac{n}{(a,n)}}]\\ &=\sum_{a=0}^{n-1}[(a,n)\mid k^2](a,n) \end{aligned}$$

于是就有：

$$\begin{aligned} \sum_{k=0}^m f(n,k)&=\sum_{k=0}^{m}\sum_{a=0}^{n-1}(a,n)[(a,n)\mid k^2]\\ &=\sum_{g\mid n}g\left(\sum_{k=0}^{m}[g\mid k^2]\right)\left(\sum_{a=0}^{n-1} [(a,n)=g]\right)\\ &=\sum_{g\mid n}g\left(\sum_{k=0}^{m}[g\mid k^2]\right)\left(\sum_{a=1}^{n} [(a,n)=g]\right)\\ &=\sum_{g\mid n}g\left(\sum_{k=0}^{m}[g\mid k^2]\right)\left(\sum_{a=1}^{n/g} \left[\left(a,\frac{n}{g}\right)=1\right]\right)\\ &=\sum_{g\mid n}g\left(\sum_{k=0}^{m}[g\mid k^2]\right) \varphi\left(\frac{n}{g}\right) \end{aligned}$$

其中 $g\mid k^2$ 我们可以通过质因数分解来看：枚举所有的质数 $p$，那么 $g\mid k^2$ 当且仅当 $V_p(g)\le 2V_p(k)$，这等价于 $\lceil\cfrac{1}{2}V_p(g)\rceil\le V_p(k)$，于是我们枚举 $g$ 的时候算出 $u(g)=\prod_p p^{\lceil\frac{1}{2}V_p(g)\rceil}$，那么答案可以进一步写为 $\sum_{g\mid n}g\varphi(n/g)(\lfloor m/u(g)\rfloor + 1)$。

直接试除法枚举因子即可，复杂度 $O(\sqrt n)$。

L

将 $v_i$ 从小到大排序后，设 $dp_{ij}$ 表示前 $i$ 个装备花 $j$ 个硬币可以达到的期望的最大值。

接下来枚举选或不选，如果选择，那么将有 $\cfrac{p_i}{100}$ 的概率为 $v_i$，$\left(1-\cfrac{p_i}{100}\right)$ 的概率为 $dp_{i-1,j-w_i}$，能这么转移的原因是前面的式子展开会形成相同的子结构。

类似 $01$ 背包转移即可，可以滚动数组压掉一维，复杂度 $O(nm)$。

M

枚举每一条线段，再枚举所有的展品，对于每一个展品我们处理出进入和退出的点，扫描线即可，复杂度 $O(nm)$。