8.2模拟赛总结

难得的没有挂分）

7.30-8.30

看T1 感觉没啥好想法 没编出来什么依赖log树高的做法

想到二分答案之后不知道怎么check

8.30-10.00

看T3 打部分分 想了想还能不能优化

10.00-11.30

看T2 把链也写了 然后想了想往后怎么做

11.30-12.30

想T1

题目分析

T1

暴力求c数组

upd

考虑二分答案为$mid$ 那么我们就需要统计小于$mid$ 的路径条数

注意到我们不用枚举每个端点 而是可以采用枚举lca来计算的方式

考虑优化，我们发现我们枚举每个点的时候 都在重复路径上跳考虑所有lca

因此我们可以考虑dfs 然后加进去所需要的点 这样lca在dfs的时候就已经知道了 把值放到树状数组里然后而二分就行

T2

这个题其实我做的不好 因为我想到链了之后 我的做法是非常容易往树上靠的

$f[i,j,op]$ 表示前 $i$ 个位置形成指定序列最少需要 $j$ 次操作 最后一个点的状态是$op$

这样每一种序列就可以唯一表示

upd

正解考虑上述dp上树 然后一个巧妙的地方就是 为了避免巨大分类讨论 可以考虑 access操作对应儿子边全0（但如果子树内没有acc的话 则不用操作） 否则对应有一个儿子有边

为了简化上述操作 我们强制让儿子边全0时必须acc 但转移时 如果出现了儿子父亲均acc了（且儿子的子树内仅有儿子acc了） 则可以去掉儿子acc的方案

T3

考虑dp $f[v1][v2]：max=v1,xor=v2$ 的方案数

upd

一个好的优化技巧：max这个东西可以讨论是在什么位置取到max的 然后就可以前缀和优化

正解考虑每一位分开做

$f[M][bit][v]$ 表示$max=M$ 第 $bit$ 位 是 $v$ 的方案数

那么其实就是要求我们求有多少个$i$ 满足 $(i+M)xorM$ 的第 $bit$ 位是 $v$

我们发现这个东西只和$M,i$ 和$M+i$ 是否进位有关

那么可以枚举$i$ 在这一位的值 然后计算有多少个$i$ 满足这一位上是$t$ 且异或之后 进位/不进位