题解：[[2024.9.26 模拟赛]] ## 智乃的差分 #找规律 #优先队列 对于数组 $a$ 而言，其差分 $d$ 数组 $d_i=\begin{cases}a_1&\text{if}~i=1\\a_i-a_{i-1}&\text{else}\end{cases}$。现让你重新排列 $a$ 数组，使 $a$ 的差分数组 $d$ 内没有整数 $x$。 ## 牛牛的旅行 #并查集 #树形dp 一景区有 $n$ 个景点，有 $n-1$ 条边连接两个景点，第 $i$ 个景点的优美程度为 $a_i$。对于两个不相邻的景区 $(u,v)$，定义 $f(u,v)$ 为路径上最大优美程度减去路径长度，求 $\sum\limits_{1\le i,j\le n,i\ne j}f(i,j)$。 ## 第 K 排列 #序列dp > [!tip] 提示 > > 本题面保留了原题面的部分汁水，以祝您更「流畅」地阅读。 有字符串 $S$ 仅包含 $\texttt{N,O,I,P}$ 四种字符，现有若干字符被隐藏（用 $\texttt{?}$ 代替）。已知该字符串在所有可能的字符串当中权值不小于 $x$，字典序降序排列的第 $k$ 个解。有表格： | | **N** | **O** | **I** | **P** | | :---: | :---: | :---: | :---: | :---: | | **N** | a | b | c | d | | **O** | e | f | g | h | | **I** | i | j | k | l | | **P** | m | n | o | p | 例如，字符串出现 $\texttt{NN}$ 相连，就要加上 $\texttt{a}$；如果出现 $\texttt{IO}$ 相连，就要加上 $\texttt{g}$。整个字符串的权值之和就是出现的所有情况的权值之和。例如 $\texttt{NOIP}$ 的权值为 $\texttt{a+b+g}$。 ## 牛牛的 border #后缀数组 对于字符串 $s$，若长度为 $i$ 的前缀完全等于长度为 $i$ 的后缀，那么称 $s$ 有长度为 $i$ 的 border。令 $f(s)=\sum i$，其中 $i$ 为 $s$ 的 border 的长度，且 $i\ne |s|$。现给你字符串 $S$，求 $\sum\limits_{s\in S}f(s)$。