2019.11.1考后总结

mac2025-11-29  12

T1 : WOJ4785

模拟题,注意不要爆long long

T2 : WOJ4786

桶套桶,一个桶记录出现次数,一个桶记录出现次数的出现次数,用类似滑动窗口的方法删除及插入即可。

时间复杂度: O ( 常 数 极 大 × n 2 ) O(常数极大\times n^2) O(×n2)

T3 : WOJ4787

上面的点必然比下面的点的权值大,故一个点的子树必然无法取到。若一个点的欧拉序编号分别为 ( l , r ) (l,r) (l,r),那么有用的区间就为 [ 1 , l − 1 ] ∪ [ r + 1 , n ] [1,l-1]∪[r+1,n] [1,l1][r+1,n]。用树状数组维护外面的能够到达的点的或和,以权值为下标,前缀或和为值插入,维护一下即可。

最新回复(0)