2018-2019 Russia Open High School Programming Contest

Problem A

Solved by kblack. 00:17 (+1)

温暖的签到。

Problem B

Solved by ultmaster. 01:09 (+)

题意：将若干字符串按照某种解析到的规则排列起来。

题解：字符串解析模拟。

Problem C

Solved by ultmaster. 03:57 (+1)

题意：有 $n$ 个小朋友，每个小朋友有一些互不相同的礼物。现在要对礼物进行再分配，使得：每个小朋友的礼物还是互不相同的，且礼物尽可能平分。求最小操作次数。

题解：有一个重要的观察 (by kblack) 就是种类多的往种类少的里塞一定是可以的。不妨把所有人按目前拥有的礼物数量排序。然后从两头扫，对于每一个待分配的小朋友，都去当前「被安排」的小朋友里找它能用的东西（的区间的开头）。具体来说有如下情况：1. 那个小朋友的最小的礼物，即 begin；2. 待分配的小朋友的每一个礼物在被分配的小朋友的集合中的 upper_bound。对于上面这些迭代器，每一个都往下遍历，依次送出（并删除），直到礼物不可用为止（不可用了以后会有下一个迭代器接上）。然后如果是小的塞满了，就分配下一个小朋友，如果大的不能再减的，就移动另一边。

最坏情况下复杂度是玄学（怀疑和根号有关），但不知怎么的就过了。

Problem D

Solved by zerol. 01:18 (+)

Problem E

Solved by kblack. 02:11 (+)

题意：棋盘上有一堆🐎，要求把所有🐎走到下侧，不足一排的贴在左边，要求不能重叠。

题解：所有这类题，要求不能重叠都是假的，因为重叠的时候转化为移动下一个就行了。随便找个对应顺序，按最短路走一走。

Problem F

Upsolved by ultmaster.

题意：有 $n$ 个数让你猜，每次询问三个下标，回答你这三个下标上的数的最大值和最小值的和。要求在 $4n$ 次内猜出来。

题解（无脑）：考虑 $n=5$ 的做法，总共能拿到 10 份信息，暴力枚举顺序后，列出方程，用高斯消元解出来，判合法性。然后 5 个 5 个做下去就好了。

全真模拟现场赛意识模糊写不了题的症状。

Problem I

Solved by zerol. 00:47 (+1)

Problem K

Solved by kblack. 01:28 (+)

题意：定义一个关系，一个串表示 ABBBBB，定义互相是子序列的可以在一组，求分最小组数。

题解：容易发现这个关系是自反对称且传递的，所以划分即是答案，每个串表示为 B 部分每个字母是否出现以及 A 部分去除在 B 中出现的后缀字母。

Problem L

Solved by zerol. 02:22 (+)

Problem M

Solved by kblack. 00:04 (+)

温暖的签到。