2026.1 模拟赛日志
2026.1 模拟赛日志
- 2026.1 模拟赛日志
- 2026 省选模拟赛 16（20260103）
- 2026 省选模拟赛 17（20260104）
- 2026 省选模拟赛 18（20260105）
- 2026 省选模拟赛 19（20260106）
- GZOI-NOI2026 省选集训（十八）（20260111）
- GZOI-NOI2026 省选集训（十九）（20260111）
- 讲课 1：陈翔乐
- GZOI-NOI2026 省选集训（二十）（20260113）
- 讲课 2：陈奕帆
- GZOI-NOI2026 省选集训（二十一）（20260115）
- GZOI-NOI2026 省选集训（二十二）（20260116）
- 讲课 3：王晶
- GZOI-NOI2026 省选集训（二十三）（20260118）
- GZOI-NOI2026 省选集训（二十四）（20260119）
- GZOI-NOI2026 省选集训（二十五）（20260121）
- GZOI-NOI2026 省选集训（二十六）（20260122）
- GZOI-NOI2026 省选集训（二十七）（20260123）
2026 省选模拟赛 16（20260103）
- [A 榻榻米 / P14680] \(2\times n\) 网格的 \(1\times 2\) 骨牌覆盖问题。直接贪心即可！
- [B 抽奖奖 / P14686] 有点难绷的双射计数，转化为经典容斥问题
- *[C 吃糖糖 / P14681] 精细的刻画和贪心转化，区间凸包查询（线段树分治或猫树分治，使用技巧优化复杂度）
\(100+100+0=200\)。第一题不敢猜能贪心，写了暴力 DP，转移很多，很逆天，最后发现最效率的方法是打表，那确实很效率了。第二题一直不会，部分分也很少，看了两个小时突然就会了（运气这一块）。第三题好难刻画啊，不敢刻画啊，没搞出来什么东西，自闭了。部分分写完了写错了（最后发现是漏了情况）。
2026 省选模拟赛 17（20260104）
- A 月灯 / QOJ14949 回滚莫队大力维护（我写了一个神秘的询问分块）
- [B 卡牌游戏 / QOJ14944] 基于策略的期望计数题。刻画策略（找到必要条件直接证明充要性），期望转概率（对整数 \(x\) 有 \(E[x]=\sum_{i\geq 0}(1-P[x\leq i])\)），根据这个 \(x\leq i\) 的限制倒推原排列限制，组合计数
- [C 图 / QOJ14684] 核心出装：\(A\cap B=\complement_U{\left(\complement_U A\cup \complement_U B\right)}\)，从这个角度出发构造指数级的答案。构造题，前缀和优化建图
\(100+18+8=126\)。第一题搞复杂了，被卡常，还好过了（运气这一块）。其实直接维护也能维护明白，改成前后缀查询就行，是能改的。第三题没找到核心出装，做太久了没啥分，自闭了。第二题没时间做，初步刻画了方案，但是有些系数没调对（应该拿特殊性质的小样例调系数啊啊啊），前两个子任务就没做，感觉有点难绷。
2026 省选模拟赛 18（20260105）
- [A 我要当总理 / QOJ15104] 很少见的那种纯分类讨论硬猜结论的题
- *[B 心景幻成 / QOJ15105] 总和为 \(O(n)\) 的 \(O(n\sqrt n)\) 背包，直接搜决策树
- *[C 花神诞祭 / QOJ15108] 提出贪心策略（倒着贪心），数据结构模拟
没打。
2026 省选模拟赛 19（20260106）
没打。
Welcome to TinyHorizon Online Judge
腾讯会议：547-4249-6014（后续都是这个会议号！）
GZOI-NOI2026 省选集训（十八）（20260111）
- [A 网格图] 图论、特殊图匹配计数
- [B 距离之和] 很神奇的区间 DP，很神奇的状态设计（需要巧妙地拆成三种子问题，有一定的逻辑关系）
- [C 树上操作] 树上 \(K\) 邻域、路径、子树的信息维护，设计 dfn 序（\(q\times K\leq 10^6, K\leq 100\)）。
\(100+0+70=170\)。
第一题一眼就知道要拆操作，然后建成一张无向图，讨论树和基环树的情况（比较经典但不是很简单）。写了一会。
第二题刻画问题花了很多时间，很后面才搞清楚贡献怎么算，浪费很多时间。然后也不会做，我的 DP 状态不太好，后面想了一下应该是会漏很多转移，非常差，而且复杂度也不太好。而且，我只写了一个子问题出来，导致转移很难写（也写不出来）。像题解那样拆成 3 个子问题，一下子就清晰了。
第三题看着就很经典。\(K=1\) 会做，应该是叫作毛毛虫剖分。然后树上到一个点距离不超过 \(K\) 的邻域，这个范围可以拆成 \(2K+1\) 个形如“\(w\) 子树中距离它恰好 \(k\) 步”的范围，这个是很简单推一下就知道的。然后 \(K\) 很大的时候没想清楚，没写。非常艰难的写完 \(K=1\) 然后再拼了两个包获得 \(70\) 分。
第二题太诡异了，没想到好写的思路，想的太复杂太诡异了，所以没做出来，并且在上面浪费了很多时间。
第三题思路总体是对的，但是算法流程还是写不出来，就是所有是重链前 \(K\) 个点的点，是应该以 bfs 序呈现没有错，但是每一层的顺序也是有讲究，不是随便乱搞，不然做不了子树。就是这些点按照 bfs 序排序后，挂到它们的 \(K\) 级祖先上，然后再重链剖分 dfs 序遍历，把挂着的点转成 dfn 序。这样，一个点的子树的前 \(K\) 层可以由它的 \(K\) 个祖先挂的点的某些个区间，再加上另外的 \(O(1)\) 个区间完美刻画。其它的也很自然。如果没读懂这段话什么意思可以看代码。
GZOI-NOI2026 省选集训（十九）（20260111）
- [A 苹果] 一个套路的数论题，莫比乌斯反演
- [B 白 / CF2053I2] 最大子段和；计数问题，然后写成像格路计数的形式，然后暴力 DP，然后优化 DP。
- [C 无题 / TEST_170] TB5 分治（等价类分治）；根号重构、根号分治。
\(100+90(100)+10=200(210)\)。第二题没有特判空长度区间（\(\sum a_i=0\)）挂分，是人类吗？
第一题核心出装 \(\varphi(\text{lcm}(i,j))=\varphi(ij/\gcd(i,j))=\varphi(i)\varphi(j)/\varphi(\gcd(i,j))\)。这个其实考虑每个质数的贡献就发现了，而且不只是 \(\varphi\) 适用，看起来积性函数都是可用的（\(\mu\) 这种函数值有 \(0\) 的就算了；哦，怪不得这题不是任意积性函数）。后面就是直接莫比乌斯反演，使用第一次学习莫反的拆和式技巧直接做就行了。有人说这个莫反的实质是卷一个 \(\mu\)，所以可以直接写成高维差分的形式，不用推那么多式子。具体的内容还没实践。
第二题就是感觉很刻意的题目，猜到第一个结论就可以一条路走到底了，有效部分分 10 分气笑了。竟然是 CF 题。首先就是，你肯定要确定“最小的最大子段和”是多少，很快可以想一个二分、差分约束的做法，这是有一点用但不多的，用处在于它启示了：1. 原数组相邻两个数最多插一个数，头尾再各自插一个数 2. 答案的下界是原数组的总和。忘了怎么猜的，反正突然猜到“最小的最大子段和”就是下界 \(\sum a_i\)。后面就爽了，\(f_{i,s}\) 表示决定了前 \(i\) 个数，当前计算最大子段和的变量 \(s\)。要求 \(s\) 最终是 \(\sum a_i\)，全程不超过 \(\sum a_i\)，然后要有 \(s+val\geq s\) 不然 \(s\) 就不是整个序列的和，非法，也就是 \(s\geq 0\)。那就很清晰了，填入的数加上 \(s\) 范围在 \([0,\sum a_i]\)，可以先写一个暴力转移，获得 10 分。后面就是垃圾，写一个双端队列想怎么维护就怎么维护，最后做到线性。
第三题不会。这里记录一点错误的结论：
现在有一些二元组 \((x,y)\)。每次操作将二元组中所有 \(\leq z\) 的数 \(x\)（或 \(y\)）变为 \(z-x+1\)（或 \(z-y+1\)）。操作完成后问有多少二元组 \(\max(x,y)\leq z\)。
下面介绍这个错误的算法。将二元组数字拆散，全部插入平衡树。每次操作就是分裂，打标记，然后合并。求答案就观察平衡树的大小，我们凑一个合理的系数（二元组 \((x,y)\) 插入平衡树时，\(x\) 给一个 \(p\) 的系数，\(y\) 给一个 \(q\) 的系数，求平衡树大小改成求系数之和）就能把 \(\max(x,y)\leq z\) 算出来了，是不是很爽？那肯定错了，经过一定尝试，我们发现我们无法凑出这样的系数，无论如何确定 \(p,q\)，甚至把 \(p,q\) 改成向量，本质上是因为矩阵不满秩，也就是矩阵里有线性相关的一个组，你把矩阵写出来，设这个线性相关组的系数，很容易就看出来，无论怎么设置，因为本身的对称性导致设出来的系数会被消元到很少数量，随便构造就满足了。（不知道怎么说，懒得把具体过程打出来了）
这里的核心问题是对称性。整个做法有对称性，但是所求的东西没有对称性，导致怎么做也做不出来。
正解复杂度很逆天。根号分治（好吧，其实最后算出来不是根号）是必要的，这个大家都知道：出现次数 \(\leq C\) 的拆成 \(nC\) 个二元组直接考虑，\(>C\) 的就每种颜色自己独立算。然后你进行一些尝试，发现操作太逆天了。最后考虑到操作分块，每 \(B\) 个操作分一块。这会带来什么呢？整个序列会被分成 \(O(B)\) 个块，操作将变成翻转块的前缀，之前的二元组的值域从原来的 \(O(n)\) 缩小到 \(O(B)\)。值域缩小了，原来 \(O(nC)\) 个变成 \(O(B^2)\) 个，并且完成 \(O(B)\) 个操作的复杂度降低为 \(O(B^2)\)（这里还没有解决怎么“分块”的问题）。如果我们适当选取参数，就可以降低复杂度了。
为了更低的复杂度，我们引入 TB5 分治（来自 P7723 Ynoi2007 TB5x - 洛谷）。大概意思是，对于操作给出的范围，我们给原序列的范围划分为若干等价类，每个操作的范围都可以划分为若干个等价类。对操作序列分治，向两边分治，求出两边分治区间各自的等价类集合，然后在这一层把它们并起来，求出当前分治区间的等价类集合（或者用别的方法也行，从上往下做异或哈希之类的）。然后再做第二次分治，进行所有操作，向下分治的时候把等价类合并起来，再撤销。总之可以看别人写的东西。
在这个题上面，由于操作猎奇，所以等价类需要从两个分治子区间合并上来求出。然后就是 \(O(nC)\) 个二元组和 \(O(n/C)\) 种特殊对待的颜色被压缩成 \(O(B)\) 的等价类上，然后被分治下去，等价类被合并，信息就被压缩的更少。复杂度：划分等价类 \(T(k)=2T(k/2)+O(k\log k)=O(k\log^2k)\)，求答案 \(T(k)=2T(k/2)+O(k^2+nk/C)=O(k^2+nk\log k/C)\)（这里就少了一个 \(k\)，复杂度降低了）。平衡得到 \(O(mn^{2/3}\log^{1/3}n)\)。\(O(n/C)\) 种大颜色由于出现次数不超过 \(O(n)\)，故 \(w/\log n\) 个颜色的出现次数可以压缩成一个 \(w\) 位整数进行同时计算，复杂度再乘一个 \(O((\log n/w)^{1/3})\)。然后需要注意常数优化。然后划分等价类好难写啊！
讲课 1：陈翔乐
杂题选讲，一堆题，其中有一堆题不会（尤其是那个二分图匹配的构造题，看不懂）
平面图分割定理：对于一个平面图，存在点集划分方法 \(A,B,C\) 使得 \(A,B\) 之间没有边，\(|C|\leq O(\sqrt n)\)。
猎奇科技：
- 更快的有向无权图的删边最短路
- 更快的狄利克雷卷积
- 更快的区间加区间 kth
差点就会完了！
GZOI-NOI2026 省选集训（二十）（20260113）
- [A 卡牌] 状压 DP、概率与期望；分段一次函数复合，解方程
- [B 最大面积] 平面上的矩形，两维度独立，异或哈希划分等价类
- [C 最后的舞台] 小工程题，暴力优化题，哈希表大作战
\(100+100+25=225\)。
第一题做过了（这谁卖的题，无敌了），很快想起来了，但是调了一会。
第二题出乎意料的简单，发现是独立的之后，异或哈希也是显然的。
第三题，震撼首发。\(O(n^3m^6)\) 显然（\(m\) 是 \(\max(R, C)\)）。使用哈希（\(\sum_{i=0}^{R-1}\sum_{j=0}^{C-1}w_{a_{i,j}}X^iY^j\)，其中 \(w_i, X, Y\) 都是随机数，可以发现这样好一点）和哈希表做到 \(O(n^2m^4)\) 次哈希表。先写了再说。怎么这么难写？这还是信息学竞赛吗。第二个不是很显然的优化就是卡角优化，定义一个图片（即原题的碎片或舞台）的“角”是以横纵坐标分别为两个关键字排序后最靠前的碎片，则舞台的“角”必须和一个碎片的“角”重叠，这样枚举第一个图片就不需要额外枚举位置，优化到 \(O(n^2m^2)\)。能卡一次“角”，那就肯定能卡两次。卡了一个“角”之后，用 \(O(m^2)\) 的代价从舞台里削除这个图片（并找到新的“角”），再 \(O(n)\) 枚举第二个图片进行卡“角”，然后不需要再次削除，直接减哈希值就行了。前面部分复杂度 \(O(n(m^2+n))\)。问题变成 \(nm^2\) 次在至多 \(64n^2\) 大小的哈希表查询：拉链哈希表，模数开到 \(10007\) 能过，不知道为什么；unordered_map 也有人过，也不知道为什么。哈希表大作战这一块。好像存在一种可能，是哈希表前面的部分太慢了，不知道，也懒得验证了，反正已经过了。
C++ 中面向对象的接口设计杂谈 - caijianhong - 博客园
讲课 2：陈奕帆
杂题选讲。《P14463 呼吸之野》这题，不会，听不懂，倒闭
下午：
GZOI-NOI2026 省选集训（二十一）（20260115）
- [A 夜隠染] 概率与期望，拆期望，组合计数，DP 递推方案数
- [B 歩拾道 / QOJ10697] 若无向连通图 \(G\) 有唯一完美匹配 \(M\)，则 \(M\) 中必存在 \(G\) 的割边。边双连通性，切边等价类，bitset 优化图的搜索 \(O(n+m)\to O(n^2/w)\)。
- [C 輪符雨 / P14475] 大鱼吃小鱼模型，区间嵌套分离关系的维护（关于最值的连续段问题），单调栈、双指针，线性魔法
\(100+30+45=175\)。线下榜里的 T2 数据是错的，影响到我了。
第一题做了一个小时，没什么好说，都是基本刻画。
第二题和第三题都好猎奇，预计一下可能做不出来。先写了两个题的暴力。
第二题想了一下，没什么思路。特殊性质想了一下，不太好做，没啥能直接用的。第三题想了一下，由于这个新的限制，导致之前的算法结论失效，没有那么好做。
第三题先做 \(K=0\)。评估了一下，觉得应该直接去想线性做法，不然不仅难写，而且比较唐。突然想到笛卡尔树，那就对了，然后写一下。到这里已经过去了三个小时。\(K>0\) 的部分有点难绷，别告诉我是动态笛卡尔树，应该不是吧。这里发现有个问题是从第一条鱼开始要吃到 \(sum\geq K\) 要一直付费，这个好像不是很好搞（不是哥们？！这个反过来，用区间贡献单点，直接单调队列就行了），遂放弃。
第二题的二分图想了一下，终于给我搞出一个判断完美匹配是否唯一的算法：定向，左部点连到匹配点，右部点连到左部其它点，然后拓扑排序看一下有没有环，就是对的。然后开始写网络流。网络流写 EK 甚至有跑不动的风险，复杂度错了，要么 \(O(n^2/w)\) bfs，要么写 Dinic。bitset 写完了，一测感觉有危险，又回去写 Dinic 了，这是真难绷。应该是能过这个分了。
链的部分分，写了个拆点之后跑拓扑排序的，但是错了，不知道为什么。（有人告诉我是因为重边，这个算法不能保证环上没有重边）然后就结束了，倒闭。
第二题，竟然是边双连通性，惊人啊！单个边双连通分量的完美匹配不唯一。证明好长，还要用切边等价这样的上古科技，还要反证、化归小命题，太难了。怎么会想到猜这个呢？如果前面部分分做的和题解一样，猜这个就可以理解，但如果不一样就倒闭了。然后就是找 \(O(n)\) 次割边拿出来判断，bitset 优化搜索即可。
第三题需要把区间分类，尤其要把一开始要一直付费吃鱼的那部分分离出来，这样才能做。然后就是建区间嵌套分离关系的树，然后写一堆线性算法就能过了。这题还是太好了。原来是上古大神 LCA 出的，这下看懂了。
第三题，这个题是难想，属于那一类性质越多越好写的题。如果看了题解，对着题解写，写的是非常爽，非常好写，不用调的（其实还是要调。不过不是虚空调试，而是有理有据的调试）。但是，在场上，写不写这个题，就是有一点赌的意味：写了，可能想不清楚怎么写，可能写不完，可能调不完（这不太可能）；不写，另一道题可能更难，可能更简单，可能一下子发现了大性质，也可能发现不了然后倒闭。如果是追求严格线性的话，那要证明一些东西（对本题而言就是证明“自闭大鱼区间”只有 \(2n\) 个），证完之后更好写（理解如何证明后，立即就能写出简单的得到所有“自闭大鱼区间”的算法；如果没有，那么会比较自闭，没有简单的算法，也许可以直接二分？不知道）。如果不追求严格线性的话，可以开大运撞过去（应该是有大运做法的，也许可以分治），不过有没有那样好的常数就是另一回事了。总之就是，这里构成一个矛盾：为了通过本题，需要很多的时间和意志；如果想要高分，需要的时间不一定比直接写正解少；如果放弃，那就没有题可以做了。
GZOI-NOI2026 省选集训（二十二）（20260116）
- [A 幻想乡] 树上路径长度和统计，树上数据结构基本技巧（树剖或点分树、虚树）
- [B 异或] P10085 同款的：操作自复合 \(2^k\) 次与自身相似，差异是坐标被放缩 \(2^k\)。以此对网格进行划分，递归子问题
- *[C 贸易路径] 广义串并联图的 Top Tree（也就是串并联树，有簇和界点的概念，深度是线性），在上面点分治
\(100+30+50=180\)。
第一题，开幕雷击，不过好像没那么难。写了一个半小时。我勒个“\(x\) 到路径 \(u, v\) 最近的距离是 \((dis(x, u)+dis(x, v)-dis(u, v))/2\)”大运做法啊。
第二题不会啊。卢卡斯定理搞出来的结论比较难做，问题在奇数上面比较难。观察到了 \(t\) 次操作和 \(2t\) 次操作的相似性。但是也没想到，这玩意竟然可以直接按照坐标奇偶性划分递归子问题？？？我勒个原创题啊，太强了。这个好啊。
请见：二项式系数的素数整除性质的研究 - caijianhong - 博客园
第三题完全不会啊，不知道有向广义串并联图有什么用，写完部分分跑了，最后补了个权值随机的不随机算法（取权值前 \(B\) 大的点计算答案是随机化吗？那我问你）。一看题解，TOPTREES 领先！一看通过代码，各显神通啊，全是乱搞过题，还有人类吗。还好最后伟大的出题人把它们都卡掉了。
有个乱搞的分数特别高，卡不掉。以下是他的做法。对贡献 \(a_xa_y+\sum_{w\in E}w\)，我们选一个 \(K\)，将其近似为 \(a_xK+\sum_{w\in E}w+a_x(a_y-K)\)，怎么近似呢，就是前两项从 \(x\) 出发正常计算（没有 \(y\)），最后一项在 \(y\) 计算，里面的 \(x\) 直接取使前两项和最大的那个 \(x\)，其它的直接不管。事实证明这个近似算法十分强，很难卡（好像最后还是被卡了）。\(K\) 可以取 \(a\) 的前 \(B\) 大的数都跑一遍，或者可以引入随机化，进行模拟退火、爬山等难绷算法，并非人类可及。
该学习静态 Top Tree 了。
讲课 3：王晶
杂题选讲。进一步学习：CF223E、P8959
杂题选讲。严重不会：qoj16210。进一步学习：qoj1357
GZOI-NOI2026 省选集训（二十三）（20260118）
- [A 糖果序列] 异或最小值（只用算相邻项），在上面的 DP，和前缀和优化转移
- *[B 粉丝转粉]
- *[C 逃离孤岛 / P5988]
\(100+0+0=100\)（中途弃赛）。
GZOI-NOI2026 省选集训（二十四）（20260119）
- *[A 矩阵]
- *[B 猪 / P14681]
- *[C 树 / AGC052F]
没打。不是哥们你怎么把前面讲课的题目搬过来了。
GZOI-NOI2026 省选集训（二十五）（20260121）
- [A 最佳位置] 模拟？二进制、二分
- [B 遗忘记忆] 拟阵交
- [C 商贸往来 / QOJ2068, AT_xmascon22_f] 匹配计数，集合幂级数，状压 DP
\(100+40+65=205\)。谁的题，出来受死啊。
第一题，非标准解法。连续三场参加的模拟赛的第一题都不是标准解法（意思是：复杂度可能略高或一样，但做法完全不同，但可以通过）。我怎么这么无敌？
第二题写完随机化就跑了。后来想了一下感觉好像可以直接增加答案，跑一个像网络流的增广路，跑出来就好了，不知道对不对（其实是对的。你妈）。不过因为第三题有个多的 25 分，决定写第三题。
第三题前 40 分比较送，直接写就行了。然后，不会啊。想到一个把序列分成前 \(n-6\) 个和后 \(6\) 个的暴力，写了一下，能过到 \(n=30\)（最后评测过了 \(n=31\)）。
然后比赛就结束了。第一题写了两个小时。然后想了一个小时的题目，第二题不会做，第三题写写暴力。第二题写写随机化，发现能过所有大样例。这个时候感觉有过第二题的可能，加上第三题有分能写，所以就算是第二题有一个可能的算法我也弃了，没时间了。然后写了第三题剩下的。然后就结束了。
第二题，拟阵，交。你妈。
第三题，陈昕阳在 APIO2025 讲过。但是我好像没有印象了，我不是听了那节课吗？哦哦哦哦哦哦哦哦哦哦哦。
奇异递归模版模式（CRTP） - caijianhong - 博客园
GZOI-NOI2026 省选集训（二十六）（20260122）
- [A 异或] 异或最小值，爆搜
- [B 字符串] AC 自动机上走路，根据结构优化状态数
- [C 桥 / P4499] 无向图连通性，边双连通性，启发式合并
\(100+100+10=210\)。第二题的复杂度是错的，侥幸过了。
第一题卡了好久啊，其实直接暴搜就对了，复杂度和线段树合并一样分析，和点数成线性。
第二题卡了好久啊，感觉好神奇，直接在 AC 自动机上走路，把两边的点都记在状态里就行，回文的条件直接当减速带了。
GZOI-NOI2026 省选集训（二十七）（20260123）
- A 供音树 / QOJ8692 max 转化为二分计数，gcd
- [B 好树] 哈夫曼树模型，背包 dp，凸优化和闵可夫斯基和
- *[C 殊途同归] 交互、随机化、划分等价类
\(100+28+10=138\)。
本文来自博客园，作者：caijianhong，转载请注明原文链接：https://chuna2.787528.xyz/caijianhong/p/19469202/contests-in-202601
浙公网安备 33010602011771号