MOCK NOIP 20221108 日志

中规中矩的一场模拟赛。

T1 写得实在是太久了……这也是没办法的事情——如果不对转移作压缩优化就没办法过。

T2 有我喜欢的马拉车 Manacher 算法，是印象里第二次在模拟赛应用。

然后就没时间了。后两题仍然只有暴力分，但最近频繁遇到跟凸包和线性函数相关的题目，这使我发现 T3 跟它相关。在最后一点时间里实现了构建凸包的函数。代码本身没问题，但思路是错误的。

简略题解

A – 石蒜反冲

这好像是很早以前的译名了。现在它叫《莉可丽丝》。

遇见多模式串匹配，自然想到自动机上 DP。但我们发现题目中给定的两个串 sakana chinanago 在任何一个文本串中最多只能匹配其中一个，且匹配位置唯一。于是简单计数 DP 转移，记录当前二者匹配数之差与目前匹配位置即可。

一些不应用就过不了的优化：

• 二者数量之差可只记录到 $\frac{n}{15}$。$15$ 是两个串的总长度。
• 转移时对于 ? s c a o 还有其他字符分类讨论，保证单次转移复杂度为 $\newcommand\bigO{\operatorname{O}}\bigO(1)$。

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

B – 回文

考虑一个询问 $[l,r]$，记其中点为 $\text{mid}$。如果一个回文串的回文中心 $c \geq \text{mid}$，则其能够为 $[l,r]$ 贡献的回文长度要不然受自己的极长回文半径限制，要不然受到 $r$ 的限制而没法扩展；在 $c\leq \text{mid}$ 时同理。

在回文长度只受到 $r$ 限制时，记中心 $c$ 的极大回文半径为 $d$。于是它能贡献的长度是一个形如 $\text{len}=\min\{d,r-c\}$ 的一次函数。我们要查询的是所有 $c\in[mid, r]$ 的这样的函数在 $r$ 处的值。这是可以简单用前缀数据结构维护的。于是按次序遍历、更新与查询决策集合即可。

C – 薅羊毛

设 $d$ 为天数。当 $d$ 较小时，可以在分层图上简单 DP 求得 $f(x,i)$：当走了 $i$ 条边到达 $x$ 时得到的最大权值。

可以通过调整法简单证明：当可用步数 $d$ 给定时，最优方案是一条从 $1$ 到某节点 $v$ 的路径，随后在某条边 $(v,u)$ 上反复横跳。进一步观察发现：

• 这条边 $(u,v)$ 的权值大于先前的路径上任意一条边的权值；
• 该路径是一简单路径，不会有环；
• 若最终我们选择到达 $v$ 且存在多条权值不同的路径，则对于不同的 $d$，我们的选择可能不同；
• 若存在多条经过 $i$ 条边的到达 $v$ 的权值和不同的路径，我们显然总是选择其中权值最大的。

那么，将 $d$ 看做自变量，若我们最终通过 $i$ 条边到达节点 $x$，这 $i$ 条边的最大权值和为 $s_{x,i}$，且 $x$ 的邻边的最大权值为 $w_x$，则能够得到一次函数 $g_{x,i}(d)=(d-i)w_{x}+s_{x,i}$。构建这 $\bigO(n^2)$ 个一次函数最大值的单调栈统计答案即可。

时间复杂度 $\bigO(n^2)$ 或者 $\bigO(n^2 \log n)$，取决于你想不想用基数排序。

D – 尼姆游戏

这道题让我想起了天元编程邀请赛的 T3。

如果一条路径的 mex $=p$，则它显然应当经过 $0,1,\cdots, p-1$；而假若我们知晓 $0,1,\cdots, p-1$ 能在树上构成一条简单路径 $x\rightarrow\cdots\rightarrow y$，那么以 $x,y$ 为根的两子树内分别任取一个点 $u,v$，则路径 $u$ 到 $v$ 的 mex $\geq p$。

而树上任意两点之间简单路径的权值异或和是很好计算的：记 $f(x)$ 表示以某固定节点 $\text{rt}$ 为根时从根到 $x$ 的异或和。则 $f(x)\operatorname{xor} f(y)$ 就是 $x$ 到 $y$ 路径的权值异或和。又因为当上文所述的所有合法的 $u$ 的 $f(u)$ 已知时，考虑一确定的 $f(v)$，我们可以利用 Trie 在 $\bigO(\log A)$ 的时间内查询是否存在一个 $f(u)$ 满足 $f(v)\operatorname{xor}f(u)\in [l,r]$。故而我们可以二分每个询问的答案，每次暴力检查 mex $\geq \text{mid}$ 时路径两端子树内有没有节点满足要求即可。

实现时需要注意“将 $p$ 并入某条路径时需要同时加入其到路径端点上所有点”这样的细节。复杂度 $\bigO(10 n\log n\log A)$，$A$ 为权值值域。实际上由于尝试扩展到下一个 mex 时很多节点也被同时加入路径，合法的 mex 非常少。