2019-2020 ICPC, NERC, Northern Eurasia Finals

Problem A

Solved by Xiejiadong. 04:08 (+4)

题意：给出一些种类的任务，每个任务完成需要固定的时长，必须在给定的时间范围内完成，求能完成的最多任务数量。

题解：考虑贪心，一定是从前往后依此做，有多个任务可供选择的时候，一定会选择当前单次任务所需时间最少的。

唯一需要处理的地方就是，每一个新种类任务开头的地方，一定是选择结束时间较早的。

但是可能会有相会嵌套的问题，引入一下反悔机制就可以了。

Problem B

Solved by Xiejiadong. 00:46 (+2)

题意：祖马游戏，求有多少位置可以放入一个珠子后，消除所有序列。

题解：可以放入的一定是最中间的一段。

也就是每次都是消除最中间的，合并两边，继续消除。

于是找到最中间段的长度 $+1$ 就是答案。

Problem C

Unsolved.

Problem D

Unsolved.

Problem E

Solved by Weaver_zhu. 00:13 (+)

Problem F

Unsolved.

Problem G

Unsolved. (-5)

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Solved by Xiejiadong. 02:17 (+2)

题意：给出不同种类的物品，要求用最少数量的屏幕显示他们，需要满足：

• 每一个屏幕只能显示同一种类的物品；
• 如果屏幕的容量为 $s$ ，一个屏幕显示的数量必须是 $s$ 或者 $s-1$ 。

题解：显然对于不同种类的物品分开考虑。

如果我们枚举 $s$ 的大小的话，那么可以发现 $s$ 最大只能取 $min\{$ 每种物品的数量 $\}+1$ 。

很容易发现，直接枚举 $s$ ，暴力对于每一种类判断复杂度是可以接受的。

那么对于第二个限制，假设显示屏数量为 $k$ ，这一种类的总数 $x$ ，需要满足 $(s-1)k\le x\le sk$ 。

我们需要找到满足要求最小的 $k$ ，直接可以通过计算得到。

Problem K

Solved by Weaver_zhu. 02:23 (+1)

Problem L

Solved by Xiejiadong. 00:31 (+)

题意：要把字母分配给 $n$ 个长度为 $l$ 的字符串，使得字典序排名为 $k$ 的字符串字典序尽可能小。

题解：很经典的套路题。直接贪心。

从小到大排序以后，对于前 $k$ 个字符串分配第一位，对于和 $k$ 第一位相同的字符串继续分类第二位，以此类推。

然后剩下的字母，直接从小到大填满空位即可。