气球赛题解

· · 个人记录

D：

从 1 到 n，边长 e_i，收益 p_i，求最短路最大收益。

一遍 dijk 是错的，理由是标记 vis 数组会导致更高收益的同样长度路径不被更新。不消零边环是错的，理由是拓扑会导致一条路径不被计算。上述两种均可以被这个卡：

1
5 6
1 2 1 1
2 5 1 1
1 3 1 0
3 2 0 2
3 4 0 0
4 3 0 0

正解应该是先跑一遍最短路，然后把仅保留所有 dis[v] == dis[u]+w 的边跑缩点，这时候缩的点是零环，最后形成了 DAG，拓扑 DP 即可。

J:

DP，设 $f[i][j]$ 表示前 $i$ 个娃分成 $j$ 组方案数，转移可以是新开一个组，或者加到前面某一个组。 先设 $f[i][j] = f[i-1][j-1]+f[i-1][j]\cdot \min(j,ftp[i])$，$ftp[i]$ 表示 $j\in [1,i-1], a[i]-a[j] \geq r$ 的 $j$ 的个数。 但是这样会计重，因为 $a[i]-a[j] \geq r$ 并不一定代表 $i$ 可以丢进 $j$ 的组里。 考虑反面，$i$ 不能丢进的组，于是 $f[i][j] = f[i-1][j-1]+f[i-1][j]\cdot \max(0,i-ft[i])$，$ft[i]$ 表示 $j\in [1,i-1], a[i]-a[j] < r$ 的 $j$ 的个数。其中 $ft[i]$ 可以 $O(n\log n)$ 预处理。 I: 重排 A，问是否能构造不存在下标递增的数值上项数 $3$ 的等差数列，并构造。 考虑某数出现 $3$ 次肯定不能构造。 考虑分奇偶讨论，发现如果三个数是奇偶偶或者偶奇奇那么一定不是等差，于是考虑把奇数丢左边，偶数丢右边。 但这样还是会有奇奇奇或偶偶偶的情况，考虑二进制下右起第二位，把 0 的丢右边，1 的丢左边，如此继续下去，最终一定构造成功。 G: 一次操作等价于将一个数丢到它后面某个位置。 考虑贪心，肯定是把前面较小的数丢到后面，于是先从前往后挑出 $k$ 个 $a_i < a_{i+1}$ 的 $a_i$，然后归并把剩下的和挑出的弄在一起。