2026.2 模拟赛日志

2026.2 模拟赛日志

目录

• 2026.2 模拟赛日志
  • 2026省选模拟赛35（20260202）
  • 2026省选模拟赛36（20260203）

2026省选模拟赛35（20260202）

• [A 百奇] 线性筛积性函数
• [B 基础图论练习题 / QOJ5407] 竞赛图的兰道定理
• [C 简易编辑器 / P5599] AC 自动机，线段树维护循环节

\(100+60+31=191\)。

第一题比较套路，就是算数题。第二题忘了竞赛图这个著名定理兰道定理了，写出了 \(O(n^3)\) 找竞赛图哈密顿回路（就是删点跑 Tarjan 并分治；该问题最优可以做到 \(O(n^2)\)），做的比较久，感觉太难了。第三题做的时候没什么时间了，写完几个暴力分就跑了，也没想（感觉想不动了，虽然很简单但就是想不到啊？什么梗）。

一个固定串的无限循环的子串，可以直接考虑维护循环长度和起始位置（\(s^{\infty}\) 的 \([st, st+len)\) 区间），容易进行分裂。如果长度固定，线段树就可以维护了。<- 对啊，就这么简洁，怎么什么都想不到。还想说是不是分块题的，看来就是做第二题做太累了。还没做出来。

• 竞赛图的性质 - 洛谷保存站 这个写的很简洁，记得看
• 浅学竞赛图 - 洛谷专栏

兰道定理：对于一个从小到大排序后的出度序列 \(s_{1\ldots n}\)，它是合法的（存在一个竞赛图出度满足这个序列），当且仅当：

\[\forall 1\le k\le n,\sum_{i=1}^k s_i\ge \binom{k}{2} \]

且在 \(k=n\) 时取等。注意到把以上结论中的出度换成入度也是对的。

2026省选模拟赛36（20260203）

• [A 最大公约数] 最大公约数、线段树二分
• [B 读文章 / P7879] 矩阵刻画 DP、线段树、后缀自动机或哈希
• [C 直径的最大值 / CF1987G2] 笛卡尔树上 DP，设计 DP 状态

\(100+100+20=220\)。第一题很简单很套路。第二题出题人肯定是有反社会倾向，反正卡了一下之后就会了，好傻逼的题目，简直是工业垃圾（不过看了一下，是 2021 年的题目。罪降一等），这里懒得说了。第三题怎么这么难，不会。

第三题就是要设计一个合适的 DP 状态然后就行了，任何刻画的手法如果没有转化成 DP 状态都是无效的，这就比较难了。咕咕嘎嘎。