NOI2020 题解报告
美食家
题目大意
给定一张 \(n\) 点 \(m\) 边的有向图，边有不超过 \(w\) 的长度。现要求从点 \(1\) 出发经过长度恰为 \(T\) 的路径回到点 \(1\) ，每到达一个点就会获得等于该点点权的愉悦值。特别地，有 \(k\) 个美食节，形如“于时刻 \(t\) 到达点 \(x\) 会额外获得 \(y\) 的愉悦值”。最大化获得的愉悦值总和。
做法 1
考虑 \(k = 0\) 的情况，也就是忽略美食节。
不难得到这样一个 DP ：设 \(f_{i,j}\) 表示在时刻 \(i\) 到达点 \(j\) 的最大愉悦值，转移枚举 \(j\) 的出边即可，复杂度 \(O(T(n+m))\) 。
做法 2
做法 1 的 DP 中转移与 \(i\) 无关，可以想到把 \(f_i\) 看做一个向量，用 max+ 矩阵描述转移，但是由于边有不等的长度，需要把连续 \(w\) 个时刻的状态合并为一个向量，这样一来就可以用 max+ 矩阵描述转移，使用矩阵快速幂，复杂度 \(O(m + (wn)^3 \log T)\) 。
做法 3 （正解）
现在考虑美食节，称有美食节的时刻为关键时刻，两个相邻的关键时刻之间是不受美食节影响的，可以套用矩阵快速幂的做法。那么就以关键时刻把时间轴分为 \(k+1\) 段，每段用矩阵快速幂，在关键时刻把美食节的影响加到状态上即可。这里矩阵快速幂不能每次暴力矩阵乘矩阵，需要预处理矩阵乘积的幂次，然后用向量乘矩阵的方式处理每一段。复杂度 \(O(m + (wn)^3 \log T + k (wn)^2 \log T)\) 。
命运
题目大意
给定一棵 \(n\) 个点的有根树和 \(m\) 个点对，第 \(i\) 个点对 \((x, y)\) 满足 \(x\) 是 \(y\) 的祖先。求有多少把边黑白染色的方案使得任意给定的点对都满足 \(x\) 到 \(y\) 的路径上存在染黑的边。
做法 1
容易想到树形 DP ，设 \(f_{u,i}\) 表示考虑 \(u\) 的子树，\(u\) 向根一直走白边能走到深度 \(i\) 的前提下的合法染色方案数。然后这个状态如果有一个点对可以从 \(u\) 向上走白边完全经过，这个状态钦定为 0 。于是可以预处理出每个点 \(u\) 的最小的有值的深度 \(a_u\) ，设点 \(u\) 的深度为 \(d_u\) ，转移即
\[f_{u,i} = [a_u \le i \le d_u] \prod_{u \rightarrow v} (f_{v,i} + f_{v,d_v})\]
复杂度 \(O(nh)\) ，其中 \(h\) 是树高。
做法 2 （正解）
上述的转移看上去形式很优秀。
把 \(f_u\) 看做一个一维向量，用线段树维护这个向量。观察转移可以发现需要对这个向量进行三个操作：
- 全局加一个数
- 两个向量点乘合并
- 保留一个区间的值
- 求点值
操作 1 和操作 3 就是经典的区间加和区间乘，操作 2 是不那么平凡的线段树合并，这个合并是没法维护区间信息的，不过为什么要维护区间信息呢？由于查询操作只有点值查询，那么只有叶子维护信息就行了，非叶子节点只需要维护其他操作的懒标记，那么合并两个节点的时候先把标记下传然后就可以直接合并了。
时代的眼泪
题目大意
给定一个 \(1\) 到 \(n\) 的排列，\(q\) 次询问，每次给定一个下标区间和一个值域区间求在给定区间内的元素的逆序对数。
做法 1
如果值域区间是全集，那么问题就是区间逆序对，这是个比较经典的问题，有两种复杂度同样优秀的做法，一种是在线的序列分块，一种是莫队二次离线。
回顾一下序列分块的做法，设块大小为 \(B\) 。
如果询问区间在一个块内，考虑差分，用块的一个前缀减另一个前缀，然后减去两部分之间的贡献，后者可以归并计算。
否则把询问区间分成三个部分 L, M, R 分别表示左端零散块，中间完整块，右端零散块。L, M, R 内部的贡献都可以预处理，对于它们之间的贡献分类讨论。
- LM, MR: 以 LM 为例，预处理 \(c_{i,j}\) 表示前 \(i\) 个块中值不超过 \(j\) 的数量，这样就可以 \(O(1)\) 求出任意块区间的任意值域区间的数量，枚举 L 的每个元素算贡献即可。
- LR: 预处理每个块的排序序列，就可以 \(O(B)\) 扫描得到每个块的子序列的排序序列，得到两边的排序序列后归并即可。
复杂度 \(O(\frac{n^2}{B} + n\log{n} + qB) = O(n\log{n} + q + n\sqrt{q})\) 。
做法 2
莫队的做法似乎难以向值域区间的限制推广，因此考虑序列分块。
先考虑询问的值域区间都是形如 \([1, r]\) 的情况，不妨假定 \(r\) 单调不降。
每次 \(r\) 增加的时候，相当于新加入一个数，是可以简单地 \(O(B)\) 维护对应块的每个前后缀的逆序对数的。
那么如果询问区间在一个块内，仍然可以用同样的方法处理。
否则同样把询问区间分为三部分 L, M, R 讨论，L, R 内部的贡献仍然是被预处理的，那么可以发现不同于做法 1 的部分仅有 MM 。
维护一个矩阵 \(f_{l,r}\) 表示第 \(l\) 个块到第 \(r\) 个块之间的逆序对数，每次加入一个数的时候枚举 \(r\) 相当于要做若干次区间加，每次询问只需要单点查。容易想到再次分块维护这个矩阵，但是注意到矩阵的每一行的长度只有 \(O(\frac{n}{B})\) ，事实上修改的时候打标记然后查询的时候暴力扫描即可。
复杂度 \(O(\frac{n^2}{B} + nB + n\log{n} + qB + \frac{nq}{B}) = O((n + q) \sqrt{n} + n\log{n})\) 。
做法 3 （正解）
现在考虑完整的问题。以下直接默认块大小为 \(B = \sqrt{n}\) 。
如果询问区间在一个块内，每个块内把值离散化，处理 \(b_{i,j}\) 表示第 \(i\) 个位置到其所在的块的左端点中离散化后的值不超过 \(j\) 的数量，\(b\) 的大小是 \(O(n^{1.5})\) 的。然后枚举的每个元素通过 \(b\) 查询贡献即可。
否则还是分三个部分 L, M, R 分类讨论。
- LL, RR: 同询问区间在一个块内的情况。
- LR: 同做法 1 （其实仍用上述做法也是可以的）。
- MM: 设值域区间为 \([x, y]\) 。先用做法 2 算出 \([1, y]\) 和 \([1, x - 1]\) 的答案，然后问题转换为求区间内有多少数对满足左边的值在 \([x, y]\) 内且右边的值在 \([1, x - 1]\) 内。这个问题怎么处理呢？我也暂时不会（咕咕咕）。
- LM, MR: 同做法 1 。
复杂度同做法 2 。
制作菜品
题目大意
有 \(n\) 种材料，第 \(i\) 种材料有 \(a_i\) 个。现要制作 \(m\) 种菜，每种菜恰好使用 \(k\) 个材料并且使用至多两种材料。求是否存在方案，如果存在则给出任意一个方案。
保证 \(\sum a_i = m \times k\) 。
做法 1
考虑 \(m \ge n - 1\) 的情况，我们证明，每次把数量最少的材料和数量最多的材料放一起做菜并尽可能多地使用最少的那个材料，这样一定能得到一个合法的方案。
应用数学归纳法，\(n = 1\) 时由于 \(a_1 = m \times k\) ，此时必然有解。接下来假设 \(1\) 到 \(n-1\) 都是成立的。不妨假定 \(a\) 是升序的。
如果 \(a_1 \ge k\) ，把第一种材料拿 \(k\) 个出来单独做菜，直到 \(a_1 < k\) 。此时 \(a_2\) 到 \(a_n\) 都是不小于 \(k\) 的，由 \(\sum a_i = m \times k\) 可以知道此时仍然有 \(m \ge n - 1\) 。
如果 \(a_1 < k\) ，把第一种材料全部拿出来，和第 \(n\) 个材料里拿 \(k - a_1\) 个一起做一道菜，需要证明 \(a_n \ge k - a_1\) ，否则做不成菜。反证法，如果 \(a_n < k - a_1\) ，那么任意 \(i\) 都有 \(a_i < k - a_1\) ，求和后有
\[mk = \sum a_i < (n-1)(k - a_1) + a_1 = k + (n-2)(k-a_1) \le (n-1)k\]
所以 \(m < n - 1\) ，与前提产生矛盾。
做法 2 （正解）
注意到 \(m < n - 1\) 的时候必有 \(m = n - 2\) ，因此我们只讨论 \(m = n - 2\) 的情况。
容易想到把所有材料划分成两个集合，然后两个集合当做一个 \(m = n - 1\) 的子问题。如果存在合法的划分，那么原问题有解。我们证明，如果原问题有解，也一定存在合法的划分。
把一道菜看做连接两个材料的边，那么对于 \(m = n - 2\) 时的一组解，得到的图一定有至少两个联通块，并且可以发现有至少一个联通块是一颗树（反证，如果都不是树，把点数和边数累加可以得到 \(m \ge n\) ，产生矛盾）。那么把任意一颗树看做集合 \(A\) ，其他的所有联通块看做集合 \(B\) ，这就是一个合法的划分。
这里一个划分是合法的当且仅当两个集合都满足 \(\sum a_i = (n' - 1) \times k\) 。
设 \(b_i = k - a_i\) ，上述条件等价于 \(\sum b_i = k\) ，问题转换为在 \(b\) 中找到一个和恰好为 \(k\) 的子集，经典的 01 背包问题，用 bitset 优化即可。
复杂度 \(O(T \frac{n m k}{w})\) 。
超现实树
做法 1 （正解）
对于两棵树 \(A, B\) ，称 \(A < B\) 当且仅当 \(A\) 可以生成 \(B\) 。
不难发现树林不是完备的当且仅当存在一颗无限大的树不能被生成，设该树为 \(T\) ，不妨假设在所有足条件的树中 \(T\) 是极小的。注意到如果 \(T\) 的某个点满足左右儿子的大小都超过 \(1\) ，那么一定存在另一颗比 \(T\) 小的树 \(T'\) 同样满足条件，这违背了 \(T\) 的极小性。那么称一颗不存在任何点的左右儿子大小都超过 \(1\) 的树为备选树，可以发现，树林非完备当且仅当存在一颗无限大的备选树不能被生成。
那么我们只需关注树林是否可以生成所有无限大的备选树，注意到非备选树始终无法生成备选树，因此我们即使在树林中我们也只需要考虑备选树。
我们递归地判定树林 \(e\) 是否可以生成所有无限大的备选树，如果 \(e\) 中存在大小为 \(1\) 的树，\(e\) 显然是完备的，如果 \(e\) 中没有树，\(e\) 显然不是完备的。否则，可以发现 \(e\) 中的备选树可以分为四类：
- 没有左儿子
- 没有右儿子
- 左儿子大小为 1
- 右儿子大小为 1
设这四种树去掉根保留另一个较大的儿子后分别构成树林 \(a, b, c, d\) ，那么不难发现此时 \(e\) 是完备的当且仅当 \(a, b, c, d\) 都是完备的，递归判定即可。
翻修道路
做法 1
考虑所有道路长度都为 \(1\) 的情况。
弦图遇事不决完美消除序列。不妨假定 \(1\) 到 \(n\) 就是一个完美消除序列且 \(t = n\) 。设翻修的路径是有向的，从 \(s\) 指向 \(t\) 。
首先翻修的路径中的任意一条边 \((x, y)\) 都满足 \(x < y\) 。反证法，对于翻修路径上某一个点 \(x\) ，其前驱后继分别为 \(y, z\) 。如果 \(y > x \land z > x\) ，那么 \(y, z\) 之间一定有边，把翻修路径中的 \(y \rightarrow x \rightarrow z\) 换成 \(y \rightarrow z\) 一定不劣，并且一定仍然合法。
那么直接从小到大连有向边然后 bfs 求个最短路即可，复杂度 \(O(n + m)\) 。