当前位置：首页 > news >正文

2025.12 模拟赛日志

news 2026/5/12 4:17:34

2025.12 模拟赛日志

2025.12 模拟赛日志
- 2026省选训练赛1（20251208）
- 2026省选训练赛2（20251209）
- 2026省选训练赛3（20251212）
- 2026省选模拟赛4（20251213）
- 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC 2026）初赛（20251214）
- 2026省选训练赛5（20251215）
- 2026省选训练赛6（20251216）
- 2026省选专题-DP 综合（20251218）
- 2026省选模拟赛7（20251219）
- 2026省选模拟赛8（20251220）
- 2026省选训练赛9（20251222）

2026省选训练赛1（20251208）

[A YetAnotherRobotSimulation] 直接枚举
[B SellingGold] 贪心、背包
[C TheCoins] 下取整有关的数学计算
*[D CityBusiness] 点分树或树剖维护树的路径信息
*[E BitIsland] 区间，dp

训练赛，通过了 A 和 B。D 写点分树被卡常了，不想写树剖了。

2026省选训练赛2（20251209）

[A EvaluatingElections] 数学枚举
[B HeavyBooks] 假的博弈论
[C CircuitDesign] 排列计数，建图
*[D Fast & Furious]
*[E GraphGame]

训练赛，通过了 A、B、C。

2026省选训练赛3（20251212）

*[A 懂树] 神秘的二叉树题，最优化字典序，树形 DP（有点像迷宫守卫）
*[B 双人游戏] 博弈，神秘的博弈转化，二分答案，直接暴搜并剪枝使复杂度正确
*[C 矩阵游戏] 二维矩形题，分类处理，最难的一类需要线段树维护静态凸包

\(0+18+10(100)=28(118)\)。第一题做了好久结果错完了，气死了。第二题什么也不会。第三题漏考虑了一种情况，差点过了。

第三题补题其实已经补了，但是被卡常了。气死了。

2026省选模拟赛4（20251213）

[A 打铁了] KTT（洛谷题目：EI 的第六分块）或分块维护凸包
*[B 拿钱了] 大粪树形 DP
[C 梦里啥都有] 纯粹的容斥和组合计数

\(100+0+100=200\)。第一题写太久了，早知道直接写凸包了，不比李超线段树难写到哪里去。第三题又是 \(0,1,1,0,-1,-1\) 循环序列（该序列 \(F\) 满足 \(F/(1-F)\) 是序列 \(0,1,2,3,4,5,\cdots\)），这个可能要背下来。然后后面都比较普通啊？就是比较恶心。我做出来了，我真牛啊。

第二题写的第一个算法常数过大，第二个代码没调出来。

2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC 2026）初赛（20251214）

[A Asian Soul] 一个虚树题，但是有一点降智导致写的比较久，而且复杂度还是错
[D Unpair Ampere] 我去！网络流最小割！
[G 又一个 01 串问题] 猜结论，贪心、邻项交换
[J 序列] 构造，打表，猜结论

以下问题是经典的并查集问题，由于性质太好了，所以可以均摊分析得到复杂度为 \(O(n+m)\)。

给一个长度为 \(n\) 的 01 序列 \(a_1,\ldots,a_n\)，一开始全是 \(0\)，接下来进行 \(m\) 次操作：

令 \(a_x=1\)；

求 \(a_x,a_{x+1},\ldots,a_n\) 中左数第一个为 \(0\) 的位置。

这是对应的树上问题的版本，同样是 \(O(n+m)\)。

给出一棵 \(n\) 个点的树，接下来有 \(m\) 次操作：

加一条从 \(a_i\) 到 \(b_i\) 的边。

询问两个点 \(u_i\) 和 \(v_i\) 之间是否有至少两条边不相交的路径。

灵活运用这个模型，结合分治的归并排序带来的有序性，可以莫名其妙地降低某些问题的复杂度。它的常数也很小。

另外：该加训网络流了！！！

2026省选训练赛5（20251215）

[A FuzzyLife] 简单诈骗题
[B CalculationCards] 实数 DP，简单期望
[C YetAnotherNim] 线性空间中的线性相关和线性无关（但是和线性基没关系。）
[D AttackAgain] 网格图多次询问点对最长路，分治每次分割矩形的短边
*[E ChristmasTree] ？

训练赛，过了前两题。C 真的不会，就是推出来了线性无关的条件，但是受限于线性基所以没想到可以直接 DP 啊！D 题就是完全不会，补算法。就是转化成网格图最长路，复杂度是 \(O((n+q)\sqrt n)\) 其中 \(n\) 是网格图大小。

E 题从题解第一句话里面学到点东西。两个人博弈，A 拿物品 \(i\) 的得分为 \(a_i\)，B 拿物品 \(i\) 的得分为 \(b_i\)，两边都想最大化自己的得分和减去对方的得分和（如对 A 来说使最大化 \(A-B\)）。这种形式特别常见，其实也没什么好的通法。但是如果 \(a_i\neq b_i\) 的话，可以把权值改一下，先往最终答案里面加 \((a_i+b_i)/2\)，然后权值改为 \((a_i-b_i)/2\)。如果 A 选到，则最终对 \(A-B\) 的贡献是 \(a_i\)；如果 B 选到，则最终对 \(A-B\) 的贡献是 \(b_i\)（B 选物品对 A 来说是负贡献）。这样两个人选物品的权值都是一样的，有时可以简化问题（？）。

2026省选训练赛6（20251216）

[A BallRemoval] 简单的区间 DP
[B LongJourney] 神秘的最短路，要好好设计状态，贪心
[C CowsMooing] 《生命的循环》，同余方程合并与削减
[D StringCover] 神秘的二维矩形覆盖题，只用考虑边界上的位置
[E HaitangAndGraph] 线性空间 DP，划分数 DP（极为经典的问题：给定一张无向图，问往里面继续添加 \(m-m_0\) 条边使它连通的方案数，不允许重边自环）

训练赛，过了前两题。

2026省选专题-DP 综合（20251218）

不太会的题目：

CF1060F Shrinking Tree
CF506E Mr. Kitayuta's Gift

以及还有一堆没写的题。

2026省选模拟赛7（20251219）

[A 有序操作] 01 序列排序题了，结论和 \(\pm1\) 折线有关
[B 树上编号] 树形 DP 压缩状态，Trie 的合并
[C 记忆博物馆之树] 树和 prufer 序列的计数，长链剖分

\(100+100+85=285\)。

2026省选模拟赛8（20251220）

[A 树点购买] 与 P10145 WC2024 线段树一样的转化套路，“对于一个线段树的区间 \([l,r)\)，在 \(l,r\) 之间连一条无向边。那么一个区间 \([L,R)\) 的和能被表示出来当且仅当在图上 \(L,R\) 连通。”后面就都是屎
[B 平凡] 虚树、点边容斥、换根 DP，总之就是一大堆（有交）路径计数问题，十分平凡
[C 随机游走 / QOJ5406] 实数的概率与期望。容斥原理、组合计数、双射转化、函数的积分

\(100+100+0=200\)。