Samara Farewell Contest 2020 (XXI Open Cup, GP of Samara)

From EOJ Wiki
Jump to navigation Jump to search

Problem A

Unsolved.

Problem B

Solved by Xiejiadong. 00:21 (+)

题意:每次都会随机给出两个选择,$a$ 分钟获得 $b$ 单位黄金或者 $c$ 分钟获得 $d$ 单位黄金。询问无穷时间下的单位时间获得黄金数量。

题解:考虑二分答案 $mid$,我们只需要判断是不是可以达到这个速度,即对于每一个选择,我们考虑的是超过部分的收益,也就是 $b-a*mid$ 和 $d-c*mid$ ,只需要判断总和是不是大于零即可知道收益是否可以得到。

Problem C

Unsolved.

Problem D

Solved by Kilo_5723. 00:31 (+1)

Problem E

Unsolved.

Problem F

Unsolved.

Problem G

Solved by Weaver_zhu. 00:32 (+)

签到

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Solved by Xiejiadong. 04:03 (+)

题意:告诉每个眼睛颜色的真实人数和下限,判断有多少人可以推断出自己眼睛的颜色。

题解:当 $a=1,b=1$ 的时候,有这个颜色的人发现没有人有这个颜色就知道了自己的颜色,自杀了。

对于其他情况,例如 $a=2,b=1$ 的时候,假设我是这个颜色,但我不知道,但我发现我看到这个颜色的人第一天没有自杀,于是我就知道了我也是这个颜色。同理可以发现对于非零的 $b$,这一群人会在 $a-b+1$ 天统一自杀。

最后需要特判只有一个 $b=0$ 和所有 $b>0$ 的情况。

Problem K

Solved by Weaver_zhu. 03:07 (+)

后悔机制,先把小怪 a 到只剩一滴血,等之后血不够用的时候再来收割。显然可以先把 $t > h$ 的都存起来。对于 $t > h$ 的小怪,可以证明两个怪要打的时候如果 $h_1 > h_2$,先打 ($t_1, h_1$) 一定更优

Problem L

Solved by Xiejiadong. 01:32 (+)

题意:删掉最少的数使得 LIS 长度 $\le k$。

题解:可以观察到数列中的每个数范围都是 $[1,k]$ ,也就是 LIS 长度为 $k$ ,只可能是 $1,2,3,\cdots , k$ 。

可以发现,如果这个数的左边有存在与其相同的数没有删除,那么我们删除它也没有用。而这个数列的 LIS 长度 $\le k$,当且仅当任意一个数字被切断,所以我们可以用 $f[i]$ 表示当前位置为相同数中最左边的数的时候所需要删除的最少数量,$n+1$ 位置为超级位置,可以是任意的数,转移就显然了。

Problem M

Solved by Weaver_zhu. 01:41 (+)

换根dp的套路,先看子树合不合法,然后在看从上面来合不合法,记录子树的最大,最小值和是否合法。判断合法的时候注意子树不能有既大于根又小于的点,传递三个值 $max, min,\text{is\_valid}$

Problem N

Unsolved.