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）
登录 - NFLSOJ
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\)。
2026省选训练赛9（20251222）
- [A CrossingTheRiver] 枚举、模拟
- [B SequenceTransmission] 数位 DP
- [C RandomWalkOnTree] 树的直径，分讨，减法原理（？）
- [D StringOption / P6700] 基环树森林，贪心，状压 DP
- *[E Haitang and XOR Mex / QOJ9929, QOJ9516]
训练赛，过了前三题。