2021.09.22模拟赛

又是六道题

2021.09.22模拟赛

A. 极好的问题

极好的问题

枚举两个数找第三个数就行，有点小细节

$O(n^2\log n)$

code

B. 打铁的匠

打铁的匠

主席树板子题

dfs 序上查询子树深度 $\ge dep_u+k$ 的和即可

code

C. 扭动的树

扭动的树

按 key 排序后每个子树都可以表示为一个区间，记 $dp_{0/1,l,r}$ 表示当前 $[l,r]$ 区间作为左右子树时的最大和

转移枚举根节点即可，需要判断下 $\gcd$ 能不能连边

code

D. 座位安排

座位安排

贪心

考虑前门的人能坐下的是一条斜线内的区域，先按照 $s$ 排序，贪心的让作为匹配到达它的 $s$ 最小的

code

E. 红心大战

红心大战

纯模拟

code

F. 购物

购物

先排除掉包含区间

处理出来每个点能到达的最右的点，$O(n^2)$ DP划分这个序列即可

code