Southern and Volga Russia Qualifier 2019-2020

Problem A

Solved by Kilo_5723. 00:12 (+1)

Problem B

Solved by Weaver_zhu. 00:43 (+)

Problem C

Solved by Xiejiadong && Kilo_5723. 02:37 (+)

题意：要将所有相同的数字通过相邻位置的交换使得全部相同的数字都放在一起。

题解：相当于要给每一个数字一个权值，使得按照权值的逆序对数量最小。

因为数字只有 $20$ 个，所以可以考虑状态压缩 dp。

状态压缩 dp 的时候，需要转移，每次转移也都需要计算一遍当前新加入的权值对总答案的影响，复杂度是 $O(2^{20}\cdot 20\cdot 20)$ 。

考虑通过大力预处理来降低复杂度。

但是直接的预处理也是需要 $O(2^{20}\cdot 20\cdot 20)$ 的复杂度，我们可以考虑从已有的状态推到当前的状态，可以通过去掉 lowbit 的方式来递推。

Problem D

Solved by Kilo_5723. 00:36 (+1)

Problem E

Solved by Weaver_zhu. 00:19 (+)

Problem F

Solved by Xiejiadong. 00:44 (+)

题意：统计一个数列所有的连续子数列中乘积分别为负数、正数、零的个数。

题解：可以通过前缀乘积直接计算得到。但是要注意 $0$ 的影响。

只能对当前最长的一段无 $0$ 后缀进行处理。

Problem G

Solved by Xiejiadong. 01:06 (+)

题意：要求对于仅包含字母 "a" 和 "b" 的两个字符串，通过每次交换两个字符串中的某两个位置使得两个字符串相同，要求交换的次数最小。

题解：显然，只需要对每一个两个字符串不同的位置进行交换。

假设不同位置中，第一个字符串包含 $x$ 个 "a" 和 $y$ 个 "b" ，显然对应的第二个字符串 $y$ 个 "a" 和 $x$ 个 "b" 。

如果 $x+y$ 是奇数的话，显然是无解的。

而对于形如 "aa" 对应 "bb" 的位置，通过一次交换就可以调整成功。显然如果 $a$ 是奇数的话调整到最后一定会有 "ab" 对应 "ba" 的形式，最后剩下的这两个位置，必须通过两次才能调整成功。

Problem H

Solved by Kilo_5723. 01:59 (+3)

Problem I

Upsolved by Weaver_zhu && Kilo_5723. (-2)

Problem J

Solved by Weaver_zhu. 01:38 (+)

Problem K

Solved by Weaver_zhu. 02:03 (+)

Problem L

Solved by Xiejiadong. 01:55 (+1)

题意：要求在某一个位置放置一个打印机，使得所有人到他的距离最小。

题解：枚举打印机放在每一个位置的时候，最远的距离。取最小值即可。