Virtual PTS 2020 Day 4 总结

原题大作战~ ### 拖延症 题意：求满足 $\left\vert i-p_i \right\vert\le 2$ 的排列 $p_1,p_2,\cdots,p_n$ 的数量。 [OEIS A002524](https://oeis.org/A002524) 这题有很多种做法，可以通过状压 dp 推出矩阵乘法优化，当然一定要**明确状态的定义**，不要被自己给糊弄了（哭）。另外遇到复杂的情形不要尝试手推矩阵。 当然还有更玄学的方法，可以暴力算出前 $10$ 项，再用高斯消元或枚举系数（记得枚举的范围要包括负数）的方法强行弄出线性递推式。 ### [旅行路线](https://www.luogu.com.cn/problem/P5304) 梅开 [~~二度~~](https://www.luogu.com.cn/blog/Sweetlemon/virtual-noip-2018-day5) [~~三度~~](https://www.luogu.com.cn/problem/P5304) 四度。 二进制分组和“最短路、次短路”的方法都有讲过了，现在着重介绍“染色”的方法。 这个题目的主要限制条件是“起点和终点是两个**不同**的关键点”，如何判断“不同”呢？我们可以记录每个点的最短路来源。 听起来很不错，但写起来却仍比较困难。这个方法的思路是，枚举图中的每一条边 $u\to v$（边权为 $w$），设满足 $\operatorname{dis}(i\to u)$ 最小的关键点为 $i$，满足 $\operatorname{dis}(v\to j)$ 最小的关键点为 $j$，且 $i\neq j$，则用 $\operatorname{dis}(i\to u)+w+\operatorname{dis}(v\to j)$ 更新答案。 怎么证明这个方法的正确性呢？我们只需证明两点：每次更新的答案都不小于最优解，并且最优解一定会在某条边上被更新到答案中（类似于证明不等式，先证明不等号，再证明等号可以取到）。 第一点很容易证明，$i\to u\to v\to j$ 肯定是一条两个不同关键点间的路径，所以这个一定成立。 第二点如何证明呢？假设最优解为 $a_1 \to a_2 \to \cdots \to a_k$，其中 $a_1\neq a_k$ 且均为关键点。那么对这条路径上的任意一个点 $a_i$，满足 $\operatorname{dis}(p,a_i)$ 最小的**关键点** $p$ 一定是 $a_1$（**或者**最小值点是 $a_k$ 而次小值点是 $a_1$），否则一定可以通过修改 $a_1$ 得到更优的解。同理，$\forall i\in \{1,2,\cdots,k\}$，满足 $\operatorname{dis}(a_i,q)$ 最小的**关键点** $q$ 一定是 $a_k$ **或** $a_1$。 接下来我们只需证明，在这条路径上存在一条边 $u\to v$，使得满足 $\operatorname{dis}(p,a_i)$ 最小的关键点 $p$ **是** $a_1$，而满足 $\operatorname{dis}(a_i,q)$ 最小的关键点 $q$ **是** $a_k$（注意，这里没有“或者”了）。 如果 $a_1,a_k$ 直接连边，那么上面的条件当然是成立的，只需取 $u=a_1,v=a_n$ 即可。 如果 $a_1,a_k$ 不直接连边呢？我们使用反证法，假设不存在边 $u\to v$，使得。我们知道，$a_1\to a_2\to \cdots \to a_k$ 一定是 $a_1$ 到 $a_k$ 的最短路。不会证了，逃（ 总之这个算法是对的（bushi ### [多重集](https://www.luogu.com.cn/problem/P4556) 题意：有一棵 $n$ 点树，有 $m$ 次插入操作，每次在树上两点 $u,v$ 的路径上所有点插入一个数；最后输出所有点上的众数（如果有多个，输出最小的一个）。 洛谷上这题标的是线段树合并模板，这里主要提一下线段树合并的复杂度问题：每递归一次就会删除一个节点，而递归本身是 $\mathrm{O}(1)$ 的，所以整个合并过程的总复杂度不高于原先的总节点数，也就是 $\mathrm{O}(m\log n)$。 还有就是注意，复制代码的时候一定要改完，特别是**递归部分**，不要让 `dfs1` 的函数递归递归着就跑到 `dfs2` 里面去了。 此外，这道题还有用树剖方法或树上启发式合并（树上静态链分治）的解法，这些算法虽然复杂度似乎多一个 $\log$，但是常数很小，所以一般也能够通过。