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 就调了一下午。

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