2026.9.20反思

第一题先想到了dp，设 $dp_{i,j}$ 表示前 $i$ 个数， 当前最右端的块的左端点是 $j$ 时最多分为几块。然后先写了 $O(n^3)$ 的暴力，但是WA了，然后写了暴力对拍但是没拍出来。

然后决定先看第二题，先写了一个 $O(nq)$ 暴力，然后注意到设 $la_i$ 表示每一个积木匹配的前一个积木是哪个，然后就直接转化为二位偏序，用主席树维护。具体可以看我的题解https://oirush.cn/p/lg14598/solution

然后回去看第 1 题，发现没开long long，开了之后统计了一下后缀最大值并加了个二分优化到 $O(n^2\log n)$ 就过了。

然后就想第 3 题，想到了对于每个点在方向确定后下一个点也是确定的，但后面的部分就没有想到了，所以只写了暴力。

第 4 题也看了，但是看着很不可做，是类似欧拉回路的东西所以没做。

在本次比赛中，我在第 1 题浪费了很多时间来找bug，但实际问题是在输出时也要开long long，所以之后在写完程序后一定要自己造一组很大的数据，防止自己忘开long long。

9.21反思

第一题看数据范围 $n \le 5000$ 想到区间dp，但是不太好写，于是考虑二分，判断前 $v$ 个是否合法就使用区间dp判断，设 $dp_{i,j}$ 表示区间 $[i,j]$ 还剩前 $dp_{i,j}$ 个询问没有满足，最后看是否存在 $dp_{i,j}=0$ 即可。

但是卡了很久常，最后突然发现 $q\le n$，把二分边界范围调小了点就卡过了。

然后看了眼二三题，感觉第三题好写点，所以想了一下第三题，原本树剖 $O(n\log^2 n)$ 肯定会超时，所以就打了个LCT就过了。

接着回去看第二题，想矩阵状态如何构造，比如看每个部分是哪个颜色的概率，但是会算错，所以放弃了。

中间看了眼第四题，但由于没读懂题所以回去想第二题了。

想了挺久第二题发现还是不会，所以又去看第四题了，然后发现之前读错题了。

那第四题的解法就很显然了，由于 $c\le20$，所以直接线段树维护矩阵乘法，但是写完后发现空间过不去，然后就开始卡空间，把矩阵开成short，线段树只递归到 $r-l\ge2$，减少节点数量，然后就卡过了。

赛后发现自己过的三题在洛谷都过不了？

9.22反思

先看第一题，很快想到每一位可能存在竖式中的 4 种情况，然后设 $p_i,q_i$ 分别表示是否需要进位，然后从高到低遍历每一位，记录当前为止可以作为开头的位的数量和前一位是否需要进位即可，时间复杂度 $O(n)$，10min写完。

然后看第二题，递减的情况就是一个 $k$ 路归并问题，开个堆就可以解决，主要是递增的的情况。考虑贪心，对于递增的情况，如果取了一个堆那么就要尽量全部取完，就是不存在取两个不完整的堆。考虑证明，设当前已经取的完整堆中堆低最小的是 $a$，取的唯一一个一个不完整的堆的下一个元素是 $b$，假如把 $a$ 换成 $b$ 更优，则有 $a<b$，那我问你，既然 $a<b$ 了，我为什么不把这个不完整的堆取完？

看第三题，显然需要倒序处理，想到每次选择一个只存在于一个连通块的颜色，然后将和其相邻的相同颜色的块合并，写了挺久，但是Wa了，hack是相同颜色的两点中间隔一堆不同颜色的点。

又想了另一种解法，假如有两种颜色，堵上任意一种，另一种就无法联通，但也被hack了，就是很多种颜色互相堵住。

最后知道T3正解要合并已经处理的颜色。

9.23反思

先看第一题，显然要先以1为起点跑bfs求出最短路，把花田按到 1 的距离从小到大排序，即为最短路遍历的花田顺序，然后把最短路的边抽出来，是个 DAG，然后用拓扑排序求出对于每一个点从1出发按最短路走到这个点可以经过的最大花田数量，最后以可以到达的终点作为起点跑多源 bfs，所有经过的点就是可以作为花田的点。

交上去61分，调了一会儿发现是选多源bfs起点是没有判断那个到达那个终点时是否可以经过全部花田，改了之后就过了。

然后看第二题，想了一下先猜测是最长下降子序列数量不超过 2，但是可以被hack，然后就没什么思路了，去看了眼 T3T4，感觉不太可做，于是又回来想 T2，然后就开始暴力分讨，用来2.5h才过（具体可以看我的T2题解）。

做完T2后看T3，转化了一下题意之后就想到了 $O(n^2)$ 的暴力dp，设 $dp_i$ 表示以 $i$ 为根的子树中拓扑序的方案数，然后对于每一个节点都跑一遍。不久就想到了换根dp，每次换根乘个逆元即可，20min就写完了，用时最短的题。