20220802NOI模拟赛--考后总结

时间安排

7:30–7:35 读题。

7:35–9:00 T1,想到二分答案后枚举一条路径的lca,然后寻找符合范围的点，可以用vector+二分维护，但是是3个log跑的巨慢，卡常卡半天没什么用。暂时想不到什么别的做法或者优化。

9:00–9:30 T2,hs队列通过暴力。

9:30–10:00 T2,对于链可以钦定一条边为1，剩余可以组合数求解。考虑链能否扩展到树上，发现可以用一维状态表示那条为1的边是否存在，枚举一个点选或不选大概就可以DP了，但是有一些特殊情况需要分类讨论，先做后面的。

10:00–11:00 T3, $b\le 5$ 可以 dfs; $b\le 80$ 可以考虑钦定最大值，然后做背包。 取 max 可以用前缀和优化到 $b\le 300$ .忽然发现可以做 FWT 省掉一个 $n$ ，但是模数很鬼畜 $2^{64}$ 觉得做不了就没再往 FWT 想。感觉到瓶颈了，去做T2.

11:00–12:20 T2,设状态DP，有几个DP需要分讨，调了很长时间。対拍确定无误。

回顾&反思

T1: 想到了二分答案，但是其有瓶颈无法通过此题。忽略了边权较小可以对权值和做桶，那么一个点的决策点可以暴力加入删除。用树桩数组可以实现优雅的倍增。还是要多关注数据范围的特殊性。

T2: 比赛的时候写出了 $n{k}^2$，在其基础上加一个剪肢的 trick 就可以达到 $nk$ 通过此题了。这个 trick 以前没见过，或者说没想到它能优化掉一阶复杂度。具体是，做树形背包或类似合并问题时，若合并的那一维值域小于等于子树大小，那么可以在枚举时设置一个子树大小和的上界，DP时可以动态维护。

T3: 其实比赛时的做法可以用 FWT 扩展到 $b\le 2000$ 多拿 20pts 的，数字的确很大，但是达不到 $2^{64}$ 的模数。于是可以直接无视模数做，可以用 int128 进行计算，还是对数据范围没有深入估量。对于正解，考虑到公式中二进制下每一位独立，那么可以分别对每一位做背包，这样可以就无需枚举整个数的值，而是枚举某一位是 0/1 ，省掉一个值域的复杂度，变为简单的 0/1 。对于类似 $x-y=k$ 绝对值的卷积可以枚举正负性分别做多项式乘法,即 $x-y=k$ 或 $y-x=k$，注意 $k=0$ 时不要算重。以后碰到这种涉及到位运算的题目要考虑能否按位拆开做。