2024.9.26 题目

题解：2024.9.26 模拟赛

智乃的差分

找规律 优先队列

对于数组 $a$ 而言，其差分 $d$ 数组 $d_i=\{\begin{array}{ll}{a}_1& \text{if}i=1\\ a_i-a_{i-1}& \text{else}\end{array}$。现让你重新排列 $a$ 数组，使 $a$ 的差分数组 $d$ 内没有整数 $x$。

牛牛的旅行

并查集 树形dp

一景区有 $n$ 个景点，有 $n-1$ 条边连接两个景点，第 $i$ 个景点的优美程度为 $a_i$。对于两个不相邻的景区 $(u,v)$，定义 $f(u,v)$ 为路径上最大优美程度减去路径长度，求 $\sum _{1\le i,j\le n,i\ne j}f(i,j)$。

第 K 排列

序列dp

提示

本题面保留了原题面的部分汁水，以祝您更「流畅」地阅读。

有字符串 $S$ 仅包含 $\text{N,O,I,P}$ 四种字符，现有若干字符被隐藏（用 $\text{?}$ 代替）。已知该字符串在所有可能的字符串当中权值不小于 $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

例如，字符串出现 $\text{NN}$ 相连，就要加上 $\text{a}$；如果出现 $\text{IO}$ 相连，就要加上 $\text{g}$。整个字符串的权值之和就是出现的所有情况的权值之和。例如 $\text{NOIP}$ 的权值为 $\text{a+b+g}$。

牛牛的 border

后缀数组

对于字符串 $s$，若长度为 $i$ 的前缀完全等于长度为 $i$ 的后缀，那么称 $s$ 有长度为 $i$ 的 border。令 $f(s)=\sum i$，其中 $i$ 为 $s$ 的 border 的长度，且 $i\ne |s|$。现给你字符串 $S$，求 $\sum _{s\in S}f(s)$。