队友还是我，ppip，阿毛。

后半场全靠 ppip 和阿毛。

11 题。

D

不难注意到若 $r_a-l_a+1 \geq 10$ 或 $r_b-l_b+1 \geq 10$ 则答案一定为九，其他情况暴力即可。

开场我切了这个题。

I

阿毛做的，我不知道。

A

不难注意到如果有三个连续的同类型括号，或者是两个以上的同括号连续段，则答案是 No。否则是 Yes。

G

不难注意到 $i$ 和 $n-i+1$ 列是绑定的。

如果这两列 1 的个数大于二，那么任何方案都不行。

否则，如果两列只有一个 1，那随便怎么反转都行。

否则，如果 2 个 1 都集中一列，那么其中必定有一个要被反转过去。

否则，那就是 2 个 1 分散在两列，那么要么都被反转了，要么都不反转。

以上的分讨会产生一些关于一行反转或不翻转的条件。

我们建立一个并查集，$[1,n]$ 的点代表 $i$ 选，$[n+1,2n]$ 的点代表 $i$ 不选，那么我们就可以将这些条件转换为并查集连边，答案是 $2^{连通块数量/2}$。

K

不难 ai-=i，连续转换为全部相同。

我们二分答案，转化为对于一个 $l$ 判定是否能让答案 $\geq l$。

套路化地，我们先思考对于单个区间怎么算需要的次数，利用货仓选址的结论得出每个数都要变成中位数。

那好，我们滑动选定的区间，用对顶堆的技巧来动态维护中位数即可。

M

计算几何，阿毛写的，深深感受到了阿毛的强大。

E

ppip 写的，网络流，深深感受到了 ppip 的强大。

B

传统的做法是根号分治，这也是题解的做法。

ppip 直接把标爆了。

我听他的做法听的云里雾里的，所以我复制一下他的题解链接。

https://www.luogu.com.cn/article/eqqje3tf

H

基本子串结构（题目名字）？哈希！

阿毛做的，具体的做法我不会。

C

这个题有点抽象，ppip 切了。

不难发现无向图是幌子，最优解全是树。

然后注意到无标号无根树很少，因此枚举这些树然后打表即可。

这点是我注意到的，然后我不会枚举无根树，所以摆烂，交给 ppip 了。

L

$n,m$ 同阶。

这个题我也贡献了一点东西。

首先我们设 $f(i,j)$ 表示前 $i$ 个线段中染色了 $j$ 条，且 $i$ 染色了的方案数。$g(i,j)$ 表示前 $i$ 个线段中染色了 $j$ 条，且 $i$ 没染色的方案数。

那么我们不难有 dp：

$$f(i,j)=\max(g(k,j-(i-k))+w(k,i))$$

$$g(i,j)=\max(f(i-1,j),g(i-1,j))$$

做到了 $O(n^3)$。

注意到 $k-[j-(i-k)]=i-j$，因此只有 $i-j$ 相同的状态才互相有贡献。

那么我们很不难使用一些数据结构来维护。

我们需要支持序列追加，前缀加正数，求全局最大值。很不难用线段树解决，至此已经有了一个 $O(n^2 \log n)$ 的做法。

紧接着，注意到因为是前缀加正数所以如果有 $f_p>f_{p+1}$，那么 $p+1$ 就可以直接被抛弃，有点类似于单调栈。每次只要选最后一个没被抛弃的点转移即可。

思路全部是 ppip 给的，我也仅仅是思考到了 $O(n^2 \log n)$ 的做法然后给阿毛讲了一下，在 ppip 给我讲完思路以后，实现了一下代码而已。

贡献表就不放了。

总结一下这次：签到我是签的飞速，但是碰到难题就不会做了，比如说 L，虽然是一个高档题，但是每一步的思考都是经典的。

B 的根号做法，在想到根号分治以后也只是一个比较典的树形 dp，但是我脑子不好想不出来。

H 我还没怎么看但是计算每一步对于那些答案产生影响这一个关键做法我也没有注意到。

反正是我太菜了导致的。