![2024年1月13日模拟赛](/img/20240113193103.webp)
2024年1月13日模拟赛
![](https://picx.zhimg.com/v2-9e83e1fd23eccdb98450679841a3a4bc_xll.jpg)
总结
今天是腊月初三咯,上 whk 的同学腊月初七就要期末考试咯。今天是模拟赛,D1D2 都很简单。所以改起来很方便。100+100+37,第三题写挂了,因为一个比较傻的错误。我这是低级错误! 我们绝对不能多次犯同样的 低级错误!要好好反思。
题解
题解的话很好很好。都比较好说,就好好说一下。
A. 第K大
就是有
用线段树 + bitset 乱搞能过。注意查找第
题解有一个
B. 划分串
题意是给定整数
挺有趣的题目。枚举前
看到讨论区有人很不喜欢这个复杂度上界,发现可以把 border 相同的归类,似乎只有最多 10 种?我一会验证一下。是的,
C. 降落伞环
还是原题。P6165 [IOI2012] rings 。考的是对特殊图的性质的掌握与分析能力。
就是动态加边,然后动态询问你满足删去这个点后剩下的是一堆链或点的点的个数,没有重边与自环。很容易发现一些喵喵性质。就是最后度数都不大于 2。因此如果没有点度数大于 3,度数为 3 的点最多 4 个,如果有点度数大于 3,那么至多一个。所以发现点数很少,很容易维护。(虽然我写得依托答辩)。然后考虑如果出现环了怎么办。考场上最开始没有想出来,考虑暴力验证这几个可能点,就是枚举当前没有连到这个点的边,然后并查集维护。写完这个之后我发现欸这个并查集好像可以动态来维护,就对这些可能点都开个并查集,然后每次加边看有没有环就行。然后考虑所有点度数都小于等于 2,那么就是没有环都可以选,有环最多一个,这个环的大小,也可以用并查集维护。
这道题我当时 WA 主要是因为下面这个错误。考虑到有一个度数大于
D. 螺旋
也是很巧妙的一道题,不难,但是我觉得我自己想的话也是有一点难度的,对于我来说,我考场上可能更有可能想出 std 的那种方法,但是也积累到了一种新的方式。
就是给定一串长度
题解是离线分块做,是因为所有颜色可以分成很多链,然后就可以根号分治,
后记
不能犯 低级错误!今天的题目虽然很简单,但是还是有值得学习的地方,自己也有不足之处,比如说在思考第三题时逻辑并没有理清,缺乏严密的思考,所以代码写起来也很丑,还很累。切记不可骄傲自满,要保持自己的成绩,积极进取,奋发上进。
- 标题: 2024年1月13日模拟赛
- 作者: 混氏新子
- 创建于 : 2024-01-13 17:52:58
- 更新于 : 2024-01-13 19:32:42
- 链接: https://blog.huasushis.cn/2024/2024年1月13日模拟赛/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。