InfOJ NOIp2023 模拟
InfOJ 的模拟赛，应该是 bot 从他之前出的模拟赛非公开题里找的。
幸好没用 Rugby 那道题，不然我直接开贺了，不过我好像至今没改 Rugby 来着 /ll。
感觉四道题难度都在 NOIP T2 ~ T3 左右。
Website, Official solution, Statement
T3 题目订正
本题输入格式实际上为第二行 \(n-1\) 个数表示每个点的父亲节点。而不是 \(n-1\) 条边。
本题特殊性质 A 为不存在 \(f_i=-1\)
本题样例修改为
1 2 3 | |
1 | |
数据范围中 test 20~25 的 \(n,m\) 是 \(150000\)。
Aψ(｀∇´)ψ
赛时写了一个 \(n^4\) 的值域无关做法，假了。
考虑直接枚举中间的子问题，两边直接删掉，这样转移是 \(O(n^5)\) 的，利用一下 and 存在的单调性可以 \(O(n^4)\)。
但是这有问题，不过考量是差不多的，考虑设 \(dp(l, r, val)\) 表示区间 \([l, r]\)，被删掉的数 and 和为 \(val\) 的最大操作次数。
这样有了值的限制，转移就不需要删完了，于是 \(dp(l, i - 1, ?), dp(i + 1, r, ?)\) 分别是子问题，转移可以做到 \(O(n^3V)\)，。
有一定的边界要判，不过这很容易注意到。
Bψ(｀∇´)ψ
Cψ(｀∇´)ψ
感觉是经典题目，之前见过类似的 Trick 不过没总结，可能那个题都直接没做。
考虑暴力的想法就是，直接设 \(dp(u, msk)\) 表示考虑 \(u\) 子树当中，选出颜色状态为 \(msk\) 的方案数。
首先这显然没法有很好的复杂度，考虑优化。（其次这个不能很好的表示恰好的限制。）
这种 \(O(2^m) \to O(m)\) 的过程基本都是考虑，我们可以不关心具体选了哪些，只关心选了的个数也就是 \(|msk|\)。
但是这样还是没法转移，因为你发现我们可能会算重，比如有两个子树，限制分别为 \(4, 5\)，然后合并到 \(u\)，你发现 \(u\) 子树内可能的颜色个数（不考虑 \(u\) 的限制的存在），应该是 \([\max\{f_{v}\},\min((\sum f_{v}) + 1, m)]\)。
一个比较笨的想法是直接类似树形背包把子树状态合并上来，合并的时候枚举算重多少个，但是这复杂度太高了我们不能接受，所以怎么办呢？
就，套路的考虑容斥，钦定出现 \(i\) 种颜色，假设 \(dp(u)\) 表示 \(u\) 子树内恰好有 \(f_{u}\) 种颜色的方案数。
复杂度 \(O(nm)\)。
考虑优化，注意到 \(i\) 有一部分是不会做贡献的，因为组合数的存在，所以我们直接从 \(f\) 最大的儿子开始枚举，这个可以看作重儿子，于是这形如轻儿子之和。
但是这还不太对，会有相同的 \(f\) 存在，我们需要合并，然后可以快速幂计算代价，这样复杂度就是 \(O(n\sqrt n)\) 的，可以看 UR #26 石子合并的题解。
对于 \(f_{i} = -1\) 的情况，我们把他的子节点全部合并到他的父节点下就可以了。