ACGO 第 8 次挑战赛题解
本场比赛后 333 题在 Acgo\tt{Acgo}Acgo 的 Python 3.6.9\tt{Python\ 3.6.9}Python 3.6.9 下很难通过，但本文给出的代码，在 PyPy 3.10\tt{PyPy\ 3.10}PyPy 3.10 下，保证能够在时限内通过。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题解简述
以下提供每道题目的思路简述和 Python\tt{Python}Python 代码，详细题解的 AC 代码，请点击题目标题查看。
A - 交集
本题可以使用很多方法解决，这里使用集合的思想来获取两个线段的交集：
1. 令交集的左端点为 LLL，右端点为 RRR。
2. 那么 L=max(L1,L2), R=min(R1,R2)L = \max{(L_1, L_2)},\ R = \min{(R_1, R_2)}L=max(L1 ,L2 ), R=min(R1 ,R2 )。
对于本题，若 L≤RL \leq RL≤R 则交集存在，交集的线段长度为 R−LR - LR−L，否则交集不存在，长度为 000。
语法小课堂
1. 使用 std::max(a, b) 可以获取 a 和 b 中较大的那个；反之使用 std::min(a, b) 可以获取 a 和 b 中较小的那个。
注意：a 和 b 的类型一定要严格一致，并且 int 和 long long 会被认为是两种完全不同的类型。
2. 条件运算符：E1 ? E2 : E3 。若 E1 为 true 则表达式的结果为 E2，否则为 E3。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
B - 比赛结果
我们可以使用一个 std::string 数组 mat 来存储比赛对局的情况。
然后使用一个二重循环遍历这个 std::string 数组 mat，对于每个 (i,j)(i, j)(i,j)，检查 mat[i][j] 和 mat[j][i] 是否存在矛盾；
若根据题目检查发现矛盾则直接输出 incorrect，并使用 return 0 直接退出程序（ Python\tt{Python}Python 可以使用 exit(0)）。
若执行完整个二重循环后，并没有退出程序，则说明比赛结果是正确的，输出 correct 即可。
语法小课堂
1. std::vector 可以当作普通的数组来使用，在效率上几乎与普通数组相当，而且操作和功能更为强大。
2. 基于范围的 for 循环：使用 for (auto x : mat) 可以方便地遍历许多 STL\tt{STL}STL 容器。类似于 Python\tt{Python}Python 中的 for x in mat:。
3. 此处使用的 for (auto &x : arr) 多了一个 & 为 引用，表示可以对 mat 中的元素进行直接修改，而不加 & 则仅为 复制（值传递）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C - 新建文件夹（1）
令 L=10L=10L=10 为字符串的最大长度。
如果我们每次都按照题目描述中的的那样去暴力查找统计与 SiS_iSi 相同的字符串的数量，则总共需要花费 Ω(N2)\Omega(N^2)Ω(N2) 时间，从而导致 TLE\tt{TLE}TLE（超时）。
我们可以使用 std::map 来存储“到目前为止 SiS_iSi 出现的次数”（Python\tt{Python}Python 可以使用 defaultdict(int)），这样对于每个字符串 SiS_iSi 可以在 O(LlogN)\mathrm{O}(L\log N)O(LlogN) 的时间内确定要输出的字符串。
通过这种方法，可以在总共 O(NLlogN)\mathrm{O}(NL\log N)O(NLlogN) 的时间内解决问题。
语法小课堂
1. std::map<K, V> 可以创建一个具有 (K:V)(K: V)(K:V) 映射关系的容器，对于本题中，我们希望给出一个字符串，就能够获取其出现的次数，实际上是要建立一个关于 (string:int)(\tt{string: int})(string:int) 的映射关系。那么访问时就可以像数组那样使用 [] 访问。
2. 对于 Python\tt{Python}Python 推荐使用 defaultdict 而非内置的 dict。
defaultdict 会在尝试访问字典中不存在的 键 时，给定一个 默认值，例如使用 defaultdict(int) 创建字典时，若访问到当前字典中不存在的 键 时，就会返回 0，而非直接报错，其行为更接近 C++ 的 std::map。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
D - 投硬币
问题的关键点是对于投完第 iii 枚硬币时，计数器为 jjj 时可以得到的最大金额。
这个状态只和投完第 i−1i - 1i−1 枚硬币时的状态有关。
于是对于投完第 iii 枚硬币，我们可以定义 dp[i][j]dp[i][j]dp[i][j] 为投完第 iii 枚硬币后，计数器为 jjj 可以获得的最大金额。
那么有 dp[i][j]=max(dp[i][j],dp[i−1][j−1]+Xi+wj)dp[i][j] = \max{(dp[i][j], dp[i - 1][j - 1] + X_i + w_j)}dp[i][j]=max(dp[i][j],dp[i−1][j−1]+Xi +wj )，其中 wjw_jwj 为计数器为 jjj 时，获得的额外奖金。
对于无法存在的状态，比如投完第 i−1i - 1i−1 枚硬币后，无法令计数器为 jjj，那么便令 dp[i−1][j]=−∞dp[i - 1][j] = -\inftydp[i−1][j]=−∞。
另外在代码实现上我们只需要保存投 iii 枚硬币后的状态即可，所以只需要保留一维状态。
每次投完硬币后的状态数为 O(N)\mathrm{O}(N)O(N)；进行状态转移的复杂度为 O(N)\mathrm{O}(N)O(N)；总的时间复杂度为 O(N2)\mathrm{O}(N^2)O(N2)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
E - 宏量运算
对于位运算而言，每一「位」的计算结果都是 相互独立 的，而每次运算后的结果只有 000 和 111 两种可能的结果，所以我们可以单独考虑运算对每一位的影响。
* 令 oneione_ionei 为：前 iii 个运算对 XXX 中二进制位上的 111 产生影响后的结果。
* 令 zeroizero_izeroi 为：前 iii 个运算对 XXX 中二进制位上的 000 产生影响后的结果。
那么对于当前 XXX 施加前 iii 个运算的影响的结果，应为：
* 将当前的 XXX 二进制位上的 111 转化为 oneione_ionei 对应二进制位上的状态，位运算操作为 (X and onei)(X\ \mathrm{and}\ one_i)(X and onei )；
* 将当前 XXX 二进制位上的 000 转化为 zeroizero_izeroi 对应二进制位上的状态，位运算的操作为 ((X xor M) and zeroi)((X \ \mathrm{xor}\ M) \ \mathrm{and}\ zero_i)((X xor M) and zeroi )，其中 M=230−1M = 2^{30} - 1M=230−1（即有效二进制位上全为 111）；
如何维护 oneione_ionei 和 zeroizero_izeroi ？
很简单，只需要在每次操作时，将对 XXX 执行的位运算作用到 oneione_ionei 和 zeroizero_izeroi 上即可。
每次位运算的时间复杂度为 O(1)\mathrm{O}(1)O(1)，总的时间复杂度为 O(N)\mathrm{O}(N)O(N)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
F - 彩球排序
若考虑所有球的颜色都互不相同，那么本题就变为了一道经典的「逆序对」问题。
那么我们可以考虑先求出整个序列 XXX 的「逆序对」的数量，在考虑如何消除相同元素的球进行交换对答案产生的影响即可。
对于颜色同为 CiC_iCi 的 MiM_iMi 个球对应的整数序列为 Xp1,Xp2,⋯ ,XpMX_{p_1}, X_{p_2}, \cdots, X_{p_M}Xp1 ,Xp2 ,⋯,XpM 。
令其排序以后的序列为 Xp1′,Xp2′,⋯ ,XpM′X_{p_1}', X_{p_2}', \cdots, X_{p_M}'Xp1 ′ ,Xp2 ′ ,⋯,XpM ′ 。
那么求出上述序列的「逆序对」数量，并将其在最终的答案中减去即可。
在实现上，我们只需要创建一个「树状数组」，然后将球上的数字按照颜色分组。
对于每组内的数字，球的颜色都是相同的，所以我们对于这个序列求逆序对，在总答案中减去即可；
在结束后，可以再遍历一遍组内的数字，消除求逆序对的过程中对树状数组产生的影响。
然后我们再对整个数组求逆序对，便可得到最终的答案。
以上两个步骤的时间复杂度皆为 O(NlogN)\mathrm{O}(N\log{N})O(NlogN)。
> 对于 Python\tt{Python}Python 而言一个可以优化的点是，倒序处理，这样每次查找就变成了“小于当前 x 的数量”，这样树状数组可以少做一半的 ask() 运算。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
