Sweetlemon 的博客

Sweetlemon 的博客

Virtual PTS 2020 Day 4 总结

posted on 2020-06-18 15:30:30 | under 总结 |

原题大作战~

拖延症

题意:求满足 $\left\vert i-p_i \right\vert\le 2$ 的排列 $p_1,p_2,\cdots,p_n$ 的数量。

OEIS A002524

这题有很多种做法,可以通过状压 dp 推出矩阵乘法优化,当然一定要明确状态的定义,不要被自己给糊弄了(哭)。另外遇到复杂的情形不要尝试手推矩阵。

当然还有更玄学的方法,可以暴力算出前 $10$ 项,再用高斯消元或枚举系数(记得枚举的范围要包括负数)的方法强行弄出线性递推式。

旅行路线

梅开 二度 三度 四度。

二进制分组和“最短路、次短路”的方法都有讲过了,现在着重介绍“染色”的方法。

这个题目的主要限制条件是“起点和终点是两个不同的关键点”,如何判断“不同”呢?我们可以记录每个点的最短路来源。

听起来很不错,但写起来却仍比较困难。这个方法的思路是,枚举图中的每一条边 $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

多重集

题意:有一棵 $n$ 点树,有 $m$ 次插入操作,每次在树上两点 $u,v$ 的路径上所有点插入一个数;最后输出所有点上的众数(如果有多个,输出最小的一个)。

洛谷上这题标的是线段树合并模板,这里主要提一下线段树合并的复杂度问题:每递归一次就会删除一个节点,而递归本身是 $\mathrm{O}(1)$ 的,所以整个合并过程的总复杂度不高于原先的总节点数,也就是 $\mathrm{O}(m\log n)$。

还有就是注意,复制代码的时候一定要改完,特别是递归部分,不要让 dfs1 的函数递归递归着就跑到 dfs2 里面去了。

此外,这道题还有用树剖方法或树上启发式合并(树上静态链分治)的解法,这些算法虽然复杂度似乎多一个 $\log$,但是常数很小,所以一般也能够通过。