P3547:「POI2013」CEN-Price List – 题解

主要思路

考虑三种最短路的形式：\(A \times dist, \lfloor \frac{dist}{2} \rfloor B + (dist \bmod 2) A, kB \)。前两种直接 BFS 一遍即可，第三种对路径有特殊要求：不能存在边集外一条边可以使得与路径的某两条边形成三元环。

说到三元环，我们就可以仿照那个根号的方法，先做标记，然后再枚举中间边。然而，这里我们没法拆成单向边，所以直接根号的做法是假的。

继续思考一个三元环 \((u, v, w)\)，发现如果我们找到了一个这样的三元环，至少我们可以直接删掉 \((v, w)\)，因为这个边不会再发挥作用了（因为我们在 BFS 的时候肯定提供最优解）。

规律题。只要能发现合法序列的极差不超过 \(1\) 这个性质就可以算了。直接：

\[ ans = 2 – n + \sum_{i = 1}^{n – 1} 2^{\gcd(i, n)} \]

然后这个显然可以用某些 Polya 题的方式用数论函数进行优化，就没了。

总有一种之前纪中 A 组做过的感觉，没想到真的做过，只是那个时候并不知道这个东西叫做 DP 套 DP。

这个题还蛮神仙的，我很喜欢。

如果是做暴力的话，那么这个思路是很有限的。我们考虑换一种思路。既然最后的答案是要求 \(\Theta(k^2)\) 级别对的最短路，我们尝试把这个规模进行缩小，然后只求小规模的全局解（并不是求出所有最短路），然后多次求解之后可以得到全规模的全局解。

一般赛场上遇上计算几何的题一般都不难，而碰上了没学过就直接爆零。为了避免这样的情况，我决定好好学一遍计算几何的一些东西。

结果是学了一遍照样爆零。