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

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.