一种对操作赋势能来平衡权值的 trick

· · 个人记录

例题：

  1. CF1924F，都要求做到最优时间复杂度，并证明你的做法是最优的。

Hint 0：答案是 \log 量级的。

Hint 1：思考一个邪恶的交互库会做什么。

Hint 2：交互库无法得知选手策略——也就是说，它必须抓住某种变量，并尽可能最大/最小化它。同时选手的目标也就变成了最小/最大化这个变量。

Sol：https://www.luogu.com.cn/article/u0ykhr9d

你应该再完整阅读题解后再继续阅读。

  1. UR28C，CF1924F 是本题的特殊情况。你也许不希望实现这个题。

Hint 0：请先完成 CF1924F。

Hint 1：字符串匹配问题的利器是 AC 自动机

Hint 2：解方程可以直接迭代

Sol：参考官方题解。

  1. P12020，zxx 给出了极为精妙的做法，并做到了很好的复杂度！不过，请你在 n,q 同阶时给出最优的时间复杂度。

Hint -1：只有 3^n 种不同的对。

Hint 0：你要预处理一些信息，同时，查询时借助信息容斥。

Hint 1：直接列出所有可能的预处理信息所带来的查询容斥结果。（例如，例如，一种可行的映射是将 A+B+C 映射到 0，A+B映射到 1，B+C 映射到 2，B 映射到 3，询问时，对其进行容斥，例如，假如第一位是 A+C，第二位是 B，我们则使用 {0}-{3}，{3}计算答案）

Sol：显然，我们只需在本地把容斥系数比凑出来即可，所以你可以直接在本地跑一个 O(\omega^7) 的东西预处理一下。最终结果和 zxx 的差别极小。说明 zxx 的做法十分精妙！

你应该在完全掌握本题后再继续阅读

4.