2026牛客寒假算法基础集训营第1场结束了。我最后过的是BCEGKL这六道题A、D、F、H、I、J都留在了赛后补题名单里。说实话这套题的难度梯度拉得很开前面几道偏思维和数学的签到题比想象中友好中段开始就明显需要建模能力了。这篇文章就聊聊我在这一场里的做题顺序、六道题的完整思路拆解以及中间踩过的几个坑。如果你也打算打牛客的寒假集训营或者正在刷算法基础题想找点参考这篇应该能帮你少走一点弯路。先交代一下背景。牛客寒假算法基础集训营是每年寒假固定的系列赛分好几场每场大概十到十二道题覆盖的范围从基础的枚举、二分、贪心、DP到图论、数论、构造都有。题目整体偏“基础思维”不是那种刷题量到一定程度才能碰的难度更看重你把经典模型理解透没有。对准备校招笔试、打蓝桥杯或者刚接触ACM的选手来说是性价比很高的训练场。1. 赛事背景与定位牛客寒假集训营到底是什么1.1 为什么值得打免费的算法训练场很多刚入门的同学会问寒假在家自己刷题和打这种比赛有什么区别。我的答案是自己刷题容易陷入“舒适区”哪类题会就反复做哪类不会的一直拖着而集训营是编排好的套题考点覆盖面广限时环境又会逼你在考场上做取舍。更重要的是赛后能看到别人的思路和通过率数据这比自己闷头刷有效得多。这一场我是在家里打的环境比较放松但节奏依然是按比赛来的。牛客的赛制是标准ACM赛制提交错误会有罚时所以“稳住能过的、不盲目死磕”反而比“多过一道题”更重要。这也是我选择先扫题、再按BCEGKL顺序做的原因。1.2 2026年第1场的整体观感第一场给我的感觉是签到题会在前几道但不会让你白拿中间夹杂着几道需要绕弯的题。比如说后面要详细聊的K和L题面第一眼看像是要推复杂公式实际上规律非常简单属于看穿之后一两行代码就能解决的类型。B和C是整套题里最值得学习的部分一个考区间DP的经典优化一个考带约束的最短路变形。G题则是那种“想到了就秒想不到就卡死”的树上思维题。整体来说这套题对你掌握的基础算法要求不算高但对建模的灵活性要求比较高。2. 做题节奏与策略从BCEGKL看排兵布阵2.1 我的过题顺序与时间轴我个人的习惯是开场先花五分钟把题面全部扫一遍不急着做先把“哪题像签到、哪题数据范围大、哪题题面里带了奇怪的限制条件”摸清。本场扫完题之后我心里的顺序是K → L → B → E → G → C。实际最后EFG和C的完成顺序略有调整但过题集合就是标题里的BCEGKL。说下原因。K和L的题面一眼能看到“数学/构造”标签这种题通常通过率分布非常两极化要么是送分、要么是坑题值得优先花十分钟试一下。B题是经典的区间调度模型看到“价值最大”基本能确定是DP属于稳定得分点。E题位运算、G题树上问题都需要一点思维转译放在中间做比较合理。C题我放到最后是因为它的题面信息量比较大需要花时间建模不适合一上来就陷进去。2.2 判断题目难度的几个信号这里分享一个非常实用的经验判断一道题难不难先看数据范围再看通过人数。数据范围直接告诉你这题应该用什么复杂度的算法比如n ≤ 10^5基本就是O(n log n)或O(n)n ≤ 20很大概率是状压DP或者暴力枚举。而通过人数是最诚实的难度标记如果开赛半小时K题通过人数已经几百说明它是送分题别犹豫直接做。今年这场我一度在E题上纠结了很久后来切出去看了眼通过人数立刻决定先放一放转去做G。事实证明这个决定是对的G题想通之后十分钟就AC了而E题回头冷静下来做也没花太久。比赛里最怕的就是跟一道题较劲到心态崩掉学会及时抽身比多会一个算法重要得多。3. 签到与思维题拆解K、L是拿分基本盘3.1 K题数字根题背后的同余周期K题大致是这个意思定义f(x)为把一个数的各位数字反复相加直到变成一位数问区间[l, r]里有多少个数的f(x)等于k。如果你知道“数字根”这个概念应该立刻能反应过来f(x)的本质就是x mod 9只是把余数0映射成9。所以这个问题就变成了统计[l, r]内有多少个数模9等于k%9。代码非常短核心就是计算从1到n有多少个数模9余m然后做差。这里要注意的是k9和k0的取模映射关系很多人在这里被卡了一发。这种题考的不是算力而是数学直觉——看到“反复加各位数字”就能想到模9答案就是一行公式的事。我用C写的判定大概是这样的long long cnt(long long n, int m) { if (n 0) return 0; return n / 9 (n % 9 m ? 1 : 0); } // 区间内询问直接 cnt(r, m) - cnt(l - 1, m)这个题的教训就是基础题考的是你把常见数学结论背熟没有。数字根、同余、奇偶性、进制转换这些平时觉得“太基础没必要看”的知识点恰恰是集训营前几题最爱出的。3.2 L题构造题里的奇偶分组套路L题是一道构造题题意大体是要求构造一个长度为n的排列使得相邻两个数的和满足某个条件印象里是不能被某个数整除。这类题在牛客出现的频率非常高套路也非常固定先把奇数和偶数分开排再想办法把交界处处理掉。为什么奇偶分组这么有用因为如果限制条件是“和不能被2整除”那奇数奇数、偶数偶数都会冲突只有奇偶交替可行。如果限制的是“和不能被3整除”那就需要按模3的余数分类来构造。本质上是同余类分组问题。构造题的通用思路是先猜一个简单结构验证一下边界条件如果成立就直接写。不要一上来就搞复杂的填充算法。L题的通过率不低说明大部分人都想到了奇偶分类这个经典套路。这种题考的就是见多识广你刷到过类似构造考场上就有思路没刷过很容易卡在“到底怎么排”的迷茫里。4. DP与图论题拆解B、C是稳定分水岭4.1 B题区间调度里的DP二分优化B题是那种你一看就知道要DP但写过之后能收获很多的题。题意是给n个任务每个任务有开始时间、结束时间和价值要求选出若干互不重叠的任务使总价值最大。这就是经典的带权区间调度问题。如果n很小直接按结束时间排序两层循环做O(n^2)的DP就能过状态转移是dp[i] max(dp[i-1], dp[j] v[i])其中j是最后一个结束时间不超过第i个任务开始时间的任务。但看这道题的数据范围O(n^2)肯定超时需要用二分把找j的过程优化到O(log n)。这里有一个很容易踩坑的地方二分时到底是找“最后一个结束时间 ≤ s_i”还是“第一个结束时间 s_i”我建议直接写一个辅助数组end_time排序后对end_time做upper_bound再减去数组起始迭代器得到下标j然后dp[i] max(dp[i-1], dp[j] v[i])。注意下标从0开始的话end_time的下标和任务下标要对齐不然转移会错位。核心代码思路如下struct Seg { int l, r, v; }; sort(seg 1, seg n 1, cmp); // 按结束时间升序 for (int i 1; i n; i) { int j upper_bound(endTime 1, endTime i, seg[i].l) - endTime - 1; dp[i] max(dp[i - 1], dp[j] seg[i].v); }这道题的价值在于它是“DP 二分优化”这个组合最经典的入门模型。很多面试题和比赛中出现的“最多能完成多少任务”“最大收益排程”都是它的变体值得彻底吃透。4.2 C题带时间约束的最短路问题C题给我留下的印象最深因为它的题面信息量很大建模过程让我绕了一会儿。题意大致是给一个有向图每条边有一个“开放时间”你必须等到了那个时间点之后才能通过这条边求从起点到终点的最早到达时间。这类题看起来是图论实际上是一个带约束的最短路。你维护的dis[u]不再是单纯的边权和而是“到达u点的最早时间”。转移的时候要注意如果当前到达u的时间是now而边e的开放时间是t那么通过这条边后的时间是max(now, t) w而不是now w。这个max操作就是整道题的灵魂。很多人在转移时想当然地写成now w样例可能都过不了。还有个细节是Dijkstra的堆优化不能丢因为每个点可能被更新多次直接队列BFS会导致复杂度退化。在写这部分的时候我犯了一个典型错误没有把“开放时间”理解成全局时间而是把它当成边权的一部分去累加。后来画了个用例才想明白题目里的时间轴是全局的等不等直接影响后续路径规划。这种题本质上考的是把现实约束翻译成状态转移的能力。代码里我额外维护了一个vis数组防止同一个点的同一个时间状态被重复出队。这里也提醒一句如果状态里除了点还有额外的维度比如时间、油箱剩余油量等需要开二维数组或者用unordered_map处理单纯的一维dis数组会漏状态。5. 位运算与树上问题拆解E、G是思维量大的两题5.1 E题按位贪心求最大ANDE题是给定一个数组求任意两个数按位与的最大值。如果你用O(n^2)暴力数据范围一大就必然超时。这种求“两个数某种位运算的最大值”的题通用解法是按位贪心。按位贪心的思路是从最高位往最低位尝试假设答案是ans先假设这一位可以取1然后判断数组里是否存在两个数它们与ans以及更低位暂时设为0做按位与之后结果仍然等于ans。如果能找到这一位就确定为1否则保持0。判断的方法也很巧妙把每个数x的“候选位集合”提取出来看看有没有重复出现等价于看x mask是否出现过两次。我当时第一次写这题时在判断“是否存在两个数都包含当前位集合”的时候写错了集合去重的逻辑。正确做法是维护一个哈希集合遍历数组如果x mask已经在集合里说明至少有两个不同的数能匹配上直接返回true否则插入集合。注意两个不同的数可能提取出相同的值所以用集合判重而不是直接比较这一点很关键。核心代码如下int ans 0; for (int bit 30; bit 0; bit--) { int mask ans | (1 bit); unordered_setint st; bool ok false; for (int x : a) { int cur x mask; if (st.count(cur)) { ok true; break; } st.insert(cur); } if (ok) ans mask; }E题给我们的启示是位运算类题目别硬想公式从高位到低位逐位确认往往是最稳的思路。类似的套路还可以推广到求最大异或对用Trie树、最大或、最大与。掌握一个套路等于会了好几个题。5.2 G题树上翻转的奇偶性思维G题是我这套题里最喜欢的一道。题意大概是这样给一棵树每个节点有一个0/1状态每次操作可以选定一个节点把以它为根的整棵子树的所有节点状态取反问最少操作多少次能让所有节点都变成目标状态。这道题如果直接去想“每个节点被操作多少次”会越想越乱。真正的突破口是发现每个节点只受它祖先节点操作的影响因为操作一个节点的子树会覆盖到它所有后代但不会影响它的祖先。所以从叶子向根做DFS维护一个“当前节点被祖先翻转了多少次”的计数器如果这个计数器的奇偶性和当前状态加起来不等于目标那当前节点就一定要被操作一次。为什么只看奇偶性因为翻转两次等于不翻所以操作次数只需要记录奇偶。这是树上的异或思维题非常经典。实现时需要注意DFS往下传的时候要把“当前节点是否需要操作”也加进计数器的奇偶性里。如果这棵树特别深递归可能爆栈我写的时候直接把递归改成了栈模拟顺便避开这个隐患。代码部分倒是很简单难的是想通每个节点只跟祖先有关这一个点。这种题考的不是代码量而是你能不能从“子树”这个词想到祖先关系再把问题转化成递推。如果你平时训练时见过“树上差分”“子树加”之类的模型做这道题会顺很多。6. 本场踩坑实录五个明知故犯的失误6.1 坑位一二分边界的lower_bound/upper_bound用反B题里我在二分时第一次用了lower_bound结果找出来的任务包含了“开始时间等于当前开始时间”的重叠任务答案直接偏大。正确用法是要找“结束时间 ≤ 当前开始时间”所以应该用upper_bound找第一个大于的再减一。这是一个非常容易错的细节建议在代码里注释清楚“取→最后一个结束时间≤开始时间的位置”。6.2 坑位二位运算符与等于号优先级E题我在if里写了类似 if ((x mask) mask) 的表达式一开始没加括号结果因为的优先级比低程序把x (mask mask)当成一个表达式编译能过但结果完全不对。这个问题很基础但每年比赛都有人中招。写完位运算相关的条件多看两眼括号。6.3 坑位三取模之后比较大小K题我一开始在统计区间数量时直接用long long计算n/9然后拿n%9和某个余数比较中途忘了把k9的情况映射成余数0输出错了好几发。这类数学题最容易在边界条件上翻车建议在纸上把k0和k9的取值写清楚再开始编码。6.4 坑位四乘法溢出与中间结果类型C题我在计算等待时间通过时间时一开始用int存dis数组结果数据一大直接溢出。比赛里一个常见的习惯就是凡是涉及时间、距离、价值的地方无脑开long long。别觉得自己能估算范围溢出这种bug非常难查。6.5 坑位五DFS递归爆栈问题G题树的深度比较大直接递归DFS有可能爆系统栈。我写题时习惯直接手写栈或者用vector模拟邻接表迭代省得赛后补题才发现这棵树深得要命。这一点在本地编译时可能不明显但在比赛的评测环境里很玄学能避免就避免。7. 赛后复盘从一场训练赛里把价值榨干7.1 补题的三种正确姿势打完比赛只对答案是不够的。我的补题流程是这样的第一遍看题解理解核心思路不看代码第二遍自己重新写一遍卡住了就看题解的某几行提示但不能整段复制第三遍隔三天再刷一次这六道题这一遍要求控制在比赛时间内完成。三遍下来这套题的考点基本就跑不掉了。7.2 建立“思路笔记”而不是“代码笔记”我会给每道题建一个标签比如“数字根→模9”“带权区间调度→排序DP二分”“树上翻转→奇偶性DFS”这种短语。等到下次遇到类似题目翻笔记的时候一眼就能看到关键词。注意别只写代码解法重点是记“怎么从题目特征联想到这个做法”这才是赛后复盘真正留下的东西。7.3 我的个人体会算法训练的重心在哪刷了几年题参加过很多次牛客的寒假营我最大的体会是算法竞赛的进步曲线不是线性的它更像爬台阶——你可能很长一段时间卡在同一水平然后在某个节点突然想通一类题。这个“想通”多半不是因为刷了一百道新题而是因为把一个经典模型反复咀嚼了很多遍。这一场BCEGKL六道题每一道对应的知识点其实都是教材级的二分优化DP、按位贪心、树上奇偶翻转、Dijkstra变体、同余计数、构造分组。如果你只把它们当成一次比赛任务做完就忘那收获很有限。但如果你把每道题当作一个模型来研究搞清楚“为什么能这么想”那么这一场比赛带给你的东西会比刷一百道水题更扎实。 
长河君 · 2026/9/12 11:33:44 · 阅读 1.2k 牛客寒假算法集训营第一场BCEGKL题解与复盘
2026牛客寒假算法基础集训营第1场结束了。我最后过的是BCEGKL这六道题A、D、F、H、I、J都留在了赛后补题名单里。说实话这套题的难度梯度拉得很开前面几道偏思维和数学的签到题比想象中友好中段开始就明显需要建模能力了。这篇文章就聊聊我在这一场里的做题顺序、六道题的完整思路拆解以及中间踩过的几个坑。如果你也打算打牛客的寒假集训营或者正在刷算法基础题想找点参考这篇应该能帮你少走一点弯路。先交代一下背景。牛客寒假算法基础集训营是每年寒假固定的系列赛分好几场每场大概十到十二道题覆盖的范围从基础的枚举、二分、贪心、DP到图论、数论、构造都有。题目整体偏“基础思维”不是那种刷题量到一定程度才能碰的难度更看重你把经典模型理解透没有。对准备校招笔试、打蓝桥杯或者刚接触ACM的选手来说是性价比很高的训练场。1. 赛事背景与定位牛客寒假集训营到底是什么1.1 为什么值得打免费的算法训练场很多刚入门的同学会问寒假在家自己刷题和打这种比赛有什么区别。我的答案是自己刷题容易陷入“舒适区”哪类题会就反复做哪类不会的一直拖着而集训营是编排好的套题考点覆盖面广限时环境又会逼你在考场上做取舍。更重要的是赛后能看到别人的思路和通过率数据这比自己闷头刷有效得多。这一场我是在家里打的环境比较放松但节奏依然是按比赛来的。牛客的赛制是标准ACM赛制提交错误会有罚时所以“稳住能过的、不盲目死磕”反而比“多过一道题”更重要。这也是我选择先扫题、再按BCEGKL顺序做的原因。1.2 2026年第1场的整体观感第一场给我的感觉是签到题会在前几道但不会让你白拿中间夹杂着几道需要绕弯的题。比如说后面要详细聊的K和L题面第一眼看像是要推复杂公式实际上规律非常简单属于看穿之后一两行代码就能解决的类型。B和C是整套题里最值得学习的部分一个考区间DP的经典优化一个考带约束的最短路变形。G题则是那种“想到了就秒想不到就卡死”的树上思维题。整体来说这套题对你掌握的基础算法要求不算高但对建模的灵活性要求比较高。2. 做题节奏与策略从BCEGKL看排兵布阵2.1 我的过题顺序与时间轴我个人的习惯是开场先花五分钟把题面全部扫一遍不急着做先把“哪题像签到、哪题数据范围大、哪题题面里带了奇怪的限制条件”摸清。本场扫完题之后我心里的顺序是K → L → B → E → G → C。实际最后EFG和C的完成顺序略有调整但过题集合就是标题里的BCEGKL。说下原因。K和L的题面一眼能看到“数学/构造”标签这种题通常通过率分布非常两极化要么是送分、要么是坑题值得优先花十分钟试一下。B题是经典的区间调度模型看到“价值最大”基本能确定是DP属于稳定得分点。E题位运算、G题树上问题都需要一点思维转译放在中间做比较合理。C题我放到最后是因为它的题面信息量比较大需要花时间建模不适合一上来就陷进去。2.2 判断题目难度的几个信号这里分享一个非常实用的经验判断一道题难不难先看数据范围再看通过人数。数据范围直接告诉你这题应该用什么复杂度的算法比如n ≤ 10^5基本就是O(n log n)或O(n)n ≤ 20很大概率是状压DP或者暴力枚举。而通过人数是最诚实的难度标记如果开赛半小时K题通过人数已经几百说明它是送分题别犹豫直接做。今年这场我一度在E题上纠结了很久后来切出去看了眼通过人数立刻决定先放一放转去做G。事实证明这个决定是对的G题想通之后十分钟就AC了而E题回头冷静下来做也没花太久。比赛里最怕的就是跟一道题较劲到心态崩掉学会及时抽身比多会一个算法重要得多。3. 签到与思维题拆解K、L是拿分基本盘3.1 K题数字根题背后的同余周期K题大致是这个意思定义f(x)为把一个数的各位数字反复相加直到变成一位数问区间[l, r]里有多少个数的f(x)等于k。如果你知道“数字根”这个概念应该立刻能反应过来f(x)的本质就是x mod 9只是把余数0映射成9。所以这个问题就变成了统计[l, r]内有多少个数模9等于k%9。代码非常短核心就是计算从1到n有多少个数模9余m然后做差。这里要注意的是k9和k0的取模映射关系很多人在这里被卡了一发。这种题考的不是算力而是数学直觉——看到“反复加各位数字”就能想到模9答案就是一行公式的事。我用C写的判定大概是这样的long long cnt(long long n, int m) { if (n 0) return 0; return n / 9 (n % 9 m ? 1 : 0); } // 区间内询问直接 cnt(r, m) - cnt(l - 1, m)这个题的教训就是基础题考的是你把常见数学结论背熟没有。数字根、同余、奇偶性、进制转换这些平时觉得“太基础没必要看”的知识点恰恰是集训营前几题最爱出的。3.2 L题构造题里的奇偶分组套路L题是一道构造题题意大体是要求构造一个长度为n的排列使得相邻两个数的和满足某个条件印象里是不能被某个数整除。这类题在牛客出现的频率非常高套路也非常固定先把奇数和偶数分开排再想办法把交界处处理掉。为什么奇偶分组这么有用因为如果限制条件是“和不能被2整除”那奇数奇数、偶数偶数都会冲突只有奇偶交替可行。如果限制的是“和不能被3整除”那就需要按模3的余数分类来构造。本质上是同余类分组问题。构造题的通用思路是先猜一个简单结构验证一下边界条件如果成立就直接写。不要一上来就搞复杂的填充算法。L题的通过率不低说明大部分人都想到了奇偶分类这个经典套路。这种题考的就是见多识广你刷到过类似构造考场上就有思路没刷过很容易卡在“到底怎么排”的迷茫里。4. DP与图论题拆解B、C是稳定分水岭4.1 B题区间调度里的DP二分优化B题是那种你一看就知道要DP但写过之后能收获很多的题。题意是给n个任务每个任务有开始时间、结束时间和价值要求选出若干互不重叠的任务使总价值最大。这就是经典的带权区间调度问题。如果n很小直接按结束时间排序两层循环做O(n^2)的DP就能过状态转移是dp[i] max(dp[i-1], dp[j] v[i])其中j是最后一个结束时间不超过第i个任务开始时间的任务。但看这道题的数据范围O(n^2)肯定超时需要用二分把找j的过程优化到O(log n)。这里有一个很容易踩坑的地方二分时到底是找“最后一个结束时间 ≤ s_i”还是“第一个结束时间 s_i”我建议直接写一个辅助数组end_time排序后对end_time做upper_bound再减去数组起始迭代器得到下标j然后dp[i] max(dp[i-1], dp[j] v[i])。注意下标从0开始的话end_time的下标和任务下标要对齐不然转移会错位。核心代码思路如下struct Seg { int l, r, v; }; sort(seg 1, seg n 1, cmp); // 按结束时间升序 for (int i 1; i n; i) { int j upper_bound(endTime 1, endTime i, seg[i].l) - endTime - 1; dp[i] max(dp[i - 1], dp[j] seg[i].v); }这道题的价值在于它是“DP 二分优化”这个组合最经典的入门模型。很多面试题和比赛中出现的“最多能完成多少任务”“最大收益排程”都是它的变体值得彻底吃透。4.2 C题带时间约束的最短路问题C题给我留下的印象最深因为它的题面信息量很大建模过程让我绕了一会儿。题意大致是给一个有向图每条边有一个“开放时间”你必须等到了那个时间点之后才能通过这条边求从起点到终点的最早到达时间。这类题看起来是图论实际上是一个带约束的最短路。你维护的dis[u]不再是单纯的边权和而是“到达u点的最早时间”。转移的时候要注意如果当前到达u的时间是now而边e的开放时间是t那么通过这条边后的时间是max(now, t) w而不是now w。这个max操作就是整道题的灵魂。很多人在转移时想当然地写成now w样例可能都过不了。还有个细节是Dijkstra的堆优化不能丢因为每个点可能被更新多次直接队列BFS会导致复杂度退化。在写这部分的时候我犯了一个典型错误没有把“开放时间”理解成全局时间而是把它当成边权的一部分去累加。后来画了个用例才想明白题目里的时间轴是全局的等不等直接影响后续路径规划。这种题本质上考的是把现实约束翻译成状态转移的能力。代码里我额外维护了一个vis数组防止同一个点的同一个时间状态被重复出队。这里也提醒一句如果状态里除了点还有额外的维度比如时间、油箱剩余油量等需要开二维数组或者用unordered_map处理单纯的一维dis数组会漏状态。5. 位运算与树上问题拆解E、G是思维量大的两题5.1 E题按位贪心求最大ANDE题是给定一个数组求任意两个数按位与的最大值。如果你用O(n^2)暴力数据范围一大就必然超时。这种求“两个数某种位运算的最大值”的题通用解法是按位贪心。按位贪心的思路是从最高位往最低位尝试假设答案是ans先假设这一位可以取1然后判断数组里是否存在两个数它们与ans以及更低位暂时设为0做按位与之后结果仍然等于ans。如果能找到这一位就确定为1否则保持0。判断的方法也很巧妙把每个数x的“候选位集合”提取出来看看有没有重复出现等价于看x mask是否出现过两次。我当时第一次写这题时在判断“是否存在两个数都包含当前位集合”的时候写错了集合去重的逻辑。正确做法是维护一个哈希集合遍历数组如果x mask已经在集合里说明至少有两个不同的数能匹配上直接返回true否则插入集合。注意两个不同的数可能提取出相同的值所以用集合判重而不是直接比较这一点很关键。核心代码如下int ans 0; for (int bit 30; bit 0; bit--) { int mask ans | (1 bit); unordered_setint st; bool ok false; for (int x : a) { int cur x mask; if (st.count(cur)) { ok true; break; } st.insert(cur); } if (ok) ans mask; }E题给我们的启示是位运算类题目别硬想公式从高位到低位逐位确认往往是最稳的思路。类似的套路还可以推广到求最大异或对用Trie树、最大或、最大与。掌握一个套路等于会了好几个题。5.2 G题树上翻转的奇偶性思维G题是我这套题里最喜欢的一道。题意大概是这样给一棵树每个节点有一个0/1状态每次操作可以选定一个节点把以它为根的整棵子树的所有节点状态取反问最少操作多少次能让所有节点都变成目标状态。这道题如果直接去想“每个节点被操作多少次”会越想越乱。真正的突破口是发现每个节点只受它祖先节点操作的影响因为操作一个节点的子树会覆盖到它所有后代但不会影响它的祖先。所以从叶子向根做DFS维护一个“当前节点被祖先翻转了多少次”的计数器如果这个计数器的奇偶性和当前状态加起来不等于目标那当前节点就一定要被操作一次。为什么只看奇偶性因为翻转两次等于不翻所以操作次数只需要记录奇偶。这是树上的异或思维题非常经典。实现时需要注意DFS往下传的时候要把“当前节点是否需要操作”也加进计数器的奇偶性里。如果这棵树特别深递归可能爆栈我写的时候直接把递归改成了栈模拟顺便避开这个隐患。代码部分倒是很简单难的是想通每个节点只跟祖先有关这一个点。这种题考的不是代码量而是你能不能从“子树”这个词想到祖先关系再把问题转化成递推。如果你平时训练时见过“树上差分”“子树加”之类的模型做这道题会顺很多。6. 本场踩坑实录五个明知故犯的失误6.1 坑位一二分边界的lower_bound/upper_bound用反B题里我在二分时第一次用了lower_bound结果找出来的任务包含了“开始时间等于当前开始时间”的重叠任务答案直接偏大。正确用法是要找“结束时间 ≤ 当前开始时间”所以应该用upper_bound找第一个大于的再减一。这是一个非常容易错的细节建议在代码里注释清楚“取→最后一个结束时间≤开始时间的位置”。6.2 坑位二位运算符与等于号优先级E题我在if里写了类似 if ((x mask) mask) 的表达式一开始没加括号结果因为的优先级比低程序把x (mask mask)当成一个表达式编译能过但结果完全不对。这个问题很基础但每年比赛都有人中招。写完位运算相关的条件多看两眼括号。6.3 坑位三取模之后比较大小K题我一开始在统计区间数量时直接用long long计算n/9然后拿n%9和某个余数比较中途忘了把k9的情况映射成余数0输出错了好几发。这类数学题最容易在边界条件上翻车建议在纸上把k0和k9的取值写清楚再开始编码。6.4 坑位四乘法溢出与中间结果类型C题我在计算等待时间通过时间时一开始用int存dis数组结果数据一大直接溢出。比赛里一个常见的习惯就是凡是涉及时间、距离、价值的地方无脑开long long。别觉得自己能估算范围溢出这种bug非常难查。6.5 坑位五DFS递归爆栈问题G题树的深度比较大直接递归DFS有可能爆系统栈。我写题时习惯直接手写栈或者用vector模拟邻接表迭代省得赛后补题才发现这棵树深得要命。这一点在本地编译时可能不明显但在比赛的评测环境里很玄学能避免就避免。7. 赛后复盘从一场训练赛里把价值榨干7.1 补题的三种正确姿势打完比赛只对答案是不够的。我的补题流程是这样的第一遍看题解理解核心思路不看代码第二遍自己重新写一遍卡住了就看题解的某几行提示但不能整段复制第三遍隔三天再刷一次这六道题这一遍要求控制在比赛时间内完成。三遍下来这套题的考点基本就跑不掉了。7.2 建立“思路笔记”而不是“代码笔记”我会给每道题建一个标签比如“数字根→模9”“带权区间调度→排序DP二分”“树上翻转→奇偶性DFS”这种短语。等到下次遇到类似题目翻笔记的时候一眼就能看到关键词。注意别只写代码解法重点是记“怎么从题目特征联想到这个做法”这才是赛后复盘真正留下的东西。7.3 我的个人体会算法训练的重心在哪刷了几年题参加过很多次牛客的寒假营我最大的体会是算法竞赛的进步曲线不是线性的它更像爬台阶——你可能很长一段时间卡在同一水平然后在某个节点突然想通一类题。这个“想通”多半不是因为刷了一百道新题而是因为把一个经典模型反复咀嚼了很多遍。这一场BCEGKL六道题每一道对应的知识点其实都是教材级的二分优化DP、按位贪心、树上奇偶翻转、Dijkstra变体、同余计数、构造分组。如果你只把它们当成一次比赛任务做完就忘那收获很有限。但如果你把每道题当作一个模型来研究搞清楚“为什么能这么想”那么这一场比赛带给你的东西会比刷一百道水题更扎实。