本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-03-09 22:26:05

A

给定一串表达式要求计算。

注意到没有未知量，把题目给的表达式复制下来直接输出就可以了。

B

给定 $n$ 个点，求两两之间的距离最大值。

$n$ 很小，暴力枚举两个点就可以了。

C

输出 $10$ 进制下第 $k$ 小的，仅包含 $0,2$ 的数。

注意到 $k \le 10^{18}$，不能使用暴力方法。

观察样例发现在 $k$ 达到上限的时候，答案也才 $60$ 位，所以答案位数最多 $60$ 位。

常用套路，类似递归的方式，逐渐减小问题规模。

假定当前求解的是答案是 $f(k)$。

假定个位为第一位，并且最高非零位是 $x$ 位，那么，至少有 $2^{x-1}$ 个数严格小于答案。

通过这个方法，可以枚举得出答案的最高非零位。

随后，再递归计算 $f(k-2^{x-1})$。

时间复杂度 $O(\log k)$ 级别，如果每次递归都重新枚举最高位，那还会多一个 log。

D

给定一个长度为 $n$ 的数列 $a$，一个正整数 $k$。

要求你对于 $a$ 的每个前缀，求出其第 $k$ 大的值。

维护一个优先队列，每次扩展前缀时候先把新元素加入，然后只要队列有超过 $k$ 个元素，就把最小的删掉。

E

称一个数字是算术数，当且仅当任意相邻前后两位的差值是一样的。

给定 $x \le 10^{17}$，求最小的大于等于 $x$ 的算术数。

注意到满足条件的数的位数一定与 $x$ 相同，因为可以使用 $99999999$ 这样形式的。

注意到 $x$ 的位数很少，可以暴力枚举最高位以及相邻两项的差值。

从小到大枚举最高位，从小到大枚举相邻低位减高位的值，第一个合法的数就是答案。

F

给定字符串 $S$，你可以随意提取 $S$ 的任意子序列（可以不连续），然后重新排列，问能得到的字符串数量。

$|S| \le 5000$。

注意到，其实有效的信息仅仅是 $S$ 中每种字符出现了多少次。

给 a 到 z 的字符编号 $1$ 到 $26$，令 $cnt_i$ 代表字符 $i$ 的出现次数。

注意到，难以处理的地方在于相同字符的排列组合，如果一个一个字符的加入，则需要在状态里面记录每种字符之前已经有多少个，这是不可能的。

所以，现在直接考虑每种字符有多少个加入最终字符串，整体考虑。

$dp_{i,j}$ 代表前 $i$ 种字符总共选了 $j$ 个的方案数。

每种字符通过枚举自己选择了多少个进行转移。

$dp_{i,j} = \sum\limits_{k=0}^jdp_{i-1,j-k}\binom{k+j-1}{j}$。

时间复杂度 $O(n^2)$，稍微分析一下就知道不需要乘 $26$。

G

给定一个长度为 $n$ 的数列，注意到有 $2^{n-1}$ 种方式将其划分为不同的连续子序列。

对每种划分方式下，子序列的极差的乘积进行求和。

$n \le 3\cdot 10^5$。

令 $f_i$ 代表前 $i$ 个元素构成的序列的答案。

$f_0=1$.
$f_i = \sum\limits_{j=1}^i f_{j-1}(\max\limits_{k=j}^ia_k-\min\limits_{k=j}^ia_k)$。

考虑 max,min 分开计算，这两个事实上差不多，这里只讨论 min 的情况。

考虑每个 $a_j$ 对于答案的贡献。

事实上，如果存在 $x \lt y$，满足 $a_x \ge a_y$，那么 $a_x$ 就没有存在的必要。

使用单调队列优化，使得有效的 $a$ 值都是从前到后降序的，同时每个 $a$ 值的贡献区间就是自己前面这一段一直到上一个 $a$ 值。

想到这里其实已经做完了，单调队列维护的时候顺便维护一下答案就做出来了。

时间复杂度 $O(n)$。

Ex

给定二维平面上的 $n$ 个点，一个整数 $k$，要求给出所有的距离小于等于 $k$ 的点对，保证符合要求的点对数量不超过 $4 \cdot 10^5$。

参考的题解做法，就当一个 trick。

做法 1 - 洛谷第二篇题解的做法

解法很简单，将这个平面划分为一个个大小为 $k \times k$ 的正方形，对于每个点，枚举以其正方形为中心的九宫格内的所有点。

这个做法显然能求出所有的点对，但是现在为什么它的时间复杂度是对的呢？

考虑将一个 $k\times k$ 的正方形划分为 $4$ 个小正方形，那么每个小正方形内部的点必然互相到达。

假设这个 $k\times k$ 的正方形内有 $m$ 个点，那么这个正方形自己内部的答案也就是 $O(m^2)$ 级别的。

此时，返回去再考虑两个相邻的 $k\times k$ 正方形的点对枚举，假设一个大小为 $p$ ，另一个为 $q$，那么计算量将是 $O(pq) \le O(\max^2(p,q))$。

考虑均摊分析，将相邻 $k\times k$ 正方形点对枚举的计算量算到点多的正方形上，假设这个正方形大小为 $s$，那么这个正方形的计算量贡献将最多是 $10s^2$，而这个正方形的内部合法点对数量就是 $O(s^2)$ 的，而总体的合法点对数量题目给了限制，所以复杂度正确。

这个做法本质上我认为是先通过一下操作排除掉一些不必要的节点，然后通过一定分析证明排除掉不必要的节点之后，复杂度在一定范围以内。

做法 2 - 第一篇题解的做法

随机将所有点旋转一个角度。

然后，横坐标升序，赌距离在 $k$ 以内的点在列表里面不会差的很远，对于每个点，枚举接下来大约 $2 \cdot 10^4$ 个节点。

本质上将所有点的横纵坐标重新随机分配了。

这样的话，由于题目对于答案的限制，每个点对答案的贡献相对平均，所以只需要枚举少量的点。