> 前言：本次挑战赛的难度相较于前面几期有所提升，主要还是因为集训的关系，出题组的成员们没有充裕的时间想原创题目（so，只能原模原样搬运某一场 ABC 的考试了。）Anyway，AK 了就行。
>
> 备注：由于 Python 的常数过大，本题解暂不同步更新 Python 版本的题解。
第一题 - INTERSECTION
题目跳转：交集。
这道题可以用暴力的方法，也可以稍微动点脑筋。看在数据量小，直接打暴力就行了，没必要花时间去找两个线段之间的关系。
注意到 0≤L1R1,L2,R2≤1000 \le L_1 R_1, L_2, R_2 \le 1000≤L1 R1 ,L2 ,R2 ≤100，可以新建一个标记数组：如果某个坐标属于某一条线段，那么就将对应索引的标记增加一。最后再遍历一边标记数组，如果存在一个坐标被标记了两遍，那么就证明该坐标被两条线段同时覆盖住了。
最后注意输出的时候要 −1-1−1，表示区间的长度。（如果没有任何重合的区间，即 ans == 0 时，特判直接输出 000 就可以了。
代码时间复杂度：O(N)O(N)O(N)。
本题的 AC 代码如下：
第二题 - TOURNAMENT RESULT
题目跳转：比赛结果。
第二题也是一道纯暴力的模拟题目，双层 for 循环依照题目题干的要求判断点 (i,j)(i, j)(i,j) 和点 (j,i)(j, i)(j,i) 所存的值是否存在冲突就行了。这边我用了一个 check 函数来检查是否存在冲突。如果存在冲突直接返回结果即可。
这边判断冲突的 check 函数我觉得值得讲一下，分类讨论：
1. 如果双方胜负状态相同且不是平局，则返回 false。
2. 如果一方是平局二另一方不是平局，则返回 false。
3. 可以证明其余的情况一定是合法的，直接返回 true 即可，不需要跟其他题解一样大费周章来写条件分支语句。
代码时间复杂度：O(N2)O(N^2)O(N2)。
本题的 AC 代码如下：
第三题 - NEWFOLDER(1)
题目跳转：新建文件夹(1)。
也是一道水题，用 STL 的 unordered_map/ map 存一下某一个字符串出现的次数就可以了。由于 NNN 比较大，因此如果直接用双层循环遍历的话绝对会超时。
但需要注意的是，map 的单次插入/查询的时间复杂度约为 O(log2N)O(\log_2 N)O(log2 N)。因此本题的综合时间复杂度约为 O(Nlog2N)O(N \log_2 N)O(Nlog2 N)。
本题的 AC 代码如下：
第四题 - FLIPPING AND BONUS
题目跳转：投硬币。
接下来来到了本次比赛的重头戏，题目难度也在此有了一个质的飞跃（我也不清楚这次 ABC 的难度为什么这么跳跃）。
考虑使用动态规划，定义状态 dpidp_idpi 表示第 iii 次掷硬币可以获得的最大金额。（其实这道题的状态定义有很多种，用二维的 dp 也可以通过本题，本题解暂是只提供前缀和动态规划的解法）
我们可以枚举在第 jjj 次抛置硬币时选择正面和反面的价值并取最大值。所以，对于每一次投掷硬币有两种可能的决策，分别是：
1. 硬币最终的状态时正面，得到第 iii 次投掷硬币的钱，计数器自增。因此结果就是得到 x1+x2+x3+⋯+xi−1+xix_1 + x_2 + x_3 + \cdots + x_{i-1} + x_ix1 +x2 +x3 +⋯+xi−1 +xi 元钱和 y1+y2+y3+⋯+yk−1+yk (c[k]≤i)y_1 + y_2 + y_3 + \cdots + y_{k-1} + y_k\ (c[k] \le i)y1 +y2 +y3 +⋯+yk−1 +yk (c[k]≤i) 的奖金。
2. 硬币最终的状态是反面，那么计数器就从头开始计数。因此最终可以获得的结果就为从第 jjj 次投硬币时可以获得的最大金额 dpjdp_jdpj 加上在区间 [j+2,i][j+2, i][j+2,i] 投币全是正面所获的的金额（因为第 j+1j+1j+1 次投币不会获得任何的奖励）(x1+x2+x3+⋯+xi−1+xi)−(x1+x2+x3+⋯+xj+xj+1)(x_1 + x_2 + x_3 + \dots + x_{i-1} + x_i) - (x_1 + x_2 + x_3 + \cdots + x_j + x_{j+1})(x1 +x2 +x3 +⋯+xi−1 +xi )−(x1
+x2 +x3 +⋯+xj +xj+1 ) 再加上前 i−j−1i-j-1i−j−1 次计数器的奖励金额 (y1+y2+y3+⋯+yk−1+yk (c[k]≤i−j−1)(y_1 + y_2 + y_3 + \cdots + y_{k-1} + y_k\ (c[k] \le i-j-1)(y1 +y2 +y3 +⋯+yk−1 +yk (c[k]≤i−j−1) 。
可以发现，我们可以通过开设两个前缀和数组来优化算法，分别约定 suma,sumb\mathtt{suma, sumb}suma,sumb 分别表示前 iii 次投币全都是正面所获的的金额和计数器的奖励金额。因此最后的状态转移方程时可以写成：
dpi=max(dpi,dpj+sumai−sumaj****umbi−j−1)dp_i = \max(dp_i, dp_j + suma_i - suma_{j+1} + sumb_{i-j-1}) dpi =max(dpi ,dpj +sumai −sumaj+1 +sumbi−j−1 )
备注：十年 OI 一场空，不开 long long 见祖宗。请大家务必开 long long。本题的时间复杂度为 Θ(N+N22)\Theta(\dfrac{N+N^2}{2})Θ(2N+N2 )。
周后，本题的 AC 代码如下：
第五题 - MANY OPERATIONS
题目跳转：宏量运算。
一道位运算的恶心题目，跟上一题一样，可以用前缀和动态规划的思想来解决。因为每一位都是相互独立的，所以只需要按位进行 dp\mathtt{dp}dp 预处理就可以了。定义状态 dpi,j(0/1),kdp_{i, j(0/1), k}dpi,j(0/1),k 表示对于第 iii 位来说，一开始的值为 j(0/1)j(0/1)j(0/1)，经过前 kkk 次操作后这一位的值。而状态转移方程就是 dpi,j,k=dpi,j,k−1dp_{i, j, k} = dp_{i, j, k-1}dpi,j,k =dpi,j,k−1 。之后不断迭代就可以求出最后的解。
本题的主要难点是位运算的一些操作，有些同学对位运算的操作不太熟悉，这里提供一些常见的位运算操作：
1. 获取一个数字的第 jjj 位：(x >> j) & 1。
2. 判断数字是否是奇数：x & 1。
3. 将一个数字乘上 2j2^j2j：(1 << j) * x。
本题的时间复杂度约为 Θ(60N)\Theta(60N)Θ(60N)。
因此，本题的 AC 代码如下：
第六题 - SORTING COLOR BALLS
题目跳转：彩球排序。
> 一道逆序对的题目，因为我懒的使用归并排序来做，所以我用了 树状数组 + map 的方式，荣获运行时长 44.9s 的好成绩。其实这道题应该比第五题简单，Based on my opinion。
一道普普通通的逆序对的题目，在计算逆序对的时候去除相同颜色的逆序对就可以了，类似一道模板题。我用了两个树状数组分别来计算每个数字出现的次数和每个颜色出现的次数。
本题的 AC 代码如下，时间复杂度约为 O(Nlog2N)O(N \log_2 N)O(Nlog2 N)：
