Gym 101623 题解

B

\max(1,n-2)

D

模拟。

G

每个多边形直接算内外多边形半径。

H

数足够大的时候 7\times \min 的贡献太小,加最大数一定最优,所以枚举一下较小两个数加多少。

I

\max(d,s)-s 从大到小排序做背包。

K

要让强的和强的打,所以除 1 号外从小往大排,相邻的配对,每次 O(n^2) 合并概率。


A

先离散化,合并连续相同的。

值域从小到大 dp,从值 i 转移到 i+1 时,如果有 a_x=i,a_{x+1}=i+1 的情况,那么 f_x 可以少切一刀转移到 f_y(a_{y}=i+1,y\ne x+1),一层一层转移的时候只需要记下转移的最大值,最大值 ban 掉的位置,和次大值就行了。

C

一个数一个数贪心,维护当前这个数有可能的出方向区间,如果包含下一个点,那么直接延申过去,否则就必须拐一下弯,更新一下这个点的出方向区间。注意由于线不能无限延长,所以区间的端点还要判是开的还是闭的。

E

先排序,补 t+\infty 的桌子,最后被占领的桌子一定是若干个区间。

考虑对这些区间做区间 dp,设 f_{l,r} 表示区间 [l,r] 被全部占领的方案数和总答案,转移就枚举最后一次占掉的桌子 k,那么左右方案数是 f_{l,k-1}f_{k+1,r},最后一次能选的数是 (a_{l-1},a_k],再乘个组合数就行了。

最后把这些区间再做个背包。

F

先预处理出每个点左右可以覆盖的 \gcd=1 的最远点。从左往右扫,栈维护当前二叉树最右边的一条链。

加入一个点 i 的时候,假设栈最后两个元素是 a,b,如果 r_i \ge r_{b} 并且 l_{i}\le a+1,那么可以贪心地用 ib 吃进左子树。如果弹完以后 r_{top} 则无解。

J

手推或者打表可以发现每个 2 的贡献是,找到它所在这个非 0 连续段,把左右边的 0+1,然后把这个位置和段中与其对称的位置都 -1。而且打表可以发现有多个 2 的时候可以依次处理。

发表评论

电子邮件地址不会被公开。 必填项已用*标注