XIX Russia Team Open, High School Programming Contest

From EOJ Wiki
Jump to navigation Jump to search

Problem A

Solved by Weaver_zhu. 00:10 (+)

Problem B

Solved by Xiejiadong. 02:22 (+)

字符串签到。

直接拿 map 给每一个字符串编号即可。

Problem C

Solved by Kilo_5723. 03:19 (+)

题意:有一些盒子,每个盒子里有数量,种类不同的物品,每次操作可以把一个物品从一个盒子里移到另一个盒子里,但移动过后每个盒子里的物品种类不能相同,求最少的移动次数,使得物品最多的盒子和最少的盒子的物品数量差最小。

题解:有一个结论,是把东西从物品多的盒子移到物品少的盒子,一定有解。

现在,每次找出物品最多的盒子和物品最少的盒子。如果其物品数相差 $\le 1$,说明物品数量差已经最小,否则从物品最多的盒子中拿出一个物品放到最少的盒子中,再找最多和最少的盒子,直到满足条件。

问题于是转化为了子问题:维护两个集合,使得每次可以从大集合中快速找出小集合不存在的内容。

可持久化线段树的变种正好能满足这一需求。

我们用线段树上的链来维护一个盒子中存在的物品,由于每次可以要找的内容都是大集合存在但小集合不存在的,所以解一定在大集合的链上,而且如果对两个线段树做差,一定能找到至少一条链,使得上面的每个节点,大集合在该点上子树的叶节点个数都严格大于小集合的节点个数。

趁着没人占机,敲了 45 min 的代码,一次(WA1不算罚时)就过了

Problem D

Solved by Kilo_5723. 00:45 (+)

题意:给出数对位置,构造两个数列,使得两个数列中一个不含有相同元素,另一个含有两个相同元素,并且这两个数列对于给出的数对位置的比大小的结果都是相同的。

题解:找到一对没有被比较的数对位置,在第一个数列里填上两个相邻的数,在第二个数列里填上相同的数,其他位置随便填就可以了。

Problem E

Upsolved by Weaver_zhu. (-3)

Problem F

Solved by Xiejiadong. 03:30 (+)

题意:每次询问三个下标,给出这三个下标位置的三个数的$max+min$,求这个数列。

题解:对于四个数,我们不妨假设$a\le b\le c\le d$,那么每次去掉一个数做四次询问,显然这个询问中的最大值+最小值就是这四个数的和,因为在上面的情况中最大+最小$=(a+b)+(c+d)$。

然后我们对于前五个数,对于每四个数询问出和,就可以得到这五个数的具体情况了,这样一共需要的询问次数是$4*5=20$。

然后对于之后的每个数,我们只需要询问他前面三个数和他四个数的和(需要四次询问),即可得到他的准确值。

前五个数的情况,我们用了$20$次,正好$4*5$,之后的每个数得到都需要$4$次询问,所以总的询问次数正好是$4n$,卡着过。

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Solved by Xiejiadong. 01:26 (+4)

题意:求一列数中任意一对有序对相乘的最小值。

题解:对于每一个数,找一个他前面比他小的数中最小的,找他后面比他大的数中最大的即可。

显然,这样涵盖了最优解可能产生的位置。

Problem J

Unsolved.

Problem K

Solved by Kilo_5723. 01:38 (+)

题意:$n$ 个无限长字符串,由开头和无限次数的循环节构成,求出最少的划分方案,使得划分出的每一个无限字符串集合都互为子序列。

题解:对于循环节,我们只要知道哪些字符在其中出现过就可以了。同样的,对于开头,在末尾的循环节含有的字符都是不需要知道的,可以去掉。而要两个字符串互为子序列,循环节出现过的字符和开头删去末尾循环节包含的字符必须相同。用 map 维护 string 到 vector 上的映射即可(虽然常数可能相当大)。

Problem L

Solved by Xiejiadong. 01:04 (+1)

题意:单周上大小为$a$的教室,双周上大小为$b$的教室,一共$n$周,每个人需要至少上$k$周才能合格,求最大合格人数。

题解:考虑单周、双周、以及所有时间的情况下对人的限制。

设单周有$x$,双周有$y$,显然答案就是$\min\{\lfloor \frac {ax+by}{k} \rfloor, \lfloor \frac {ax}{k-y} \rfloor, \lfloor \frac {by}{k-x} \rfloor \}$。

不过需要注意分母$\le 0$的时候,说明限制没有意义,不需要考虑。

Problem M

Solved by Kilo_5723. 00:14 (+)

题意:对于一个序列,求出其中最长的连续子序列,使得其中任意两个相邻位置的元素都不想等。

题解:在每两个相邻相同元素之间插入隔板,在开头和末尾加上隔板,题目转变为求两个相邻隔板间最大距离,枚举即可。