NOIP 8/11 题解

· · 个人记录

T1 魔法森林

原题：P9504

题意概述：有一个 n 个点 m 条边的无向简单连通图，有两个属性 A 和 B，每经过一条边 A 就少 1，每条边有边权 w，若你在经过某条边时，属性 A 的值为 k，则你的属性 B 值会掉 \dfrac{w}{k}，若你需要从 s 到 t，求最少 B 属性的个数，n \le 2 \times 10^4，m \le 4 \times 10^4，w \le 100。

25pts：

Subtask 3，w \le 1，答案最多为 1，如果到终点的边有 w=0 的，就为 0，否则为 1。

50pts：

爆搜即可。

75pts：

倒着搜。

100pts：

倒着搜，不超过 w 条边之后代价为 0，注意到 w 很小（\le 100），考虑 DP，f_{u,i} 表示倒着走到 u，已经走了 i 条边的最小生命值。所以我们发现这就是分层图最短路，跑一次 Dijkstra，时间复杂度 O(w(n+m) \log mw)。

注意到分层路连边每次都是 i 层到 i+1 层，拓扑序已经做好，所以发现不需要 Dijkstra，是一个 DP，DP转移方程式是：f_{v,i+1}=\min(w_{u,v}) (f_{u,i}+w_{u,v})，时间复杂度 O(w(n+m))。

T2 异或

原题：P7335

题意概括：n 个数，选出 k 个不交区间 [L_i,R_i]，求这 k 个区间异或和之和最大值 ，k \le n \le 3000。

5pts 爆搜，O(n^{2k})。

25pts：

$f_{i,j}$ 表示前 $i$ 个数分成 $j$ 个区间的答案。 加区间：以 $i$ 结尾，以 $l$ 开头，$l$ 从 $1$ 到 $i$，$f_{i,j}=f_{l-1,j-1}+w_{l,i}$。 不加区间：$f_{i,j}=f_{i-1,j}$。 总时间复杂度 $O(n^2 \times k)$。 100pts： 区间无用的定义：如果一个区间比另一个区间长，异或和又比另一个区间小。 舍弃后有多少个区间？$[i,i]$ 一定要。$[i-1,i]$ 要的当且仅当 $a_i xor a_{i-1}>a_i$，概率为 $\dfrac{1}{2}$。又 $[i-2,i]$ 要的当且仅当 $a_i xor a_{i-1} xor a_{i-2}>$ $a_i xor ai-1$ 和 $a_i$，概率 $\dfrac{1}{3}$，所以一个区间有用的概率为长度分之1，所以有的个数的期望时 $\sum{\dfrac{1}{j}（1 \le j \le n）}= \ln n+O(1)$。 $O(n^2)$ 预处理有用区间后在25pts的加区间的时候只考虑有用区间，复杂度从 $O(n)$ 变成 $O(ln n)$，所以，复杂度变成了 $O(n \times k \times ln n)$。 T3 小 C 的树 II： 题意： $n$ 个节点的树，你可以进行一种操作：把 $i$ 号节点的子树所有都增加 $v$，但需要代价 $c_i$，求最小代价使得其点权都不一样且不等于 $0$，$n \le 2 \times 10^5$，点权修改后不能超过 $2 \times 10^5$。 $10pts

菊花图，答案为 \sum c_i - \max{c_i}，构造方案即可。

$n \le 18$ 直接爆搜，有几个点，就构造 $2$ 的几次方。 $100pts$： 正解思路： 非常神奇。以根结点为根给每个节点做一个 dfs 序，得到每个叶子节点都代表一个区间 $[L,R)$，每次给 $L$ 到 $R$ 连边，记 $s$ 为叶子数量，则构成一张 $s+1$ 个点 的 $n$ 条边的图，每条边的边权为 $c_i$，则答案为这张图的最小生成树。 为什么选最小生成树？我们需要选 $s$ 条边，假如我们选的一些边构成环，对于某条边而言，环上的一条边都可以被环上其他边的加减表示，相当于被其他边取代了，这条边就是没有用的，就需要直接删去，所以 $s$ 条边是一颗生成树。 为什么一定要选 $s$ 个点？我们现在假设一个集合 $S$，$0∈S$，所有叶子节点 $∈ S$，每次的操作就是将一个小集合剥离大集合，所以我们至少需要选择 $s$ 条边，所以构成一颗生成树。 这样我们就求出了选择的最小生成树。 我们设配对点的编号等于叶子的权值，得出结论，你选择的 $s$ 个叶子，选择的跳到最近的一个点必须是不相同的。DFS 一遍，每次加上这个节点的权值，并且把上面的节点的权值减去。 $dfs(u,add)$ 表示当前进行到 $u$ 节点，上面已经选了 $add$ 的权值，时间复杂度 $O(s \log s)$，是求最小生成树的时间复杂度。 T4 最大子段和： 原题：CF280D 题意概述： $n$ 个数，$q$ 次操作： $1.$ 把 $a_x$ 改为 $v$。 $2.$ 求出 $[L,R]$ 选出 $k$ 个子段的最大和。保证 $n,q \le 10^5$，$1 \le k \le 20$。 $12pts$： 纯暴力。 $28pts$： $f_{i,j,0}$ 表示第 $j$ 个区间还没锁死。 $f_{i,j,1}$ 表示第 $j$ 个区间已经锁死了，想在第 $i+1$ 个点再开一个新区间。 状态转移是 $O(1)$ 的，时间复杂度 $O(qnk)$。 $44pts$： 线段树求区间最大子段和。 时间复杂度 $O(n \log n)$。 $56pts$： $v,a_i<0$，很简单（送分），答案是 $0$。 $100pts$： 注意到 $k$ 很小，考虑 DP。 以拼完/没拼完设计状态。 只有两边可能没拼完。 设计状态 $f_{i,0/1,0/1}$，表示选择 $i$ 个区间，左边选没选完，右边选没选完，状态转移也很简单。 每次 pushup 的复杂度 $O(k^2)$，时间复杂度是 $O((n+q \log n) k^2)$，时限有 $4$ 秒，卡常后可以过。 注意到这个东西合并是有凸性的，这样可以将时间复杂度降到 $O(k)$，时间复杂度 $O((n+q \log n)k)$。