2019-2020 ICPC, BAPC

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

Records

[Contest]

Solutions

A

显然我们应该让值更大的人参与尽可能多的比赛

所以依然是基于树深度的贪心,每次选取可行链最长的点给当前值最大的人,然后暴力标记可行链为不可行并做修改

因为每个点只会被标记一次不可行,所以均摊复杂度$$O(n\log n)$$

B

签到题

C

D

E

F

G

暴力扩展40步,剩下的就是能框住黑格子的最小矩形中白格子数量不变,算一下就好了

H

简单贪心,我们发现对于一个$$x$$的花瓶,我们按照$$(x - 1, x), (x, x), (x, x + 1)$$的顺序尝试进行匹配总是最优的

所以把花瓶和花台排序扫一下即可

I

观察发现$$k = m - n + 1$$不太大

由于图连通,我们抠出一颗DFS树(其实不连通就是每个连通块的答案加起来233),然后观察返祖边

显然返祖边刚好有$$k$$条,我们暴力枚举所有返祖边的子孙点是否选取,然后做一个树DP即可

复杂度是$$O(n2^k)$$

J

分解质因数

K

特判在两点连线上的情况

然后用三角形框住这个点,解个方程

L

概率收敛,计算几千轮

$$f[i][j]$$表示第i轮一个人还有j条命的概率

然后枚举轮数

$$g[i][j]$$表示前$$i$$个人里面有$$j$$个人还有一命的概率

计算一下