小战NOIP2024

· · 个人记录

A

贪心的正确性是显然的，至此思维难度结束。

代码的细节主要在于两个字符串自由区间的交错问题，大概写+调了30min。

B

注意到 v\ge 2，因此对于一个已知的 \{(a_i,b_i)\}，最优策略一定是尽可能躲开 (a,b) 的限制。

所以一个 \{(a_i,b_i)\} 不合法，当且仅当存在从 (c_i,d_i) 到 (c_{i+1},d_{i+1}) 的链接，且链接过去的值不满足条件。

随便数一数就行。写起来比 A 快。

C

想的最久的一题。

构造一个图 G，点为原树的边，并且每个点对应的边集构成一个完全图，那么问题转化为在图 G 上定根的 dfs 树计数。

一个重要的观察是 dfs 树没有返祖边，因此每一个边集完全图在 dfs 树上一定呈现为一条链，而链与链之间的交点是固定的。至此再把问题转化为，对于每一条链都钦定一个顺序的方案数。

考虑定根的影响。发现定根意味着对于每一个边集完全图，其对应的链的一个端点会由根确定。具体地，若根为 x，x 子树内的边集对应的链，其中一端一定为父边；子树外边集对应的链，其中一端一定为走到 x 经过的边。

至此定根就非常好算了，其实就是 \prod (deg-1)。对于多定根的情况考虑容斥，即求 \sum (-1)^{|S|}f(S)。

进一步观察，S 内的点一定要位于一条简单路径上，否则一定存在一个边集被钦定三个端点；而对于一个简单路径上的关键点，其有效约束点只有简单路径的两个端点。对于该点集 S，f(S)=\prod_{i\in \text{path}}(deg_i-2)\prod_{i\not\in\text{path}}(deg_i-1)

因此我们设 f_{x,0/1} 表示子树 x 内选择了一条链，链上有奇数/偶数个关键点的方案数的 \sum (\prod\frac{deg-2}{deg-1})，转移是简单的。

时间复杂度 O(n)。

D

NOIP D<C 是什么神秘仪式吗。

不会那个神秘结论，想的时候走了挺多弯路，但传统DS切入点非常有限，还是做得出来。

考虑枚举 lca 处的点 x，那么 x 的贡献是若干个在子树节点未出现的极长编号连续段。

注意到这个极长编号连续段的个数是 O(n) 的，因为段与段无交，可以看作对 n 个点建树，总段数 \le 2n-1。

一个段 [L,R] 对一组询问有贡献，当且仅当 \max(L,ql)+qk-1\le \min(R,qr)。

注意到 ql+qk-1\le qr 是恒成立的，因此上式是一个三维偏序，cdq分治即可。

时间复杂度 O(n\log^2n)。

总结

我他妈为什么最后一战是 NOIP2023 而不是这个 NOIP2024？？？？