时间安排
7:25 - 7:40
看题，发现一点都不会。
7:40 - 7:50
A 题随便胡了个贪心，过不了大样例。
7:50 - 8:30
想到了 A 正确的贪心，但是脑瘫了，求一个数右边第一个小于它的数竟然只能想到线段树二分，而且还要先把区间拆下来，我不认为自己能够在很快时间内一遍写对，而且时限 0.5s 怕卡常，就写了个 60 分的暴力。
8:30 - 9:40
想了想后三题，B 题只会 15 分，C 题大概知道怎么构造，但是我赛时肯定写不完，D 题只会 \(m=n\)。突然会了 A 题 100 分，只需要单调栈 + ST 表。
9:40 - 10:05
过了 A 题大样例。
10:05 - 11:50
写了 B 题 15 分，C 题 25 分，D 题 15 分。罚坐。
总结反思
-
B 和 D 实际上都在我的能力范围之内，赛时的时候不敢想也不敢写，怕像之前一样浪费太多时间，但实际上什么也不写反而导致一直罚坐。
-
一边写对的能力不足，C 题这种即使赛时想到也一定调不出来。
题解
A.至少分几段
考虑贪心，段的右端点必定左端点右边第一个小于它的数的左边的最大值所在的位置。然后随便用单调栈或者数据结构维护一下。
B.交换消消乐
先找到相同数字的一对 \((l,r)\)，考虑如果有相同的另一对在里面，那么可以优先处理里面那一对；如果有相同的一对都在外面，那么对于当前这一对的操作次数并没有影响。那么问题就转换成了对于每一对相同的 \((l,r)\) ，查询区间里面只出现过一次的数的个数，然后相加。用树状数组维护即可。
C.超级一笔画
构造题。可以用分治解决。AT 官方题解
D.生成连通图
计数题目。
设 \(f_{i,j,k}\) 表示走了 \(i\) 步，扩展了 \(j\) 个点，\(1\) 所在的强联通子图有 \(k\) 个节点的方案数。
- 终点属于未拓展的点
- 终点在不包含 1 的强连通里
- 终点在包含 1 的强连通里
\[f_{i+1,j+1,k}+=f_{i,j,k} \times (n-j)
\]
\[f_{i+1,j,k}+=f_{i,j,k} \times (j-k)
\]
\[f_{i+1,j,k+1}+=f_{i,j,k} \times k
\]