百度之星比赛题目讲解

按照难度排序。

G. Cafeforces

可以钦定第一个账号用来上分，第二个账号用来处理不利于第一个账号上分的比赛，这样问题就能等价转化为只有一个账号，但是可以从 $n$ 场比赛中选一些来打，问最后评分的最大值。

设当前评分为 $x$，本场比赛表现分为 $y$，显然只有 $x<y$ 时打比赛才更优。即一场比赛后的评分会变为 $\max(x,\lceil\frac{x+y}{2}\rceil)$。从前到后扫一遍即可。

D. Left and Right

当且仅当 $l = r \ne 1$，答案是 infty。当 $l=r=1$ 时答案为 $0$。

如果 $l \neq r$，枚举你可以将 $x$ 拆分为的数字个数 $k \in \mathbb N_+$，你能得到无穷多个区间 $[kl, kr]$。你需要求不在任何区间内的正整数 $x$ 个数。而注意到一旦在某个 $k_0$ 满足 $k_0r \leq (k_0+1)l$ 时，所有超过 $k_0l$ 的 $x$ 都一定能表示；如果让 $k_0$ 是满足该性质的最小 $k$ 取值，那么对于所有小于 $1 \leq i \leq k_0$，都有 $[(i-1)r+1, il-1]$ 内的 $x$ 无法被表示，而这些区间的长度和是一个等差数列求和。单次询问时间复杂度 $\mathcal O(1)$。

A. Bus Station

如果存在 $w(u, v), w(v, w) \in S$，总是能调整为 $w(u, w)$，于是对所有需要被统计的集合 $S$，每个点在 $S$ 内的出现次数等于其度数模 $2$，并且容易证明这是最优的。

进一步地，对于一个点 $x$，考虑所有 $x$ 的邻边，其中有 $deg_x \bmod 2$ 条是特殊的（被覆盖路径的一条端点恰好为 $x$），而剩下的 $\lfloor \frac{deg_x}{2} \rfloor$ 对可以自由配对，并且对每个结点，覆盖其的所有路径的配对方案都是独立的，于是答案只和所有 $deg_x$ 有关。具体地，答案是所有 $(deg_x - 1 + (deg_x \bmod 2))!!$ 的乘积。时间复杂度 $\mathcal O(n)$。

C. GCD Xor MEX

考虑对 $\operatorname{mex}$ 的值 $x$ 分类讨论：

• 若 $x = 0$，则异或和等于 $\gcd$，直接枚举 $\gcd$ 的值并更新答案即可。
• 若 $x = 1$，则必须选择 $0$，异或和等于 $\gcd$ 的值异或 $1$，同样可以枚举 $\gcd$ 的值。
• 若 $x \geq 2$，则选择的数中总是存在 $0, 1$，所以 $\gcd$ 总是为 $1$，枚举 $\operatorname{mex}$ 的值更新答案即可。

每次答案更新都形如一个区间和一个数取 $\max$，容易解决这个问题。时间复杂度 $\mathcal{O}(V (\log n + \log V))$。

E. Odd Occurrence

首先考虑整个序列只有一个数。此时长为 $i$ 的子序列出现了 $\dbinom{n}{i}$ 次，而根据 Lucas 定理的推论，$\dbinom{n}{i}\bmod 2=[i\subseteq n]$。这意味着 $[1,n]$ 的所有数在二进制下都是 $n$ 的子集，也就是存在正整数 $k$ 使得 $n=2^k-1$。所以对于原序列的每种元素，其在原序列中出现次数必须恰好形如 $2^k-1$，否则不合法。

然后考虑整个序列只有两个数。假设一个数是 $1$，出现了 $x$ 次；一个数是 $2$，出现了 $y$ 次。那么序列中 $1,2$ 和 $2,1$ 的总出现次数是 $xy$。又 $x,y$ 都是奇数，所以 $xy$ 是奇数。如果 $1,2$ 和 $2,1$ 同时出现，那么必然只能是奇数+偶数=奇数，出现了一个偶数，不满足。这意味着 $1,2$ 和 $2,1$ 不能同时出现，即 $1$ 和 $2$ 的下标范围不能有交。从而我们推出，原序列满足条件的充要条件是，每种数出现次数形如 $2^k-1$，并且所有出现位置都是连续的一段。$\mathcal O(n)$ 或 $\mathcal O(n\log n)$ 判断即可。

B. Plants vs Zombies

假设当前考虑了 $[1, r]$ 内的陷阱摆布情况，所有剩余的血量 $> r$ 的敌人里，生命值最小为 $m$。那么此时有两种决策：

• 在 $(r, m]$ 内摆放至少一个陷阱。因为可能要摆放很多个陷阱，所以先在位置 $r+1$ 摆放是不劣的。因为目前所有剩余的敌人集合就是会踩到这个位置的敌人集合，可以计算出这个陷阱会直接击杀哪些敌人，随后转移到 $r \gets r + 1$ 的状态；
• 在 $(r, m]$ 内不摆放任何陷阱。于是生命值等于 $m$ 的所有敌人自然死亡，转移到 $r \gets m$ 的状态。

考虑设 $T(n)$ 表示在给出 $n$ 个敌人的情况下，计算所有可能情况的时间复杂度。有 $T(n) = T(n - \frac{n}{k}) + T(n - 1) + \mathcal O(n)$。在题目给出的限制条件下，$T(n)$ 在可以接受的范围内，于是暴力 dfs 的时间复杂度就是 $\mathcal O(T(n))$ 的。

通过对所有可能到达的状态 BFS 扩展会比暴力 DFS 的效率大概快 10 倍左右，详见给出的 std-2.cpp。但两种做法应该都可以通过。

H. Soupo

直接在 Treap 上维护循环卷积，考虑到插入的期望旋转次数都是 $O(1)$ 的，考虑到交换律，你可以把插入遍历时的 pushup 换掉改成卷一个两项的多项式，只有在旋转时的 pushup 是需要重新跑一遍 $k\times k$ 的循环卷积的。

不妨设你的插入删除次数是 $q_1$ 而翻转或查询次数是 $q_2$，那么你的复杂度是 $O(q_1(k+\log n)k+q_2k^2\log n)$。

出题人在 std 中使用的是无旋 treap，旋转对应的就是无旋 treap 找到位置后进行分裂的那段路径，因此这样做实际是一样的。

事实上替罪羊树也能做到这个复杂度，因为你对一个大小为 $n$ 的树重构的时间复杂度为 $O(nk)$，因为大小超过 $k$ 的子树只有 $O(\frac{n}{k})$ 个，但是我还没有写过这个做法。

F. Operation

以下设 $V$ 为值域。

首先，我们用在 trie 树刻画操作过程：把这些区间中的数从低位到高位插入 trie 树中，则在这颗 trie 树上 dp 即可求出答案。

显然我们不可能真正将这些数插入。于是我们观察一个区间数的性质。

我们考虑从高位到低位的数位 dp 的过程，则一个区间一定可以划分为 $O(\log V)$ 个区间，其中每个区间都形如“前几位固定，后几位任意选 $0/1$”的形式。

我们用正则表达式刻画这类区间，容易发现是可以刻画的：前几位确定，后几位是 $\mathrm{*}$，倒着插入后即为“前几位是 $\mathrm{*}$，后几位确定”于是，我们建立正则自动机，在这个自动机上 dp 即可得到答案。

注意到，因为这个正则表达式的特殊性质，我们并不需要跑建立朴素正则自动机的算法。我们考虑这样一个算法来建立自动机：

• 把拆分后得到的 $O(n\log V)$ 个区间按照 $\mathrm{*}$ 的长度从大到小排序。排序的目的是防止 $\mathrm{*}$ 少的串破坏下文中链状 DAG 的结构。

• 首先，在 trie 上插入一条链状 DAG，形如“$1$ 到 $2$ 有两条边（$0/1$），$2$ 到 $3$ 有两条边（$0/1$）等”，长度为最长连续 $\mathrm{*}$ 的长度。

• 然后，每次插入一个串时：

  • 首先跳若干次 $\mathrm{*}$。

  • 然后，按照插入 trie 的方式插入。注意到我们为了保证之前插入的部分和现在插入的部分不会组合出新的串，我们需要可持久化的插入方式，即插入时要把当前要走到的节点复制一份再走。

于是就做完了。复杂度 $O(n\log^2 V+q\log V)$。