2022/8/3 Exam Summary

时间安排

7:30~8:00

先看了一遍题,It doesn't feel like one,非常自闭.

8:00~9:00

写了T2的暴力.

9:00~9:20

写T3的暴力

9:20~10:00

写T3the second and third gears,But somehow the answer is always big.
于是就放弃了

10:00~11:00

T1It can be done after Stirling split power,But don't know why the answer is always wrong.自闭.

11:00~12:00

想了想T2的$O(n^2)$,Finished writing a large sample.

考后总结

T1

It is the routine of using Stirling number to divide the power,into a composite meaning,Then proceed through tolerance and exclusiondp,All in all, it's very tricky.
I made a typo during the exam,导致挂了.

T2

$O(nlo{g}^{3}n)$

dsu on tree,Then use the tree chain to divide the statistics$d[y]-2\ast cnt[x][y]$
复杂度$O(nlo{g}^{3}n)$,But the constant is not big.But very good.

$O(nlo{g}^{3}n)$

Merge maintenance with segment tree,Then there is the tree chain segmentation,不过空间是$O(nlo{g}^{2}n)$,很危险.
So each heavy chain shares a segment tree,So the spacelog.

T3

就是dp,It's just that the author did better.
待upd.