View source for 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 (+)

题意：指定数列的长度 n。要求构造两个数列，使得对于所有询问的数对的大小比较结果一样，且一个数列中没有重复元素而另一个中有。

题解：如果所有数之间都比较过了，那么显然无解。否则把没比较过的两个数设为 1/1 和 1/2，其他数任意填成互不相同的。

== 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 J ==

Upsolved by zerol.

题意：给两个字符串 s 和 t。各自取一个非空前缀拼接而成能产生多少本质不同的字符串。

题解：首先利用 Z 函数求出 t 的每个前缀在 s 中出现的次数。用前缀函数处理处 t 的每一个前缀的最长 border。现在要计算有多少种重复的方案数。对于 t 的每一个前缀，考虑 t 和 t 的最长 border 重合（如果重合的 border 更小，那么在该 border 作为前缀的时候计算），剩下的部分在 s 中出现的次数就是重复的计数，从答案中减去即可。

== Problem K ==

Solved by kblack. 01:28 (+)

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

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

== Problem L ==

Solved by zerol. 02:22 (+)

题意：有大小为 a 和 b 的教室，单双周切换，每个同学一学期至少上 k 次课，问最多能支持多少同学。

题解：考虑这两个教室的总容量（单位 人次），最后的答案可能是受到总容量限制，也可能是单个容量限制，对于这两种限制对答案取 min 即可。设大小为 $a$ 的教室开放 $t_1$ 周，大小为 $b$ 的教室开放 $t_2$ 周，那么答案就是 $\min\{\lfloor \frac {at_1+bt_2}{k} \rfloor, \lfloor \frac {at_1}{k-t_2} \rfloor, \lfloor \frac {bt_2}{k-t_1} \rfloor \}$。

zerol：这一类题目就是考虑最后限制的情况，然后取 min 即可，省下了更复杂的讨论过程。在这题中，如果受到单个的限制，那么另一个可以看做无限多，那么可以简单算出这时候的答案。

== Problem M ==

Solved by kblack. 00:04 (+)

温暖的签到。