总结

今天是腊月初三咯，上 whk 的同学腊月初七就要期末考试咯。今天是模拟赛，D1D2 都很简单。所以改起来很方便。100+100+37，第三题写挂了，因为一个比较傻的错误。我这是低级错误！ 我们绝对不能多次犯同样的 低级错误！要好好反思。

题解

题解的话很好很好。都比较好说，就好好说一下。

A. 第K大

就是有个集合，区间操作，每次向一段区间插入一种颜色，然后查询一段区间内的第小颜色。

。

用线段树 + bitset 乱搞能过。注意查找第个 1 的话，可以使用二分（像倍增求 lca 那种样子），就是不断右移，然后最后记录一共右移了多少就行。这样的话是的，暴力跳的话找到这一位的时间复杂度是的，可能会超时要卡常，但是看到同机房有人用标记永久化搞过去了？（这是什么）。其实手写 bitset 查询可以优化到的，但是看到前面线段树已经带了，就不愿意手写了。

题解有一个的做法，看了一下，感觉……不如我 bitset。

B. 划分串

题意是给定整数，对于一个串，如果存在一个切分，使得与的最大公共前缀长度大于等于，那么称是的精准切分。如果至少有个精准切分，那么称是一个切分串。给定，问有多少长度为的切分串。

挺有趣的题目。枚举前位然后考虑后位就行。这道题我有一点抽象，我用了 dp + 容斥 + 二项式反演做的，就记录选择个位置匹配的有多少种。但是直接用类似 KMP dp 的方法就可以了，就维数比我多一维，但是复杂度都是。（这里就把和看成同阶吧，差不多）。补充，其实我也用了第三维，记录这个开头匹不匹配，貌似可以省掉这一维的，直接转移开头，貌似需要前缀和优化（好像更麻烦了），我这个样子就是一位一位转移。反正我没有卡常，同机房有人正解被卡常了，不知道怎么写的。

看到讨论区有人很不喜欢这个复杂度上界，发现可以把 border 相同的归类，似乎只有最多 10 种？我一会验证一下。是的，的时候 border 的位置集合确实只有个，改了之后速度改善显著。

C. 降落伞环

还是原题。P6165 [IOI2012] rings 。考的是对特殊图的性质的掌握与分析能力。

就是动态加边，然后动态询问你满足删去这个点后剩下的是一堆链或点的点的个数，没有重边与自环。很容易发现一些喵喵性质。就是最后度数都不大于 2。因此如果没有点度数大于 3，度数为 3 的点最多 4 个，如果有点度数大于 3，那么至多一个。所以发现点数很少，很容易维护。（虽然我写得依托答辩）。然后考虑如果出现环了怎么办。考场上最开始没有想出来，考虑暴力验证这几个可能点，就是枚举当前没有连到这个点的边，然后并查集维护。写完这个之后我发现欸这个并查集好像可以动态来维护，就对这些可能点都开个并查集，然后每次加边看有没有环就行。然后考虑所有点度数都小于等于 2，那么就是没有环都可以选，有环最多一个，这个环的大小，也可以用并查集维护。

这道题我当时 WA 主要是因为下面这个错误。考虑到有一个度数大于的点出现了，那么以后出现的度数为的点一定要连向这个点对吧。然后我就开心地判断了一下新加的边的另一个端点是否为这个大于的点，于是开心地挂了……完全忽略了之前已经连向这个度数大于的点的情况。我把这个补全就 A 了，伤心(T_T)。

D. 螺旋

也是很巧妙的一道题，不难，但是我觉得我自己想的话也是有一点难度的，对于我来说，我考场上可能更有可能想出 std 的那种方法，但是也积累到了一种新的方式。

就是给定一串长度的序列。每次询问一个区间，求这个区间内最长的满足左右端点相等且中间都小于等于端点的子区间的长度。

题解是离线分块做，是因为所有颜色可以分成很多链，然后就可以根号分治，结果比我预处理 +询问快？分块很好想，后面这种就是每次找到区间内最大值，分为很多段，把最大值的处理了，然后头尾两段，就先维护一个点往左往右最大区间，然后这里两边询问就行。可以使用 st 表。这是个很棒的 小技巧，就是把一个区间内最大值拿出来，然后考虑脑袋和尾巴，就很方便了。

后记

不能犯 低级错误！今天的题目虽然很简单，但是还是有值得学习的地方，自己也有不足之处，比如说在思考第三题时逻辑并没有理清，缺乏严密的思考，所以代码写起来也很丑，还很累。切记不可骄傲自满，要保持自己的成绩，积极进取，奋发上进。