The 13th Chinese Northeast Collegiate Programming Contest(Gym 102220)

来自PC Wiki
跳到导航 跳到搜索

Records

Solutions

A(Unsolved)

B(Solved by: lzy)

枚举$$C$$, 考虑可选取的种类, 在不超过限制的条件下最大化价值和即可.

C(Solved by: sqc)

对于每条线,和他相交的线的个数为$$(n-1)$$减去和它平行的线的条数加上和它重合的线的条数

D(Upsolved by: sqc)

考虑$$m$$个操作最多将树上分成$$m$$个不同的权值段

这些权值段的端点只可能是操作中的端点

我们选操作中的端点作为关键点建立虚树

然后在虚树上暴力爬树

注意边上没有点的情况

E(Solved by: zhn)

简单分析后可知每个点对答案的贡献就是求与之邻接的边中最小边权w,然后w*(deg-2)加到答案里

F(Unsolved)

G(Solved by: lzy & sqc)

发现两维坐标独立,对每维分别做

变成了一堆闭区间,选一个位置,最小化完全在其左边的右括号到其距离和加上完全在其右边的左括号到其距离和

考虑答案可能存在的点为区间端点

扫两遍即可

H(Solved by: zhn & lzy)

观察发现对于一个区间$$[l, r]$$, 答案是$$h_l + \sum_{i = l + 1}^r \max(h_i - h_{i - 1}, 0)$$

那么我们维护这个式子即可, 事实上是维护原数组, 以及原数组的差分, 使用两个树状数组即可.

I(Unsolved)

J(Solved by: sqc)

签到题