2026 刷题记录

# February

# 2.9

来就先切了道 CF985F，注意在第 16 个点会 WA，因为你代码的哈希如果没有取模会造成冲突，可以考虑取模来解决。

接着是 P3065，不难想到把值都扔上 Trie 树，但你会发现贪心是错的，你没法确定字典序。

如：

2
acc
acb

由此发现贪心是错的。

因为会存在优先级的顺序，所以我们可以根据钦定的字符串的每一位置来建图。

具体的，假如说我要求 $m$ 比 $a$ 小，那后面如果出现了一个字符比 $a$ 大，比 $m$ 小，那就不合法。

在图上就是形成了环，由此，跑拓扑序即可。

# 2.10

早上过来先把昨天没做的 P3065 给写了，然后就是听讲。

下午先写了 CF1167F，事实上，你打出暴力后会发现这只和两个点之间的大小关系以及两点之间所在位置的顺序有关，可以考虑把他扔到树状数组上维护即可。

# 2.11

昨晚讲课，没时间写题，先花了一小时把 CF1228E 给写了。

你会发现，我们定义两个数组 f 和 $g$ 分别表示至少有 $i$ 行 $j$ 列不满足要求以及恰好有 $i$ 行 $j$ 列不满足要求。

用二项式反演容斥即可。

下午打了场新春欢乐赛，和 PLH 拿下 rk 7 成为二等奖守门员。

# 2.25

返校第一天，配置环境配置了一个小时。

挑战了一下 AT_abc405_g 发现复杂度带了只 $\log$ 会 TLE 但我们可以考虑分块优化修改时的复杂度，这一点可以优化到 $O(1)$，最终复杂度就去掉 $\log$ 了。

# 2.26

早上把昨天晚上没打出来的的 CF2203E 写了，性质很好想，当已经确定了数字 A 后发现数字 B 的最优策略是在离 A 最近的两个点上，分别计算两点所得的分数，取最大值即是选择 B 的最优方案。

我们可以发现分数的图像存在单谷结构，可以考虑二分或三分来处理，复杂度 $O(n \log^2 n)$

下午先来写图论专题。

先来写 P1948 有一种很巧妙的思路，可以二分答案然后计算是否存在一条路径满足处理后代价 $\le mid$。

对于 check 函数，可以考虑将大小大于 $mid$ 的边记为 1，剩下的记为 0，然后 01BFS 来跑一遍看最短路是否 $\le k$ 即可。

# 2.27

先写了 P10928 思路不难想，可以考虑模拟一遍 Kruskal 的过程即可。

但我 RE 了。

原因是在排序的时候把 w<wl 写成了 w<=wl 。

接着就是 P10929 不难想到跑完一遍 dij 之后可以考虑维护每个点都可以由哪个点转移过来，再根据乘法原理乘起来即可。

在第 3 节上课前把 P10931 给过了。

事实上是个很好的树上差分问题，可以考虑定义 $f_i$ 表示 $i$ 的子树内有多少条边连向了另一块树上，只需每次访问到一个附加边时把 $f_u$ 和 $f_v$ 加上 1，他们的 $lca$ 减去 2 即可。

回来改了一下 HDU4578 放假前留的题。

我们可以考虑重载信息（info）和懒标记（tag）这样方便后续操作。

剩下就是细节问题，错就错在处理 info 合并时没有把区间长度和端点考虑进去。

# March

# 3.2

花了快一上午的时间解决 P3008 明知不能用 SPFA 作死获得了 88pts 的好成绩。

事实上，我们可以考虑用并查集缩点来优化，然后根据拓扑序来跑 dij 由此，复杂度降下来了。

下午先写了 P2886 我们发现 $T$ 的值很小，可以考虑把输入的点离散化掉。

在考虑后发现如果将题目中的边与边之间的信息转化为矩阵则可以考虑将两个矩阵的信息合并起来，这是个广义矩阵乘法，发现它显然满足结合律，于是可以考虑矩阵快速幂来解决，复杂度 $O(T^3 \log n)$

# 3.3

上午先解决一下 P3629 我们发现，如果不加边，那距离就只能是 $2 \times (n - 1)$。

同理，我们发现新加的边只能通过一次，所以当 $k=1$ 时只需把直径两端连接起来即可，答案是 $2 \times n - L1 - 1$。

当 $k=2$ 时，可以考虑将直径上的所有边权赋为 -1 然后再计算一遍直径即可，答案就是 $2 \times n - L1 - L2$。

下午先解决了 P6066，简单题，直接跑欧拉回路即可。

接着是 P3469 发现只需在跑点双的时候记录一下值即可。

# 3.4

【数据删除】

# 3.5

感觉没必要写的就不写了。

写一下 CF1083B，不知道这道 *2000 咋评到蓝的。

一个很直接的思路就是枚举第 $i$ 号位所在的状态，如果说出现不同，将累加系数 $\times 2$，但你过不去第 3 个样例。

再次思考发现就是要求在一颗 Trie 树上每一层的节点 $\le k$ 的情况下最大化节点数量。

这似乎好求，可以考虑记录前 $i$ 个所做出的前缀总数，在每一访问到一个 $i$ 时，之前的前缀都可以选择 $a$ 或 $b$，但如果说：

• $s_i=b$
• $t_i=a$

那方案数需要减一。

# 3.6

和 Danielcdo 打了场 duel 被爆杀了。

来写写 CF208E。

我们把题目拆成两个部分：

• 求出 $v_i$ 的 $p_i$ 级祖先
• 求出祖先的 $p_i$ 级子孙的数量

我们发现对于问题一是容易的，简单 $lca$ 即可。

思考问题二发现，目的只是在于祖先的字树内，这启示我们可以考虑结合 $dfn$ 序来考虑，我们只需考虑深度为 $v_i$ 的深度的点是否在祖先的 $dfn$ 序包含内，这其实只需按他们的 $dfs$ 序排列即可，最后可以二分解决。

# 3.9

【数据删除】

# 3.10

尝试一下 P1600，原来是树上差分吗。

发现对于最短路径 $(u,v)$ 我们可以考虑分类讨论。

对于 $(u,lca(u,v))$ 只需判断是否满足 $dep_u=dep_i+w_i$ 其中 $i$ 是路径上的点。

$(lca(u,v),v)$ 同理。

# 3.11

开 P4556，树上差分是好想的，主要是考虑区间最值的问题，这只需加上线段树合并即可。

# 3.12-3.15

【数据删除】

# 3.16

转眼间有好久没记了。

调了半天的 P1120 远古剪枝题，当时好像是因为一个地方剪枝剪错了挂到了 78pts。

最后是有一步卡常的，在 Linux 下可以使用 getchar_unlocked() 和 putchar_unlocked() ，以及逻辑运算符是比位运算要慢的。

# 3.17

昨晚打了场 Edu188 虽说没有上一场 2168 的 perf 那么恐怖，但还是有 1783，能涨就行。

# 3.18

想了半天的 P10930 发现只会操作一、三，看了下蓝书这才知道这个神仙结论。

我们发现对于点集 $S$ 可以考虑对于按照它们的 dfn 序来排列，这样只需计算两点之间的距离即可，这里可以用线段树二分或 set 维护。

# 3.19

【数据删除】

# 3.20

调 P4381 就调了一下午。

事实上而言，这就是个基环树直径的板子，但我为何唐到判环都判错了的，最后写了拓扑才过。

# 3.23

改 P1084 最后一步贪心错了，调了 1 天。

首先要求最大值最小化，容易想到是二分答案。

二分一个 $mid$ 表示要求在总移动最大值 $\le mid$ 的情况下是否满足要求。

先判断哪些军队在时间 $mid$ 内能冲到根的儿子，再用 DFS 标出哪些根儿子子树已经被内部军队封住，最后按 “最小自留、本地优先、剩余时间大的去补外部缺口” 做贪心即可。

似乎这个图论专题写了一个多月了还没写完。

# 3.24

【数据删除】

# 3.25

挑战一波 P5633 & UVA1537，然后成功挑战失败。

我们发现这两道题是类似的，都是在要求根节点的度数 $\le$ 或 $= k$。

对于这一点，我们可以考虑先在与根节点有连边的子树内先跑一遍最小生成树，然后考虑能与根连边的点与根节点之间是否连边。

对此，可以先连上处理好的森林的根与根节点的边，然后考虑每个森林内部能与根连边的点与根连边的长度与原来森林里最长的边的长度，答案减去原长，加上新长即可。

# 3.26

学了一下权值二分，做了 P2619。

说实话，这个算法是有点玄学的，对于此算法，主要形式就是要满足一个限制条件（最多 / 最少 / 恰好要满足选择 $p$ 个值），同时还需定义 $f_i$ 表示在每一个点连接时需付出 $k$ 的代价时，选择 $i$ 个值的最大 / 小值（也可以理解为枚举一个斜率 $k$，选择 $i$ 个值的最大 / 小截距）。

我们构造此类图像的目的就是为了使 $p$ 作为某一种的 $k$ 为代价时的最优点（即凸顶），这样会发现 $f_k$ 的值是可以很快求出来的，这一般只需贪心、DP 等亦或是其他题目需要的算法。

又因为这个算法是以根据图像做切线时的截距大小为核心的，所以需要考虑对于 $\Delta f_i$ 具有单调性，即这时候就要求 $f_i$ 的函数图像是一个凸包。

对于 P2619，这里需要满足白色的边的数量要恰好为 $k$。

这里发现对于在原先跑出来的最小生成树一定是最小的，而往它内部加边或者删边对它增加的值一定单调上升。

这满足了 $\Delta f_i$ 有单调性，所以可以考虑权值二分，中间的 check 函数只需跑一遍最小生成树即可。

通过 600 祭。

# 3.27

【数据删除】

# 3.28

刚写的日志被【数据删除】了，这个故事提醒我们写一段保存一段。

早上过来依旧专题起手，看了看 P10953，似乎需要处理一下边双，但我好像忘了，上 oi-wiki 看会儿。

发现对于同一个边双里的点，答案就是 0，而对于不同边双里的两个点，答案就是 $dis_u + dis_v -2 \times dis_{lca(u,v)}$。

# 3.30

改了一天的题，直接【数据删除】。

# 3.31

把 3.29 的晚练给改了，把 CF2211C2 的题解 给交了上去，为什么除了我以外的题解全是 DSU 啊，这不是一个简单的模拟黄题吗？

依旧改题，【数据删除】。

# April

# 4.1

尝试一下 P4819 发现这题似乎缩个点统计一下入度就完了，然后获得了 30pts。

仔细思考后（事实上是翻了翻讨论区），发现一组这样的 hack：

4 3
1 2
3 2
3 4

我们发现最后是不用找 $1$ 号点的，处理一下即可，这哪来的紫。

# 4.2

早上被拉去 Test JDScript0117 出的 CF div 1+2 然后被 C 创飞了（虽然最后还是切了，但没时间写 D 了）。

下午过来先写了 P2860 又是唐题，又是边双。

我们只需处理出边双缩点之后的叶子结点的数量 $x$，答案就是 $\lceil \frac {x} {2} \rceil$，注意处理一下重边即可。

又写了一下 P10947，一个挺板的最短路计数和严格次短路，一个 dij 解决。

# 4.7

写了一天的 DSU，啥权值 DSU ，扩展域 DSU 快吐了。

接着来试试 P10463 发现这似乎需要用到辗转相除法，翻了翻蓝书才知道 $\gcd x,y,z$ 就等于 $\gcd x,y-x,z-y$ 这提示我们可以使用差分来实现一个区间查，单点修的线段树，维护 $(l,r)$ 内的 $\gcd$ 的大小，最后查询时只需输出 $\gcd a_l,query(l+1,r)$ 即可，仍需拿一个树状数组维护一下每个数的值即可。

# 4.8-4.13

【数据删除】

# 4.14

昨晚打了 CF2220 差点掉惨，最后 12 秒切 D1、D2，B 没写出来。

早上过来先把晚练总结补上，再写了 CF2220D2 的题解（后来删了）。

# 4.15

早上过来先把 CF2220E/CF2219C 用贪心写了，然后写了 题解。

下午开始刷专题，先把 P10590 & CF198E 给写了。

这两道题最开始想了一种要用线段树 + 树状数组维护的一个东西，打一半的时候发现，数据比较小，可以用分块解决。

发现这道题其实是个二维偏序的题，最后转化为求满足 $len_i \le r_x$ 且 $w_i \le p_x$ 的所有未访问值，加入到队列中。

对于这，我们考虑先对每个点按照 $w_i$ 从大往小排序，然后分块，在每个块的内部再按照 $len_i$ 排序即可，剩下的就很板了。

# 4.16

早上复习了一下联通分量，太久没写容易忘掉（主要是点双），又切了板子，用 struct 封装一下。

下午补一下图论剩余的题（其实只有两道），但还是留下了一道圆方树，但把 P3533 给切了。

我们发现这很明显是一颗内向基环树，考虑先用拓扑求出环的位置，视每个环上的的点为根，形成一个森林。

发现查询的点如果在同一颗树内，这就是个 lca 的板子，这里不做讨论。

如果这两个点不在同一个联通分量里，那直接用并查集判掉就好；如果在，先让他们跳到各自的根，预处理出这个环上的顺序，考虑一下是从 $x$ 到 $y$ 还是从 $y$ 到 $x$ 即可。

有理由怀疑这个出题人不想写 SPJ 才给的这么多约束条件。

你谷终于上题了，把 CF2220E/CF2219C 题解 扔了上去，为什么有人认为这题评紫啊，不理解。

# 4.17

【数据删除】

# 4.18

上午来接着刷专题，先做了 P1494，莫队的板子，简单维护一下发现答案的统计是显然的，用新的值减去旧的值即可，再写个 gcd 就完了。