2022联合省选小结

· · 个人记录

过了好久终于补完了。

题目详情

  1. 题解：预处理器

    标签：模拟

    小结：没啥好说的。

  2. 题解：填树

    标签：树形dp，拉格朗日差值，容斥。

    小结：

    • 明白了多个单项式相乘的式子可以用拉格朗日插值。
    • 有时候数据结构也能做到，但是很难吧，起码考场上是这样想的。
    • 对于路径问题，如果是对于每个路径操作，那么时间复杂度无法优化。所以一般还是考虑怎么把路径合在一起算。

  3. 题解：学术社区

    标签：欧拉回路，网络流。

    小结：

    • 还是先尝试能不能转化成图的模型。
    • 覆盖所有边的问题，考虑用欧拉路径或回路，就要进一步考虑度数问题。
    • 两种会冲突的模型，就分开考虑，尝试通过其他方法合并。
    • 最优决策考虑网络流。
    • 部分分还是很有提示性的。

  1. 题解：卡牌

    标签：容斥，状态压缩dp。

    小结：

    • 质因数的性质，可以根号分治，感觉这题部分分暗示 O(2^n) 的算法，但是考场没看出。
    • 容斥原理理解加深了。

  2. 题解：序列变换

    标签：贪心，括号树。

    小结：

    • 括号序列还能搞成括号树，这样更好理解操作意图。
    • 接下来就是分类讨论，基于对比的贪心，发现性质。

  3. 题解：最大独立集问题

    标签：dp

    小结：

    • 这个dp方程真的妙，代价只包含已知量，并给未知量留好位置，只要知道位置量，就能算出代价和。

    • 先写出正确的转移，再进行优化，改一次运行一次，感觉这样能很大程度保证正确性不变，又能避免很多错误。

    • 枚举路径利用宏定义节省代码。

总结