- 2026暑假训练补题记录
2026暑假训练补题记录
牛客多校（一）
A. 模拟题，签到（700）
E. 数学题，求贡献度（900）
F. 数学+构造题，找规律（1500）
推式子不算难，但是在赛时不太容易想到。相比之下打表找规律更快
G. 计算几何题，Checker Hack题（1700）
第一次做这种题，完全出题人恶趣味，当长见识了，算是考察对于数据量和范围的敏感度吧
J. 模拟题，超级无敌大模拟（2200）
写了将近五百行，代码能力下降就得多写大模拟
C. 数据结构题，带权并查集（2300）
数据结构题真需要多见多练，既考察数据结构科技，又考察算法逻辑，还考察代码实现能力
H. 动态规划题，超多重状态转移DP + Minimax博弈 （2600）
感觉到了第五题往后就很吃算法功底。状态转移题要多写，这个感觉是能练熟的
杭电多校（一）
A. 贪心题，分类讨论（如签到）（800）
这一场总体难度就挺高的，这题严谨分类讨论有一定思维量，但是可以无脑对比所有情况，因此代码还算好写
F. 数学题，求概率 + 求贡献度（1200）
在求这种连续段相关问题的时候，要想到从边缘变化点切入。这题推式子有点过于电波了，挺难的
J. 博弈题，模拟 + 打表 + 找规律（1600）
这道题给我的启发就是，博弈题应该多模拟一下状态转移的过程，稍微多列几个回合的草稿就能找到规律
E. 模拟题，阅读理解 + KMP思想（1400）
这道题思维量不算大，但是这种给伪代码的题目非常长，需要很细心去模拟这个过程
D. 树论题，树上并查集+优先队列（1800）
其实这道题的题解我虽然看懂了，但是我无法get到那种思考方式，估计是因为树论结合数据结构的题做的太少了
I. 数学题，多项式乘法（卷积）+ NTT数论变换 + 斯特林数（下降幂）（3100）
这道题是不小心看错了补的，花了我两天时间，是个意外。但是学习到了很多数学（数论）知识
H. 动态规划题，二维DP + 字符串哈希 + 二分查找 + 树状数组（线段树）（2300）
卡常题，补题补了一万年，通过这题学了挺多算法和数据结构，但还是得吐槽一下杭电比牛客真的恶心太多
牛客多校（二）
M. 数学题，签到（900）
N. 思维题，前缀和（1600）
B. 数学题，位运算 + 线性基（1900）
异或王国一直是我的弱势领域，写位运算的题一定要考虑到位之间独立的特性，去对单个数位01画分支图
tip: a+b = a^b + (a&b)<<1, 按位异或相当于无进位加法，按位与相当于进位
G. 数学题， 分治 + 素数性质 + 容斥原理 + 动态规划（2500）
在做数学题的时候经常想当然，常常缺乏严密的推导。另外，容斥原理虽然很难写，但是还是要去攻克
tip: 在1e7范围内，素数间距最大为158，任意数的质因子数量最大为8
L. 动态规划题，拓扑排序 + 状压DP（2300）
图论题有两大难点，如何想到建图，如何用动态规划优化算法
杭电多校（二）
K. 动态规划题，一维DP（神人签到）（1700）
想不到，根本想不到，感觉动态规划题还是练少了，没完全开智
H. 树论+构造题，树的直径（1600）
这题赛时队友想的构造，我只负责代码实现，看来这场我打的很迷糊啊，前两题单凭我自己可能都开不出来
J. 贪心题，优先队列（1700）
一开始就陷进二分的漩涡中，只能说还是太缺乏正确的贪心思维了
D. 模拟题，优先队列（1700）
神秘三重队列题，一个queue数组，一个pending堆，一个waiting堆
G. 数论+树论题，DFS序 + ST表倍增 + 容斥原理（2200）
woc补这题补了一个星期，一开始以为又要虚树又要启发式合并又要莫比乌斯反演的，结果一个都不需要
牛客多校（三）
K. 计算几何题，签到（800）
L. 思维题，博弈论 + 优先队列（1400）
A. 思维题，位运算 + 状态维护（1900）
无语了赛后补完了过一阵子再看还是不会。依旧强调：1.位运算关注位的独立性；2.连续段考虑边缘差分
杭电多校（三）
C. 动态规划题，背包DP（构石签到）（1500）
数据造的依托，我之前用最长不递减子序列也能AC。暑假的杭电真的是拉完了
E. 数学题，分解质因数（1500）
这道题其实有点小trick，赛时队友用了黑科技过的
tip: 在对1e18分解质因数的时候，可以先求出1e6范围内的质因数，如果还有质因数只可能是p/(p)^2/p1*p2
J. 数学题，概率论（1600)
这道题邪修过的，我总不可能去学什么鞅的时停定理。邪修的一些小巧思是有必要的
tip: 从[1,n]不断抽取一个数，直到抽中x为止需要的期望次数为n。可以用几何分布的递推公式证明
如果一个事件在任意时刻发生的概率是 p，哪怕各个时刻之间存在复杂的重叠和相关性，但在“对所有情况求平均”的宏观大面上，它第一次发生所需要的期望“尝试次数”往往可以直接拍脑袋当作 1/p
牛客多校(四)
I. 字符串题，签到（1500）
补题的时候debug半天，感觉有时候对于细节处理过于依赖ai了，导致丧失了自主debug的能力
B. 数学题，构造 + 同余定理（1400）
这道题证明了我数学和思维能力真的很差，只能说考虑同余定理的时候，多考虑不同的方程写法，能发散思路
D. 博弈题，贪心 + 模拟（1600）
博弈题的种类太多了，不可能全部学完，要学会通过模拟去推演游戏流程
杭电多校（四）
K. 思维题，签到（1200）
最近是不是状态不好啊…这道题赛时出的，但是补题的时候突然卡壳了…
G. 数学题，并查集 + 裴蜀定理（1500）
感觉自己的数学能力不如队友…推式子的时候可以把所有等式或不等式列出来多找找联系吧，只能多练了…
J. 动态规划题，随机化哈希（2100）
杭电的数据造的真的弱。之后可能不怎么补杭电了。1e6的数据让我用n2的二维DP暴出来了，笑死我了
牛客多校（五）
N. 打印题，签到（100）
K. 思维题，找规律（1700）
E. 数学题，线性筛（2300）
这题难点在于怎么魔改线性筛，在线性时间复杂度内取到所有数的最小质因子。教训是一定要懂得板子的原理
L. 思维题，差分（2400）
多刷cf锻炼思维吧，没什么好说的了。牛客和杭电的AI打分机打分有些虚高
杭电多校（五）
E. 模拟题，签到（1300）
J. 数学题，线性基（1900）
H. 数据结构题，二维偏分 + 离散化 + 线段树 + 离线查询（1700）
map和set操作的常数时间比lower_bound大近十倍，不知道有没有用先记着，毕竟狗杭电卡这个
牛客多校（六）
H. 思维题，签到（1500）
D. 图论题，Dijkstra单源最短路（1700）
G. 图论题，类拓扑排序（1900）
杭电多校（六）
L. 思维题，求贡献度（1900）
B. 模拟题，码力与细节（1600）
J. 数学题，推式子（1400）
当时因为这道题和队友闹得有点僵。问题在于，错误地把数学题当电波题做，不能严谨证明自己解法的最优性，说白了就是乱猜。对于像求贡献度、求差分等这种题，一定要认认真真依照条件列式子，不能脑袋一热就认定某种情况一定最优，然后再以此出发推出一大堆错误的结论
牛客多校（七）
K. 字符串题，签到（1300）
G. 思维题，模拟（1000）
L. 数学题，中国剩余定理（1700）
杭电多校（七）
H. 思维题，签到（800）
B. 字符串题，暴力（1600）
L. 树论题，DFS + 优先队列（1700）
牛客多校（八）
I. 模拟题，签到（1000）
G. 思维题，构造（1600）
B. 动态规划题，二维DP（1800）
这题题解和AI解提到了什么卡特兰数、前缀信息、括号序列模型之类的，但是我好像都没感受到。这题赛时给我最深的记忆点就是二维DP的内层循环需要倒序遍历，有点背包DP的意味。最难绷的是赛后补题的时候忘记了怎么做，啃自己赛时写的代码啃了半天
M. 字符串题，字典树 + 优先队列（1900）
杭电多校（八）
L. 数学题，签到（1000）
A. 图论题，BFS（1600）
B. 数据结构题，推式子 + 变量分离 + 线段树（1900）
最近经常遇到关于变量分离的题，这个要点最早应该是在位运算的题，要求我们注意到位的独立性，分开考虑。其实在任何题目推式子的时候都应该考虑通过变量分离的方式，去尝试简化式子
牛客多校（九）
B. 思维题，签到（800）
H. 思维题，构造（1700）
这道题已经可以称得上是很电波了，想练这种题唯一的办法就是多刷cf
I. 数学题，二分查找 + 二次函数
一个经典中学数学陷阱，当含参二次函数二次项系数为0的时候要当作一次函数做特判
D. 树论题，树上启发式合并（1900）
杭电多校（九）
A. 思维题，签到（800）
D. 数学题，前缀和 + 线性基（1600）
L. 数学题，二位偏序 + 树状数组（1700）
树状数组和线段树这类树形数据结构，可以动态处理当前位置前面的区间内大于当前位置的数的数量，鉴定为对树状数据结构用法不够掌握，建议多刷树状数组和线段树的题