lsjh NOIP 练习题 #2 做题记录
honey_
·
·
个人记录
`题意`：
给定长度为 $n$ 的序列 $a$，求长度至少为 $2$ 的本质不同的最长上升子序列个数（严格）。
$1 \leq n \leq 10^5,|a_i| \leq 10^9$。
答案对 $10^9+7$ 取模。
`分析`：
首先不考虑去重，设状态 $dp_i$ 表示以 $a_i$ 结尾的最长上升子序列个数，则有转移 $dp_i = 1+\sum\limits_{j = 1}^{i-1}dp_j[a_j < a_i]$。
现在考虑有重复的数，当 $a_i = a_k(i < k)$，显然，在 $1$ 到 $i-1$ 中的小于 $a_i$ 的数的集合 $S$，若存在 $i+1 \leq j < k,a_j \in S$，那 $j$ 对答案一定会有多余的贡献，所以可以存 $pre_i$ 表示上一个出现 $a_i$ 的下标，对于 $dp_i$，直接减去 $dp_{pre_i}$ 即可。
容易发现 $dp$ 方程是一个类似前缀和的东西，本质是单点修改，区间查询，可以离散，树状数组或线段树优化。
时间复杂度 $O(n \log n)$。
-----------------
$H-$ 机会成本
`题意`：
有 $n$ 个三元组 $(x_i,y_i,z_i)$，选定一个 $j$，令 $(x,y,z) = (x_j,y_j,z_j)$ 要求最小化 $max(x_i-x,0)+max(y_i-y,0)+max(z_i-z,0)$。
$2 \leq n \leq 2 \times 10^5,1 \leq x_i,y_i,z_i, \leq 10^9$。
`分析`：
直接枚举 $(x,y,z)$ 是 $O(n^2)$ 的，这显然不能接受，考虑对原式分析，$max(x_i-x,0)$ 可以看做答案取 $x_i-x$ 或 $0$，然后 $y,z$ 同理，这样我们可以把原式拆成八种情况：$0,x_i-x,y_i-y,z_i-z,(x_i+y_i)-(x+y),(x_i+z_i)-(x+z),(y_i+z_i)-(y+z),(x_i+y_i+z_i)-(x+y+z)$。
这样题意本题要求的 $\min\limits_{i = 1}^{i = n}\{max(x_i-x,0)+max(y_i-y,0)+max(z_i-z,0)\}$ 就转化成了 $\min\limits_{i = 1}^{i = n}\{max(0,x_i-x,y_i-y,z_i-z,(x_i+y_i)-(x+y),(x_i+z_i)-(x+z),(y_i+z_i)-(y+z),(x_i+y_i+z_i)-(x+y+z))\}$.
然后对于一个 $x$，显然 $x_i-x$ 的最大值为 $max(x_i)-x$，所以对于这八项，只需要分别预处理出 $x_i,y_i,z_i,x_i+y_i,x_i+z_i,y_i+z_i,x_i+y_i+z_i$ 的最大值就可以了，然后查询是 $O(1)$ 的。
时间复杂度 $O(n)$。
-----------------
$J-$ 区间
`题意`：
给定 $n$ 个区间，第 $i$ 个区间为 $[l_i,r_i]$，你需要选出其中 $m$ 个区间，使得这 $m$ 个区间的交集不为空，并最小化这 $m$ 个区间中长度最大的区间长度与长度最短的区间长度的差。
$1 \leq m \leq n,1 \leq n \leq 5 \times 10^5,1 \leq m \leq 2 \times 10^5,0 \leq l_i \leq r_i \leq 10^9$。
`分析`：
首先 $l_i,r_i$ 都很大，大概率要离散，题目与区间长度有关，那可以先按照区间长度大小排序，然后依次枚举区间，覆盖 $[l_i,r_i]$，然后判断是否有一个点覆盖次数大于等于 $m$，容易发现，覆盖操作就是区间加 $1$，判断操作就相当于全局最大值是否大于等于 $m$，这显然可以用线段树维护。
然后可以双指针，维护当前选的区间（注：数组要开足够大）。
时间复杂度 $O(n \log n)$。
-----------------
$L-MIN\&MAX I
题意：
对于一个 n 阶排列 p，我们建立一张无向简单图 G(p)，有 n 个节点，标号从 1 到 n，每个点向左右两侧最近的比它大的点以及比它小的点连边。
现在在所有的 n 阶排列中随机选择一个排列 p，请求出 G(p) 中三元简单环的期望个数，答案对 998244353 取模。
`分析`：
令三元环为 $(i,j,k)$，容易发现这样的 $(i,j,k)$，必须满足 $p_j < min(p_i,p_k)$ 或 $p_j > max(p_i,p_k)$，然后两种情况是对称的，只用求 $p_j > max(p_i,p_k)$ 个数，然后乘 $2$ 即可。
我们设点 $(i,p_i)$，然后发现，如果 $i,k$ 要有 $j$ 满足条件，那么以 $(i,p_i),(k,p_k)$ 为对角顶点的矩形内部应没有其他点，然后会发现对于每个 $p$，答案总是接近 $2n$ 的，而一个 $j$，如果没有满足条件的 $i,k$，那么他左边 $(x < j)$ 或右边 $(x > j)$ 应该至少有一个方向是没有大于或等于 $p_j$ 的，也就是说 $j$ 是二维偏序极值点，那么对于任意一个排列，他的答案就是 $2n$ 减去这个排列的二维偏序极值点的个数。
而二维偏序极值点呢，就是一个排列的前缀最大值或后缀最大值。
考虑期望线性性，$j$ 为前缀最大值的概率为 $\frac{1}{j}$，为后缀最大值的概率为 $\frac{1}{n-j+1}$，然后再减去同时可能是后缀最大值的可能性为 $\frac{1}{n}$，所以对于 $j$，同时不为前缀最大值且不为后缀最大值的概率是 $1-\frac{1}{j}-\frac{1}{n-j+1}+\frac{1}{n}$。
答案就是 $2 (\sum\limits_{j = 1}^{n}1-\frac{1}{j}-\frac{1}{n-j+1}+\frac{1}{n}) = 2(n+1-2\sum\limits_{j = 1}^{n}\frac{1}{j})$。
$O(n)$ 实现可以获得大部分分数。
本题的瓶颈在于求 $\sum\limits_{j = 1}^{n}\frac{1}{j}$，对于这里，我们可以设一个较大的底数 $S$，打表预处理出 $\sum\limits_{j = 1}^{S}\frac{1}{j},\sum\limits_{j = 1}^{2\times S}\frac{1}{j},..., \sum\limits_{j = 1}^{k \times S}\frac{1}{j}$，然后就能 $O(S)$ 的复杂度求解了。
而如果代码长度过大，可以考虑适当范围内扩大底数，也可以用其他进制。
-----------------