2025.12 模拟赛日志

2025.12 模拟赛日志

目录

登录 - 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] Trie 树上的动态 DP 的维护，均摊决策数，拆成历史和线段树

训练赛，过了前三题。

2026省选训练赛10（20251223）

  • [A CucumberWatering] 属于那种不是很简单但是又很容易的高复杂度 DP
  • [B StRings] 维护一堆链
  • [C EvenPaths] DAG 路径条数，但其实是暴力题，meet in the middle，FWT
  • [D HaitangAndRanking / QOJ9936] 高维偏序，线段树分治，的有关技巧（见下）
  • [E HaitangAndWater / QOJ9935] 神秘的期望 DP，线段树优化

训练赛，过了前三题，第五题做过。第三题是暴力过了，蠢了，直接倒着做，复杂度就是对的了，不知道在干什么。

海棠题的出题人讲题（这都公开？）：【出题人讲题】2024牛客多校第八场_哔哩哔哩_bilibili

QOJ9936 Haitang And Ranking 这个题说一下：这题有三个排列 \(a_i,b_i,c_i\)，然后不断修改 \(c\) 并询问是否存在 \(a_i<a_j,b_i<b_j,c_i>c_j\)。这是四维的问题，我们先把比较难绷的时间维用线段树分治删掉，这样就是动态三维偏序存在性，也就是动态二维数点（树套树或分块）。

优化方法在线段树分治上。我们原来会有动态三维偏序存在性，是因为我们是沿着线段树分治结构一直递归遍历整棵树，每次遍历到一个线段上就会把这个线段上的点加入到一个结构里面，同时进行查询，遍历完线段后再撤销操作。（线段指的都是线段树分治结构上的点）

由于存在性是只要有一个就行，换句话说点对之间是互不影响、互相独立的，发现一对点炸了就行。考虑改成：遍历到线段时，提取线段的子树里（不包括它自己；它自己的点对自己处理）的所有点，转而查询这些点和线段上的点之间构不构成偏序，这样就变成静态三维偏序存在性，也就是静态二维数点（排序后树状数组），这就少一个 \(\log n\) 了。有一些细节，就是提取子树内的点时要去重，去重之后只有 \(O(len_{\text{线段}})\) 个点要处理，这是因为这些点当初被插入线段树时的区间都和这个线段有交但不是包含它，意味着这个区间有一个端点在线段里面，那就是和线段的长度成正比的数量了。静态三维偏序存在性一共需要处理 \(O(n\log n)\) 个点，复杂度 \(O(n\log^2n)\)（假设 \(n,q\) 同阶）。

2026省选模拟赛11（20251226）

  • [A 盘王节] 贪心、暴力双指针
  • [B 感染的电脑] 组合意义天地灭，代数推导保平安。反正就是写一个 DP 发现组合意义或者用生成函数刻画这个 DP。
  • *[C 树上两个团 / P5399 Ynoi2018 駄作] Top Cluster 树分块（树的簇），分类讨论计算

\(100+76+25=201\)。大家记住了，一个形式幂级数卷积一个 \(\exp(x)=\sum_{i\geq 0}x^i/i!\) 是只能 FFT 的，没有救。这个和卷积 \(1/(1-x)\) 不一样，这是前缀和，但是它的 EGF 版本是救不了的。

\[\sum_{j\geq 0}[x^j]F(x)G(x)^j=F(G(x)) \]

2026省选模拟赛12（20251227）

没打。第三题：QOJ11549 Inverse Knapsack

2026省选训练赛13（20251229）

没打。

2026省选训练赛14（20251230）

  • [A ScoringSystems] 随机哈希背包
  • [B Block3Checkers] 一种很像平面图最小割转对偶图最短路的东西
  • [C Calculate the Expression] 有点难写的线段树直接维护一坨矩阵和表达式信息
  • [D Deceleration] 有点神奇的转化和线段树二分
  • *[E DestroyThreeRoads / P9105] 边四连通（题外话：有人告诉我边三连通分量缩完之后是仙人掌）

训练赛，过了 A 和 C。

2026省选训练赛15（20251231）

  • [A TheFourSquares] 神秘的小计数
  • [B JumpingOnTheGrid] 在中间相遇，简单的 bfs 最短路
  • [C Rock Paper Scissors] 造一个确定性有限自动机并在上面走路
  • [D SemiMultiple] 取模循环，划分等价类，取模循环背包的退背包（线段树分治或一个神奇方法）
  • [E FieldGrid / P13351] 寻找类似支配对的东西（扫描线 + set），转化为二位数点

训练赛，过了 A、C、D。B 题有个 \(m\) 写成 \(n\) 了，没看出来。

循环背包回退是可以实现的：当 \(m\) 为奇数时，每个环长都是奇数，系数是线性无关的；当 \(m\) 为偶数时，如果 \(x\) 的末尾是 \(1\)，直接背包处理，否则递归到 \((n−1,m/2)\) 继续，总复杂度 \(m^2+(m/2)^2+(m/4)^2+⋯=O(m^2)\)。

posted @ 2025-12-23 14:35  caijianhong  阅读(176)  评论(0)    收藏  举报