20220810NOI模拟赛--考后总结

时间安排

7:30–7:35 读题。T3 非常鬼畜。

7:35–9:10 T1,对于同一棵树的情况可以 DP ，但当有两个棵树时 DP 就显得不那么优秀了。这种子树限制个数的和某道 PR 的 守卫 很像，想到可以建图解决限制问题。依照想法建图，调试。

9:10–9:30 T2, 显然可以数位 DP ，问题在于如何快速求满足 abcd 的方案数，这玩意可以 DP ，但是复杂度很高没什么优化的空间，想到可能有更妙的方法。部分分可能可以用 DP 做，然而时间和空间都不允许，写个暴力滚粗。

9:30–11:00 T3,莫名想到分开时间段，这样每个鸽子时一个函数，三分应该可以求其峰值，用拉格朗日插值可以求出有关点值，想法很模糊。看了几个部分分不知道有什么用， 对于 $m=2$ 可以按上述方法做，分段三分，细节较多调试半天。猜了几个拓展的结论不过都是假的。

11:00–12:30 看T2，T3。

回顾&反思

T1: 场上算是过掉了。一个更优秀的建图是，对于每个子树选择点个数的限制，分别对应一个关键点和他控制的集合，由于树上子树与子树之间要么包含要么不交，那么求出有祖先关系的集合差，集合与集合之间不交，可以分别想对应普通点连边。

T2:看出是数位 DP 了，瓶颈在于不能快速求限制了 01、10、00、11 子串个数的串数量。考虑将每一段的 0 或 1 缩成一个 0 或 1 ，那么 01、10 的个数只与这些缩后的 0、1 有关，往里加 1、0 等价于增加 11、00 ，那么就变成分配问题可以直接组合数求解。还是要多分析性质。
总结一下见过的 01 串性质的题的常见套路 ：1. 将连续的 0 或 1 缩成一个 0 或 1 ，然后考虑加其他 0 ，1 ；2. 将 0、1 的一些特征串看成一个整体，考虑不同整体的关系 ； 3. 考虑 0，1 的移动。

T3: $n<m$ 的部分分没拿到有些可惜，将 m 个点放在 n 条边 n 个点的简单回路上，$n<m$ ，那么根据鸽巢原理，必有两点在一条边上。正解是拆分时间段，解函数方程。