【题解】牛客挑战赛82

T1狩影·进击

容易证明，Kendieer 的最佳决策是每过x秒吃掉一个a值最大的企鹅士兵。

问题的核心在于如何计算企鹅大军的总伤害。考虑将每个连续的 $x$ 秒合并计算（因为在这段时间内，企鹅大军造成的每秒伤害不变）： $x$ 秒的总伤害 = $\min(剩余企鹅的∑a_i,k)$ 。

因此，将企鹅大军按照a值从小到大排序后，重复执行以下过程：计算每x秒的企鹅伤害，删去末尾的企鹅。时刻判断总伤害是否大于初始血量即可。

T2雪遁·逃生

题意：把字符串 $S$ 划分成若干连续子串，子串序列字典序不下降，求最多段数。

预处理任意后缀对的最长公共前缀 $lcp[i][j]$ ，使任意两段比较 $A$ 和 $B$ 在常数时间内可判定谁更大。设 $lenA$ 为 $A$ 长度， $l = lcp[a][c]$ 。若 $l \geq lenA$ 则任意长度 $\ge lenA$ 的 $B$ 都满足 $A \le B$ ；否则通过比较 $s[a+l]$ 与 $s[c+l]$ 得出结论。

考虑动态规划，设状态 $dp[end][start]$ 表示将前缀 $S[0..end-1]$ 划分且最后一段为 $S[start..end-1]$ 时的最大段数。初始化 $dp[j][0]=1$ （把前缀当一段）。

状态转移过程为：若上一段为 $[prev_{start}, prev_{end})$ ，下一段为 $[prev_{end}, j)$ ，当且仅当 $A \leq B$ 时可转移：

dp[j][prev_{end}] = max(dp[j][prev_{end}], dp[prev_{end}][prev_{start}] + 1)

对于固定 $(prev_{start},prev_{end})$ ，满足 $A\leq B$ 的 $j$ 是从某个最小 $j0$ 开始到 $n$ 的连续区间，因此只需算出 $j0$ （用 $lcp$ 常数时间得到）。

对区间更新进行优化，对每个 $prev_{end}$ 用 $best[j]$ 记录各 $prev_{start}$ 对应的最小起始位置 $j0$ 的候选值，然后做一次前缀最大化把 $best$ 批量写回 $dp$ 。这样把枚举三重循环的第三层合并，整体变为 $O(n^2)$ 。

答案为 $\max_{0\leq i\le n}\{dp[n][i]\}$ 。

时间复杂度：预处理 $lcp$ $O(n^2)$ ，动态规划 $O(n^2)$ 。

T3神木·溯源

考虑树形 $dp$ 。需要维护的信息如下：

$f(u)$ 表示仅考虑以 $u$ 为根的子树中，强制选取 $u$ 时的最大答案；

$g(u)$ 表示考虑整棵树中，强制选取 $u$ 时的最大答案；

$h(u)$ 表示仅考虑以 $u$ 为根的子树中的最大答案；

$s(u)$ 表示考虑整棵树中，强制不选取 $u$ 时的最大答案。

计算上述四个函数：

$f[u] = ∑\max(0, f[v])$
$g[u] = f[u] + lst$ ，其中 $lst$ 表示 $u$ 上方能与 $u$ 相连的最大答案。可结合祖先的 $f$ 函数在 $dfs$ 过程中顺带计算得出 $lst$ （细节见标程）；
$h[u] = \max(f[u], h[v])$
$s[u] = \max(val, h[v])$ ，其中 $lst$ 表示 $u$ 上方的最大答案。

可结合祖先的 $f,g,h$ 三个函数在 $dfs$ 过程中顺带计算得出 $val$ （细节见标程）。

在上述四个函数的基础上计算答案：

若 $\max(g[pos] + x - a[pos], s[pos])$ 不为 $0$ ，则答案即为上述表达式（选取 $u$ 和不选取 $u$ 的两种情况取较大值）；

若 $\max(g[pos] + x - a[pos], s[pos])$ 为 $0$ ，则答案为整棵树中最大的一个点权（因为不能选取空集）。

T4试炼·终境

先将问题转化为“对于每个 $i$ ，都寻找一个数与 $i$ 配对”。观察发现，想要不“浪费”任何一个二进制位，就要尽可能地让所有二进制位互补。例如： $101$ 与 $010$ 配对， $10010$ 与 $01101$ 配对。

可以先尝试计算一下 $∑i⊕a_i$ 可能的上界。对于每一个二进制位，若 $1-n$ 中的所有数字在该位上 “ $1$ ” 的个数之和大于 “ $0$ ” 的个数之和，则显然无法通过配对使所有的 “ $1$ ” 都被利用上（也就是说，肯定要“浪费”至少一个 $1$ ），例如有三个数 $1、2、3$ ，那么在二进制的第 $0$ 位上有 $2$ 个 “ $1$ ” ， $1$ 个 “ $0$ ” 。又由于所有数字是 $1-n$ 的排列，故该位上 “ $1$ ” 的个数之和至多比 “ $0$ ” 的个数之和大 $1$ 。综上， $∑i⊕a_i$ 的一个上界为 $∑i$ 减去所有满足条件（ “ $1$ ” 的个数之和大于 “ $0$ ” 的个数之和）的二进制位的值。

存在多种能达到这种答案上界的构造方法，以下介绍其中相对简单的一种。

若 $n$ 表示当前需要考虑 $1-n$ 中各个数字对应的 $a_i$ 值，令 $n’$ 为 $n$ （以 $n$ 的最高位）取反后的值：

若 $n’$ 不为 $0$ ，则对于 $n’-n$ 范围内的每一个数 $i$ ，令 $ans[i] = n - i + n’$ 。而后，令 $n := n’ - 1$ ；
若 $n’$ 为 $0$ ，则 $ans[n] = n$ 。而后，令 $n := n - 1$ ；

反复执行以上过程直到 $n$ 为 $0$ 即可。

T5时锁·封印

在本篇题解中作以下约定：最终答案指要求输出的答案，选取子串指最终答案在进行循环排列之前的结果，最大字符指输入的字符串中字典序最大的字符，连续段指由若干最大字符组成的子串。

根据本题的要求，想要找到字典序最大的答案，需要优先考虑最大字符。不难理解，最终答案的开头一定是最大字符。

先进行一个分类讨论：

假设存在若干由最大字符组成的连续段（比如样例中的 $bbaba$ 就存在 $bb$ 和 $b$ 两个连续段）。由于可以进行循环排列，故选取子串的首尾一定是恰好两个连续段。因为这样可以使最终答案的开头由更多的最大字符构成。

假设仅存在一个由最大字符组成的连续段，那么它一定在选取子串中。

关键观察：最长的（如果存在同样长的则取最靠后的）连续段，一定会出现在最终答案中。

证明：如果不存在同样长度的连续段，则结论显然成立；如果存在同样长度的连续段，采用反证法，若选取子串不包含最长且最靠后的连续段，那么选取子串的首尾一定都是同样长度的连续段，此时若将尾部延伸至最靠后的连续段，等价于在最终答案之后添加了一段字符，根据字典序的定义，不如选取最靠后的连续段更优。

于是，我们可以根据上述分类讨论进一步研究实现方法：

如果存在若干由最大字符组成的连续段，那么最靠后的最长连续段一定是选取子串的开头或结尾。若在开头，则将该连续段之后的整个子串截取出来，再寻找一次最靠后的最长连续段作为选取子串的结尾即可。若在结尾，则将该连续段之前的子串截取出来，则问题等价于选取一个最大的后缀。可以在 $O(n)$ 复杂度完成或使用后缀数组在 $O(nlogn)$ 的复杂度内完成。两种情况取字典序最大值即可。

如果仅存在一个由最大字符组成的连续段，则先将该连续段之前的子串截取出来，仍然选取一个最大的后缀。而后，再将该连续段之后的子串截取出来，逐个枚举并添加前缀字符，直到该字符小于前述后缀的开头字符即可。需要留意边界情况。

总时间复杂度和空间复杂度均为 $O(n)$ 。

T6时殒·残篇

将内层的两个求和看作一个整体，即先计算 $\sum_{j=1}^i\sum_{\substack{k=1\\ \gcd(k,i)=j}}^ik^p$ 。不难发现，对于每个 $j$ ，存在唯一的 $k$ 使得 $\gcd(k,j)=j$ 。其实际意义是将集合 $S=\{1,2,...,i\}$ 划分为若干个互不相交的子集 $S_j=\{k\in S\mid\gcd(k,i)=j\}$ ，由于 $k$ 的唯一性，所有 $S_j$ 的并集即为 $S$ ，做到了遍历所有的 $j$ 。因此， $\sum_{j=1}^i\sum_{\substack{k=1\\ \gcd(k,i)=j}}^ik^p=\sum_{j=1}^i j^p$ ，原式化为 $\sum_{\substack{i=1\\ \gcd(i,n)=d}}^n \sum_{j=1}^i j^p$ 。

令 $S_p(x)=\sum_{k=1}^x k^p$ ，原式变为 $\sum_{\substack{i=1\\ \gcd(i,n)=d}}^n S_p(i)$ 。把 $i=d\cdot t$ ，并令 $n' = n/d$ （易知若 $d\nmid n$ 则答案为 $0$ ），条件 $\gcd(i,n)=d$ 等价于 $\gcd(t,n')=1$ 且 $1\le t\le n'$ 。于是问题变为