2026 年 2 月日祭
梦熊集训
梦熊集训是什么打板子大赛吗。
选择性地记录了部分题目。
Day 1 : 分块思想 & 莫队
其实这天是 1 月 31 日。
分块是会的，莫队是不会的。后者是，对于一些静态问题，若支持
一个经典 trick 是，对于一些题目，我们需要
C - 教主的魔法
考虑分块。区间加是容易的，直接做即可。查询
是困难的，考虑有什么东西能够维护这东西，容易想到排序与二分，实时维护对每个块排序的结果即可。时间复杂度 或 。 D - Range Set Query
区间数颜色，可以莫队草过。考虑
做法，显然先离线下来，发现对于右端点 ，左端点的答案从右往左显然是单调不降的，而能带来贡献的点的颜色一定没在右侧出现。所以拿树状数组维护维护每个位置的贡献即可。 E - Range Shuffle Query
使用经典 trick 即可。
G - 异或序列
类似于小 Z 的袜子，直接莫队即可。
H - 弹飞绵羊
经典分块维护动态树。
I - 蒲公英
经典分块维护众数，以块为单位，预处理出每个区间的众数与每个元素在前缀的出现次数，那么每个询问的答案要么是零散块中的数，要么是整块的答案，随便处理一下即可。
J - 由乃打扑克
经典题，类似于教主的魔法，在外面再套一层二分即可，需要卡常。
Day 2 : 线段树进阶 1
这是线段树基础吧。
B - Takoyaki and Flip
需要维护加、翻转、清零的标记，注意一下几个标记的优先级与下放顺序即可。
C - Transformation
大概是屎吧，大力维护一下即可，不想写。
D - 大魔法师
直接做是困难的，发现只有矩阵能维护这东西，然后做完了，需要卡常。
F - Maximize The Value
对于每个元素单独考虑，发现此时只用维护一下最大子段和。扫描线即可。
G - 火灾 / Fire
感谢这道题占掉了我一下午，不然没事干了。
考虑初始每个数最终在
矩阵上的覆盖区域。发现是一个平行四边形，它的长宽可以单调栈求出。平行四边形是困难的，将其拆成三个三角形，发现这三个三角形都是等腰直角三角形且有一条直角边在 轴（ ）上。考虑询问，线段是困难的，射线是容易的，将一条线段拆成两条向左的射线。令三角形按右上角定位，射线按端点定位。考虑一个三角形对一条射线的贡献，可以分成两类。若三角形在射线左侧，那么三角形的贡献可以放到 轴（ ）上，是一个带权的加；否则，三角形的贡献可以斜着（向左下）放到 轴上，也是带权的加。把所有三角形和射线按位置排序，用两个树状数组（或线段树）维护两侧的三角形的贡献即可。
Day 3 : 线段树进阶 2
B - Rmq Problem / mex
主席树或莫队即可。
D - Clearance
简单的势能分析题。
E - DZY Loves Colors
好像不太熟悉有关颜色段的势能分析。考虑线段树维护，查询是容易的；对于修改，若当前区间颜色不同，那么暴力递归处理儿子；否则直接修改。考虑一次修改覆盖的区间，除了两侧可能有
个零散的颜色段，中间的颜色段都是完整的，而一个颜色段只会被插入一次删除一次，插入和删除的时间复杂度是 ，所以总时间复杂度是 。 F - 市场
经典势能分析题，维护并讨论极差即可。
G - 楼房重建
经典 trick，
合并即可。
模拟赛 1
A - 北极星（QOJ2402）
正难则反即可。
B - 太空沙（洛谷 P3573）
想不到拓扑序，是不是可以退役了。考虑直接算出删掉每个点之后的最长路。对于当前点，删掉它后剩下了三种路径：起点与终点拓扑序均比当前点小；起点与终点拓扑序均比当前点大；起点拓扑序比当前点小，终点拓扑序比当前点大。对所有点按拓扑序排序，前两种直接前后缀和即可，第三种拿个 multiset 维护一下即可。
C - 排列（洛谷 P14419 加强版）
拿棵势能线段树维护一下
即可。 D - 昔在、今在、永在的剧目
发现
与 的限制都是在使区间变长，有且仅有 最小的限制在使区间变短，因此考虑从 的角度入手。对于每个 ，钦定 是最大值，那么直接选择 在笛卡尔树上管辖的区间即可，若这个区间的或和 ，那么把 甩到一个树状数组上维护后缀最小值即可，这也顺便解决了 的限制。考虑修改，直接在笛卡尔树上跳即可，如果当前操作没有影响就停止。因为一个点最多被修改 次，所以时间复杂度 。
Day 4 : 树上问题 1
F - Beautiful Pair
哦哦每个节点的贡献是独立的，我在想什么。
枚举最大值，那么显然有了左右两个区间。在较小的区间中暴力枚举，在另一个区间中查询。这东西复杂度是
的，因为本质上是一个启发式合并的过程。 G - 黑暗幻想
太牛了。发现 Alice 很容易赢，那就讨论一下 Alice 什么时候能赢。发现
较小时 Alice 可以二分图染色，只要染完较少的一半还能再染一次就一定能赢，此时要求 ；若 Alice 只能操作 次，即 ，讨论一下发现依然是 Alice 必胜；若 Alice 只能操作一次，即 ，那么当且仅当 时 Bob 胜。
Day 5 : 树上问题 2
B - Tree Destruction
一个显然的贪心是保留直径，做完了。
C - Tenzing and Tree
太牛了。考虑拆绝对值，发现若根是带权重心就能拆掉绝对值。枚举带权重心，发现错解不优，于是贪心即可。
D - 聚会 2
太牛了，把重心和直径结合在了一起。考虑取
个点的情况（ 是偶数）。考虑到重心在一条 到 的路径上，使得所有带权点都在以 为根 的子树中或以 为根 的子树中，且两个连通块中的带权点数相同。令重心为根，讨论 的关系并放缩，转化为 ，于是按子树大小从大到小排序并动态维护直径即可。 E - 捉迷藏
唐。
F - Dynamic Diameter
唐。
G - 幻想乡战略游戏
略屎。考虑到重心只与点权有关，于是先动态维护一下重心。具体地，重心
是 dfs 序最大的满足 的点。考虑维护答案，拆一下式子过后发现维护链加链和即可。
Day 6 : 图论杂题选讲 1
图论板题选讲 1。不过反正我图论菜。
模拟赛 2
A - Sing Alive
唐。
B - 旅行
唐。
C - 地砖
屎。对形态打表即可。
D - 简单修路题
牛但典。考虑 ST 表优化建图，若第
层的点 与点 连通则说明 与 一一连通。考虑合并第 层的 与 ，若这两点本身连通则结束合并；否则合并并暴力下放到儿子；下放到第 层时计算贡献。因为每个点只会被合并一次，所以时间复杂度 。
Day 7 : 图论杂题选讲 2
都并非困难，但有些题怎么就是想不到呢。
C - 归程
容易想到双
做法，直接建出可持久化并查集即可。考虑如何单 ，尝试找到一个结构能把加边的过程复原出来，容易想到 Kruskal 重构树。因为树上的点权满足堆的性质，并保留了每个时刻点之间连通的信息，所以查询时直接树上倍增即可。 E - 旅行者
发现以点为主体计算是困难的，考虑将主体变为边。钦定一条边在最短路上，求出离两个端点最近的关键点是容易的，那就做完了。
G - Modulo Shortest Path
容易想到对所有点按照
排序，这样就变成了对前缀和后缀连边。容易想到令 ， 同理，点数和边数就变成 的了，但这样会产生负权边。为了不产生负权边，我们需要对后缀的部分进行修改。设我们要对 到 连边，显然需要满足 ，那我就令 。考虑 的元素如何处理，发现直接令 即可。 I - Elaxia 的路线
首先容易求出哪些有向边同时在两个人路线中出现，显然不可能出现环，那么这些边就形成了一个 DAG，直接跑最长路即可。
Day 8 : DP 优化 1
G - Hitchhiking in the Baltic States
太牛了。设
表示长度为 的子序列，最后一项的最小值，发现新加入一项对 的影响是：区间加、删除元素、插入元素。因为进行区间加之后 数组依然是有序的，所以可以使用平衡树维护。
Day 9 : DP 优化 2
J - LCC
钦定碰撞的点以及方向，那么我们就有了若干条形如
与 的方向必须 / 不能同时为 与 的限制，于是有一个简单的 DP。这个转移可以写成矩阵形式，考虑把所有碰撞按照碰撞时间排序，那么每次碰撞只需要修改一个矩阵，拿线段树维护一下即可。时间复杂度 。
其他题在 这里。
模拟赛 3
D - 最长直径（洛谷 P9846）
数据好水，直接钦定带权直径是不带权直径也能过。一个简单的
做法是枚举直径，再在直径上 DP。考虑把区间 DP 搬到树上，同样设 表示选了 条边，当前直径端点为 的最大权值。但这样可能会把某个端点本来想走的点当成废点用了，所以额外加两个 01 维表示左端点和右端点是否已经确定即可。代码是屎的。感觉这东西难点在于样例太弱导致容易误认为答案在原直径上。
Day 10 : 字符串
B - Isomorphic Strings
考虑对于每个字符出现的位置进行哈希，那么查询两个区间是否相等，只需要判断第一个区间中每个字符的哈希值是否与第二个区间中每个字符的哈希值一一相等即可。把哈希值取出来再排序比较即可。
C - 集合
首先考虑对于每个左端点预处理出最大的合法的右端点，这一部分使用双指针实现。考虑如何判断两个区间相等，与上一题类似，对于每个字符出现的位置进行哈希，那么现在只需要判断集合相等，再哈希一次即可。
D - First! G
建出字典树，枚举每个串，对于它的字典树上的每个结点，该结点字典序应当比它所有兄弟都小，于是建出图判一下环即可。
F - You Are Given Some Strings…
我咋这么唐，把
的正反串各建一个自动机，再把 的正反串丢到这两个自动机里即可。 H - 回响形态
不会 trick。border 一个有趣性质是，对于原串的一个 border，若我把原串正反相间插入形成一个新串
，那么这个 border 在新串中就是一个回文串。那么本题做完了。
Day 11 : 组合计数 1
从二项式反演讲到了莫比乌斯反演（？）。
选的题除了
J - BBQ Hard
太牛了。要求的相当于是
，考虑后面那东西的组合意义，即从 走到 的方案数。发现这样依然很难做，充分发扬人类智慧，把矩形平移一下，变为 走到 的方案数。这样，起点只有 个，终点也只有 个，于是直接格路计数即可。 M - 修行 / Asceticism
原来容斥两遍就做完了吗。第一遍把恰好
个容斥为至少 个，第二遍把 个非空段容斥为 个段。这样是 的，大力推式子就变成 或 了。
Day 12 : 组合计数 2
D - 数字电路
牛牛题。计数是困难的，考虑转为期望，之后有一个简单的
的树形 DP，可是显然过不了。我们关注我们真正要求的东西，这个东西可以用 DP 值表示出来。暴力把这个东西展开再合并，就有一个极其简单的 的树形 DP。再把这个东西转成计数，就转化成区间翻转了。时间复杂度 。 E - Mahjong
简单题。容易找到一种生成序列的方式使得它们形成双射，而对生成序列计数是容易的，容斥一下即可，需要暴力计算组合数。
F - Cow Tennis Tournament
哦简单题，我在干什么。考虑正难则反，发现不合法的三元环都满足存在一个点出度为二，于是拿棵线段树维护一下，枚举出度为二的点即可。
G - Dark Horse
牛牛题。转化一下题意，变成对于
个集合，第 个集合大小为 ，每个集合的最小值不属于 的方案数。直接数是困难的，考虑容斥，钦定一些集合的最小值属于 ，考虑如何计算方案数。设 表示已经考虑了 中的前 个元素且 最小值属于 的集合 的集合是 的方案数，那么我们只需要求出 。考虑转移，若当前元素不是最小值那就直接转，若是最小值，枚举其所在的集合，那么我们要从大于当前元素的未被选的数中选若干个数，于是把 从大到小排序即可。
其他
NOISG(CN) 2026 Prelim
ABC 都是唐，那么为何我花了那么久呢。
D 是动态直径板子，且 MX 集训的时候也做过板子，那我怎么不会呢。Solution。
E 并非困难，被 wmr 评了黑，怎么会是呢。Solution。
Educational Codeforces Round 187
Link。
F - Binary Search with One Swap
实则并非困难。简单分析一下就可以得出每个点对的美丽值，此时分为两部分，其中一部分可以直接差分，另一部分是按子树大小卷一遍。发现直接卷显然是过不了的，注意到不同的子树大小只有
种，所以枚举子树大小即可。时间复杂度 。
晚练
物流运输 (20260225)
对于每个区间预处理出它们路径相同时的最短路，随便 DP 一下即可。
瑰丽华尔兹 (20260226)
随便 DP 一下即可。
- Title: 2026 年 2 月日祭
- Author: Getaway_Car
- Created at : 2026-02-01 00:00:00
- Updated at : 2026-03-07 20:06:25
- Link: https://getawaycar1024.github.io/article/diary/2026/02/
- License: This work is licensed under CC BY-NC-SA 4.0.