2022/8/2 考试总结

时间安排

7:30~8:00

写了个T1,T3的暴力。

8:00~9:00

T1显然可以二分答案之后枚举lca，复杂度$O(nlo{g}^{3}n)$有72分，写完调完。

9:00~10:00

T1因为树的形态随机，所以直接dfs一遍树把所有合法的二元组用数据结构维护就行了。
复杂度$O(1)-O(\sqrt{n})$或者$O(logn)-O(logn)$感觉分块很悬于是写了线段树二分。

10:00~11:10

T3是max卷积和异或卷积的拼合体，所以分别做就行了，复杂度$O(n^{2}logn)$，有62分。

11:10~11:30

写T2的暴力

11:30~12:00

链的部分显然可以用组合数算，又想了一会dp发现不太会。

考后总结

T2

其实是个很简单的dp，设$f[i][j]$表示i的子树内选了j个点access的方案数，然后钦定每个状态被可以得到这个状态的最少花费处计算，考场上没想到这一点。其余部分就是简单地树背包。
还是要练习dp的水平。

T3

异或对于每一位是独立的，因此对于每一位分别用FFT差卷积计算方案数，再用max卷积合并，这样的好处是不需要FWT，复杂度$O(nlo{g}^{2}n)$。
另一种做法是用数位dp统计，不过还没看懂。