XIX Russia Team Open, High School Programming Contest

Problem A

Solved by Weaver_zhu. 00:10 (+)

Problem B

Solved by Xiejiadong. 02:22 (+)

字符串签到。

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

Problem C

Solved by Kilo_5723. 03:19 (+)

Problem D

Solved by Kilo_5723. 00:45 (+)

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 (+)

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 (+)