MOCK NOIP 20221117 日志

T1 的 Hack 数据提醒我，尽管时间复杂度没有变化，但所有想到剪枝和常数优化在时限不充裕的题目中仍是必要的。

T2 没有认真读题，忽略了“恰执行一次”的要求。

T3 里面没有使用自己熟悉的存边方式，时间趋紧的情况下代码实现出错。这再次告诫我应以求稳为重。

简单题解

A – 跳棋

从 $(x,y)$ 跨步跳能够跳到 $(x\pm 2,y),(x,y\pm 2)$，以及 $(x+k,y+k),k=\pm 2$。可以发现 $x,y$ 奇偶性均不变。我们只需要考虑所有存在棋子的格子及其邻居。它们形成若干连通块，在这些连通块上 BFS 即可。

若采用 std::map 存储，时间复杂度为 $\newcommand\bigO{\operatorname{O}}\bigO(7n\log n)$。需要采纳“避免遍历不存在的连通块”之类的优化。

B – 最小基因序列问题

题目所述操作即“将区间翻转后每个位置‘反转’（$\mathtt{T\leftrightarrow A,G\leftrightarrow C}$）”。考虑从前往后贪心枚举区间左端点。若其后方不存在翻转反转后比它严格更小的字符，则在此处操作不优（若翻转后与原串的首尾字符相等，如 $\mathtt{A\cdots T}$，显然等价于只操作 $\mathtt{A,T}$ 中间的一段）。

找到最优左端点 $l$，找到最小可能的右端字符 $c$。可能有多个位置满足 $s_r=c$。对这些位置在翻转反转后的序列（记作 $\overline{s}$，其长度为 $p=n-l+1$）上后缀排序，则后缀数组存在一个前缀 $\newcommand\sa{\operatorname{sa}}\sa(1),\cdots,\sa(k)$，满足 $\overline{s}_{\sa(i)\cdots p}$ 是 $\overline{s}_{\sa(i+1)\cdots p}$ 的前缀，最优方案存在于这个前缀当中。比较这些前缀可以采用两个指针在 $s$ 和 $\overline{s}$ 上分别移动比较对应位置字符的方式在线性时间内完成。

如果发现不执行操作最优，鉴于题目要求操作“恰好一次”，则我们反转最后一个字符。 痛失 $\text{10 pts}$。

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

C – 摆件

注意到所有颜色相互等价，且实际填充过程中至多只有 $n$ 种颜色是有实际意义的。当 $n$ 较小时，我们枚举节点 $x$ 所属的编号最小的颜色集合并计算代价，复杂度为 $\bigO(B_n)$，$B_n$ 乃贝尔数（将 $n$ 个互异元素划分为若干个集合的方案数）。在 $n\leq 11$ 时有 $B_n\leq 7\times 10^5$，可以接受。

对于一棵树，由于每个颜色等价（在某节点填写颜色 $A$ 的子树方案数，必定等于填写颜色 $B$ 的子树方案数）我们有简单的 $\bigO(n)$ DP：$f(x)$ 表示 $x$ 的子树内的方案数。

对于更大的 $n$，我们发现有 $m-n\leq 9$。结合树的部分分，我们猜想是利用生成树的某些性质。考虑任意一棵全图的 DFS 树（无向图的 DFS 树没有横叉边，只可能有返祖边），将所有返祖边的更深一侧端点的所有边“断连”。那么，不考虑“断连”的边的全图，就是一个由若干孤点和若干棵树组成的森林。可以得到有 $k\leq 10$ 个这样的孤点。枚举 $B_k$ 次这些孤点的颜色划分，记某种划分采用了 $t$ 种不同颜色。对于森林的部分，我们 DP 统计方案数：$f(x,c),c\in\{0,1,\cdots,t\}$，表示在 $x$ 填写 $t$ 种颜色以外的颜色/第 $1,\cdots,t$ 种颜色的方案数。转移时注意统计“断连”边的权值。

精妙的优化

下文中默认已合并了重边的权值。

对于度数为 $1$ 的点，我们总是恰有 $K-1$ 种颜色使得它和邻居颜色相异，反之相同。于是记邻边编号为 $i$，答案恒乘上系数 $\text{diff}_i\times (K-1)+\text{same}_i$，随后删去该点。

对于度数为 $2$ 的某个点 $x$，记它连接了 $y,z$ 两点。则当 $y,z$ 颜色相同时，$x$ 的两邻边有 $K-1$ 种方式均采纳 $\text{diff}$ 权值，反之亦然；若 $y,z$ 颜色不同，则两条边的权值可以分成三类讨论。于是产生/合并新边 $(y,z)$ 后删去该点和两邻边。

最后，每个有邻居的点的度数均不小于 $3$。记最终剩余 $m’$ 条边，$n’$ 个点，有 $3n’\leq 2m\space(*)$。同时在该过程中，恒有 $m’-n’=m-n\leq 9\space(**)$，于是有 $n’\leq 18$（此时不等式 $(*)$ 取等号得到 $m’=27$，卡到 $(**)$ 上界）。

时间复杂度 $\bigO(B_k\times n),k\leq 10$，实际上不采纳方才的优化是难以通过的。

D – 百分号

建出（儿子有序的）括号树，存在从节点 $x$ 到它的首个儿子（的左括号状态）和末儿子（的右括号状态），以及从 $x$ 左、右括号向对应方向兄弟右、左括号态的连边。

则从括号节点 $u$ 到 $v$，必然经过 $\newcommand\lca{\operatorname{lca}}\lca(u,v)$ 或它的儿子。设 $f_u(x,0/1)$ 表示从节点 $u$ 到达 $x$ 的左/右括号态的最小步数，$f_v(x,0/1)$ 同理。我们向 $f_u(\operatorname{fa}(x),0/1)$ 转移，分情况讨论系数。运算 $(\min,\cdot),(+,+)$ 满足幺半群性质，可以使用广义矩阵乘法在树上倍增/树剖优化。

时空复杂度 $\bigO(n\log n)$。