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 (+)
题意：有一些盒子，每个盒子里有数量，种类不同的物品，每次操作可以把一个物品从一个盒子里移到另一个盒子里，但移动过后每个盒子里的物品种类不能相同，求最少的移动次数，使得物品最多的盒子和最少的盒子的物品数量差最小。
题解：有一个结论，是把东西从物品多的盒子移到物品少的盒子，一定有解。
现在，每次找出物品最多的盒子和物品最少的盒子。如果其物品数相差 $\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 (+)
题意：对于一个序列，求出其中最长的连续子序列，使得其中任意两个相邻位置的元素都不想等。
题解：在每两个相邻相同元素之间插入隔板，在开头和末尾加上隔板，题目转变为求两个相邻隔板间最大距离，枚举即可。