2019-2020 ICPC, NERC, Northern Eurasia Finals

From EOJ Wiki
Revision as of 07:09, 6 December 2019 by Xiejiadong (talk | contribs) (→‎Problem J)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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$ 第一位相同的字符串继续分类第二位,以此类推。

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