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： $O(n^3)$ dp。

$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$。

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

$30pts$：

$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)$。