2021“MINIEYE杯”中国大学生算法设计超级联赛（3）

AC Codes

1003 Forgiving Matching

FFT做带通配符的字符串匹配。看这里。

1004 Game on Plane

显然Alice应该尽量让选出的直线互不平行，而Bob要选出平行数量最多的直线。所以把直线变成最简化的向量排序就行了。

1007 Photoshop Layers

小模拟。

1009 Rise in Price

设 $f_{i,j,k}$ 表示从 $(1, 1)$ 走到 $(i, j)$，一路上收集了 $k$ 个钻石时，钻石的单价最高能涨到多少，则 $ans = \max(k × f_{n,n,k})$。
考虑每个 $(i, j)$，保留其中前m个 $k × f_{n,n,k}$ 最大的状态进行转移。由于题目数据随机，所以需要保留的状态不多。

1010 Road Discount

将原始边作为白边，折扣边作为黑边，由于同一条边不可能选择两次，那么问题等价于求包含恰好 $k$ 条黑边的最小生成树。这是一个经典问题，令 $f(k)$ 表示包含恰好 $k$ 条黑边的最小生成树的边权和，则 $f(k)$ 是一个凸函数，求出 $(k)$ 的方法为：
• 选择参数 $c$，将每条黑边的边权都加上 $c$。
• 求出修改边权后的图的最小生成树，令 $sum(c)$ 为对应的边权和，$l(c)$ 为最小生成树中使用黑边数量的最小值，$r(c)$ 为最小生成树中使用黑边数量的最大值。
• 二分找到合适的参数 $c$，满足 $l(c) \leq k \leq r(c)$，则 $f(k) = sum(c) − k \times c$。
由于边权在 $[1, 1000]$ 之间，因此可以预处理出 $c = 0\ldots 1000$ 的所有信息，一共需要求 $c$ 次最小生成树。注意到如果对黑边或者白边单独求最小生成树，则非树边不可能用到，因此可以将边数缩减至 $O(n)$。
总时间复杂度 $O(m log n + nc log n)$。

1011 Segment Tree with Pruning

记忆化爆搜。