2026 1月 训练记录

· · 个人记录

前情提要

新的一年开始了，看着日历上的年份还感到陌生，训练仍是需要被记录的。

1.1

下午把昨天下午那题过了。一道普通多维线性 DP+前缀和优化，只是昨天状态定义复杂了，不好转移。其实我的做法也还可以把第一维从 30 降到 10（三种括号分别存储，不必计统计总数），导致常数是别人的三倍，但是不管了，还是可以过。

晚上想写下 https://www.luogu.com.cn/problem/UVA1630 。很快就过了，一道很简单的区间 DP，估计真实难度为绿（提交的工单过了）。我直接写的 O(n^4)，本来还以为多测过不了，结果 90ms 直接过了，常数优秀。其实优化也不难，把直接边 DP 边统计方案改为先记录从哪转移最后回溯找方案就可以优化掉一个 n，但是不想写。

1.2

早上起来水了 P5752，把式子化简一下，发现答案只与平方和有关，然后用二维区间 DP（也就是在矩形上 DP）直接解决即可。

晚上想做一下 https://www.luogu.com.cn/problem/UVA10559 。结果想了一会儿发现不会，只会 O(n^4) ，能过弱化版，看题解吧。

1.3

假期结束了，晚上回校打了 abc，开 urt 打了 EF（while 写成 if 调了一个小时）。

1.4

下午写过了 UVA10559。怎么直接 O(Tn^4) 可以过啊，可能 dfs 能省很多时间吧。定义 f_{i,j,0} 表示删除区间 [l,r]，删除方式不限的最大价值。f_{i,j,k} 表示删除区间 [l,r]，并且 r 是和另外 k-1 个相同颜色的块一起删除的，不计算这一部分的价值，其余部分的最大总价值。转移时枚举上一个和 r 一起删除的位置即可。

把 UVA1292 写了，买啥好说的。又把 UVA1222 写了，还是没啥好说的，树形背包 DP 板题，难点甚至在于输入时的字符串处理。又把 P10962 写过了，还是没啥好说的，换根 DP 板子。

晚上切了 P3211，分每一位考虑，倒序计算期望，然后列出转移方程，再转到矩阵中，然后跑一遍高斯消元，时间复杂度 O(logVn^3)。

1.5

早上把 P10963 做了，直接根据题意状压，虽然理论时间复杂度 O(T2^nn^3)，但是由于用递推转移，省略了有很多无用状态，所以常数小于 1。

上午想写下 P7689，结果想了一节课只会超高复杂度做法，不用细想都知道不可行，决定查阅题解。改过来了，还是最优解。这道题的关键在于，我们发现如果只用 0/1 来记录状态的话会非常麻烦，需要记录两行，这样转移时就需枚举三行，虽然剪枝优秀的话还是会省很多时间，但仍然太复杂了。所以考虑再加入 2 来描述状态，我们将填的每一块的每一个部分都钦定一个记录符号，就像下面这样：

1 1 1\\0 0 0 2 2\\1 1\\0 0

这样 DP 就只用记录当前行就能体现整体状况。然后我们从上往下递推转移：如果当前状态当前位置为 1，那么下一行对应位置就是 0；如果当前状态当前位置为 2，那么下一行对应位置就是 1；如果当前状态当前位置为 0，那么下一行对应位置就可以是 0/1/2，注意如果是填 1/2 的话可能会影响后面几个格子填的数，还需要判断这些位置是否可填，然后将方块数量增加一。这个过程可以通过 dfs 实现。这样我们就在放置每个块的第一行时计算了贡献，并且确保放下了完整的块。

这种做法的理论时间复杂度为 O(Tn3^{2m})，但是存在大量的无效状态会在递推转移的过程中忽略，并且 dfs 过程中要么只有一个分支，要么有多个分支但是递归层数会减少，中途也有剪枝，所以实际时间远小于这个。

总结一下：新的 trick：增加进制数更确切的描述状态，减少状态枚举。递推 + dfs剪枝 大量降低运行时间。

下午先写了 SP16809，对顶堆（维护中位数）预处理 + DP，时间复杂度应该是正解，但是 vjudge 上交不了。又把 P2569 切了，直接根据题意模拟 DP，啥性质也不用找，然后单调队列优化一下就完了。

晚上做 P10965，我怎么突然不会最大 01 矩阵了？看了眼以前做的题才想起来。我们不用枚举矩形的右下角，只用枚举矩形的最下面的一行在哪，然后枚举矩形最高的位置 h_i，计左边第一个比它小的是 L，右边是 R，用 h_i\times(R-L-1) 更新答案即可，时间复杂度 O(nm)。

P4746 是 SP16809 的弱化版，直接交了。又把 UVA1640 做了，简单数位 DP，没啥说的。感觉今天做题量已经超标了，但是这个专题还剩最后一道题：P10968，开始思考。

1.6

上午把 P10968 写了。昨晚初看题还觉得很难，今天一早重新思考，发现按照数字大小插入序列进行 DP 即可，决定写一篇题解。

然后把 P10961 写了，简单 DP 优化，本来还想 bitset 闯过，结果失败了。

下午把 P10964 写了，线段树颜色均摊优化 DP，比较板。发现自己不会 P4954，显然不能直接 DP，需要先发现结论，但是始终找不到什么关键信息，决定看题解。改出来了，代码极短，但是思维还是有紫的，以下是总结：

首先引出这道题的王牌结论：对于同一些草包，在所有堆叠方案中，高度最高的方案一定最下面一层大小最小。因此，局部最优解就是全局最优解。考虑 DP，我们先将 a 翻转过来，直接定义 f_i 表示前 i 个能分出的最大层数，g_i 表示此时最下面一层的大小。转移显而易见，设 j 为最优决策点：

f_i=f_j+1\\g_i=s_i-s_j\\ 1\le j<i\space \space g_j\le s_i-s_j

直接做是 O(n^2) 的，考虑优化。移项：g_j+s_j\le s_i。我们发现 s_i 和 f_i 都具有单调性，因此当 k<j 且 g_k+s_k\ge g_j+s_j 时 k 这个决策点可以直接删除，剩下的元素一定满足 g_j+s_j 时单调递增的，最有决策就是最后一个满足 g_j+s_j\le s_i 的 j。由于 s_i 单调递增且决策集合时刻满足单调性，因此可以用单调队列维护，时间复杂度 O(n)。这道题的关键在于：发现结论，列出 DP，通过单调性找到优化方法。

关于结论，以下是引用一个陌生大佬的证明： 任意取出一个能使层数最高的方案，设有 n 层，把其中从下往上每一层最大的块编号记为 A_i；任取一个能使底边最短的方案，设有 m 层，把其中从下往上每一层最大的块编号记为 B_i。 显然 A_1\le B_1，A_m\le B_m，这说明至少存在一个 k∈(1,m)，满足 A_{k-1}\ge B_{k-1} 且 A_k\le B_k。 也就是说，方案 A 第 k 层完全被方案 B 第 k 层包含。构造一个新方案，第 k 层往上按方案 A，往下按方案 B， 两边都不要的块放中间当第 k 层。 新方案的层数与 A 相同，而底边长度与 B 相同。证毕。

构造法证明太强了，显然考试无法证出来，只有猜出结论。我觉得只有多手模，多尝试猜测，多练习 CF 类似的猜结论直觉才可能做出。

晚上把 P4767 过了，就是弱化版再加一个最板的四边形不等式优化。关键在于发现区间中位数距离和满足四边形不等式，这可以通过分讨奇偶性证明，这里不证了。马上下课了，还是看一下 P10966 吧。

1.7

上午把 P10966 写了，比较板，由于四边形不等式写得更熟练些，所以写的四边形不等式。还有一种斜率优化的方法，可以 O(n) 解决，也不难，就是化简式子。很快把 P3628 切了，很板的斜率优化，不用推任何结论，根据题意列方程，然后推式子，就变成了斜优板子，可以 O(n) 解决。

下午切了 CF1129D，自己切的 CF 2900* ！！！感觉有点进步。先用扫描线，然后修改和查询再用分块维护，其中查询整块需要排序和二分，所以时间复杂度为 O(n \sqrt n \log n)，极限通过！

1.8

昨天晚上打 CF 了。差点调出 D2 掉分了，今天早上很快改出来了。上午还把 E 改了。一开始一直找不到突破口，看了眼题解才发现。又是 CF 比赛的常态：神秘性质+简单算法。具体突破口见 CF 官方题解，关键在于通分合并，转化为 gcd，利用 gcd 的性质：gcd(a,b)\le a-b 发现最终值小于等于 1，所以只有取等，然后 n^2 定义 DP，枚举因数进行转移即可。

晚上把 CF2173F 写了。不知道区间长度小于 \sqrt n 的情况怎么做，看了眼题解立马知道了。直接从 1 到 \sqrt n 枚举区间长度，然后二分有多少个，时间复杂度 O(n \sqrt n \log n)。

1.9

今天写了 P11833，去年省选，上午两节课才想到做法（假了两次），下午三节课才写+调出来（太难调了），写了坨 200 行屎山，怎么感觉这道蓝做的时间已经超过了大部分紫题？

晚上 20 分钟把 P11536 切了，历史最快紫（虽然难度显然不到）。本来想水篇题解的，结果交不了了（果然题太水了）。很套路：列式子->ds 维护。然后把 P2163 切了，小容斥+离线二维数点，没什么说的。

1.10

这天被三场线上比赛挤满了。

上午是耻辱场，第一次打 USACO，结果铜组没 ak，被 Ad-hoc B 创飞了，我太菜了！要是没晋级岂不成小丑了？

下午是猎奇场，我不知道为什么自己会去打个洛谷月赛（可能是上午发挥不好精神失常），T1T2 快速水过了，T3 乱搞，不知道哪错了也不知道为什么是对的，反正被捆绑创成了 39 分。T4 也是神题，本想暴力打个 8 分跑路，写的哈希+ dfs，使劲优化+特殊性质，搞到了 44 分。好久没打过洛谷比赛了，等级分一整年没变过了，这回会涨吧。

晚上是雪耻场，abc 从开始就聚精会神，没看过榜单。过了 F 后去看震惊的发现进了 rk100！最后 rk83，表现分 2400，rating +109。然后水了篇 F 题解，等洛谷搬题。

1.11

晚上返校把 ARC180D 切了（其实上周就想到思路了）。一开始一直在想拆贡献+扫描线，结果由于多查询所以不可做。后来想到了答案有关最大值的性质，然后想到用线段树+单调栈维护，然后就解决了，时间复杂度 O(n \log n)。本来想写篇题解，结果又交满了，悲。

1.12

昨晚打了 arc，不会 C，今天早上改过并写了题解。关键在于先从绝对值的性质下手，转化贡献计算方法，然后将式子赋予实际意义，再通过插板法计算组合数解决。

下午切了 CF1996G，首先断环成连，枚举从那一条边断开，这样每一条限制就变成了固定的区间，答案就是区间并集大小。优化就列出不等式，转化成二维扫描线，用线段树维护即可，时间复杂度 O(m\log n)。

晚上学习了线段树分治，并写了 P5787。线段树分治与线段树有很大区别，它不用维护什么区间信息，写没有什么修改查询，它只是利用了线段树的二分结构，减少递归层数。在时间轴上建立线段树，可以离线解决像这种在某时刻出现又在某时刻消失的问题。

例如这道题，我们把每条边的出现分配在时间轴线段树上，类似于区间修改。然后通过一次递归找到所有答案，当到达一个节点时，加入新边，如果构成了二分图，那么直接将区间内答案全部设为 no，否则继续递归。递归结束回到这个节点时，将在这个节点上建的新边全部撤销，进行回溯。这就是线段树分治的统计答案方法。

此外，这道题还用到了一个新的知识点：带权并查集（又称种类并查集或拓展域并查集），用来判断二分图。也就是将每个点拆为黑形态和白形态，每次建边建两条，黑白相连和白黑相连，这样就维护了点与点之间的黑白关系。当存在一个点满足黑形态和白形态在同一个集合中，那么不是二分图（因为自相矛盾了）。每次建边时判断两端是否矛盾即可（因为两个连通分量内部一定是满足的，所以只要两端不矛盾，那么连起来后的整个大的连通分量也满足）。这里由于有撤销操作，所以不能路径压缩，需要存储真实父亲，这样又导致需要按秩合并，确保高度。所以总时间复杂度为 O(m \log k \log n)。

1.13

上午切了 CF1924B，比较板的线段树区间修区间查。

然后切了 P1856，比较板的扫描线，直接 O(n^2) 都可以过。优化的话其实就是计算连通块个数，使用不下放的懒惰标记+类似于最大子段和的存储和转移方式即可，可以做到 O(n\log n)，不想写了。

下午学习了线段树优化建图，并做了 CF786B。线段树建图主要运用于区间建边的的优化，仍然主要运用线段树的维护区间的结构，将建边区间分成线段树上的 \log n 个单位结点。又由于区间需要与具体节点对应，所以线段树的树边也许建出来。又由于这道题的建边方向不定，所以需要建出两棵线段树，分别处理两种方向。然后对着新图跑 dij 即可，时间复杂度 O(n \log^2 n)。

晚上写了 P3919，主席树板子。这道题关键在于想到主席树，因为从题面中你并不能发现需要维护什么区间信息。但是线段树具有二分结构，能够在 log 的时间复杂度下查询位置答案，并且加上可持久化和动态开点，能在 log 的复杂度下创建新版本。所以什么信息也不需要维护，我们只是利用它的结构存储历史版本，不然难以存储（我试过直接链表，但是太混乱了，而且还无法快速查询，还是主席树结构清晰高效）。本来还想再写一遍模板 2 的，但突然觉得自己已经很熟练了，就算了吧。

1.14

上午三节课单挑 abc414g，最后 AC75，TLE2，MLE2，下午发现做法有问题。不能将两边都拆分成线段树节点然后一一连边，因为线段树查询找到的节点个数只是 log 级别的，可能会达到 2log，所以这样连边一定 MLE。

于是先放下这道题，先去把 CF915E 切了，没什么好说的。然后写了 CF1114F，直接用欧拉函数计算方法加上线段树即可，有点卡常，没思维难度。

1.15

昨天晚上突然想到了那到 abc414g 的优化方法，是我犯唐了，忘了个简单 trick 能优化掉一只 log，今天上午改了一点就过了，写了篇题解（虽然可以卡）。看了下官方题解的做法，很巧妙的做法。利用线段树的树边边权，做差分，左边计算终点到左边最大值的距离，右边计算起点到右边最小值的距离，在加上左边最大值与右边最小值的距离，就能得到起点与终点的距离，作差分的过程中始终大减小，因此边权一定不为负。

下午先切了 CF2147F，虽然又不是正解，但是过了。然后写了篇题解。题解区找这个性质几乎都是在图上找的，原来我把分块改成线段树就是正解啊！还有什么组合数学的方法，不想看了。

晚上学习了猫树分治，然后写了 P6240。猫树分治的结构也是和线段树一样是二分结构，但是线段树每次查询需要合并 \log n 次区间，不能用于解决这种合并复杂度高的题目。我们将查询离线，对于每个节点，只处理跨过中间的询问，其他的由递归左右儿子处理。分有中间为起点，分别向左右端点跑一次 01 背包，这样处理每个询问就只需合并左右背包。又由于背包大小固定，所以合并起来时间复杂度只需 O(V)，总时间复杂度 O(nV\log n+mV+m\log n)。猫树原理与之类似。

1.16

上午三节课和下午两节课终于把 P14528 切了，时间复杂度没问题，就是做复杂了，导致常数巨大，但仍然写了篇题解。哦哦哦，原来第一部分不需要线段树，因为没有动态查询，直接倍增预处理即可，我犯唐了。

晚上先把 P7457 切了，我们发现边权很小，所以直接对每种边权都维护并查集检查连通性，询问时从小到大判断是否连通，再加上线段树分治即可。

1.17

上午模拟赛，由于考的是春测题，我做过原，所以被单独换题了。极限切 T4，运用了才知道的组合意义+树形 DP，导致白天心情一直很好。

现在刚结束 CF，心态临近崩溃，被诈骗了 2 个小时，最后 5 分钟才清醒过来怎么做，又要掉大分了。我试图安慰自己，竞赛就是这样，起起伏伏，要学会克服，视之平常，但情绪仍然很低落，毕竟已经连掉 4 场了。哎！

1.18

晚上写了一晚上的英语报纸。

1.19

早上很快把 CF2190B2 改了，比赛时没有发现答案只能为 0 或 n-2，知道后直接用 DP 根据结构计算即可，时间复杂度 O(n^3)，应该可以优化吧，但是不管了。

然后写了一下午 P9120，由于直接写并集太麻烦了，偷懒写了个容斥，结果被卡常 95 pts，只好面向数据点编程。思维难度有紫，代码难度有黑的一道题。突破口在于观察最小值与最大值所在的行，然后二分答案会 k=3 的情况，接着转到二维，用 ds 维护，就是 k=4 的情况，时间复杂度 O(k^2\log V n \log n)。

1.20

早上继续写 AtCoder-jsc2019_final_h，中途切了 abc441f。

晚上晚练是唐唐 P3092，然后仍然没有调出白天那道题。

1.21

上午写了对拍，然后终于调出来了，写了篇题解。然后写了 P6864，简单矩乘。晚练是 P5664，做过原，直接写了。

1.22

我不会 P3960，太菜了。线段树综合的不看题解记录就这样被打破了。看了一眼就会了。

晚上晚练是 P3953，没切。

1.23

早上改了晚练题。晚上写了 P3960 的代码。没做出来是因为不会维护操作：从序列中拿出一个元素放到最后。我们只需要在这个位置标记为不存在，在最后一个位置标记为存在，然后使用线段树二分查询即可。加上动态开点线段树，这道题的时间复杂度为 O(q\log n)。

1.24

昨晚打了 CF1075，上分了，还差 24 分上紫，早上来把 E 改了，猜结论题。下午写了 CF2183F，二维计数类树形 DP，还好，我甚至还被卡常了几发。

晚上打了 abc，真的越来越无聊了。把 CF2174D 改了，线段树换树状数组，加上了特殊情况，写了篇题解。

1.25

晚练。

1.26

早上改过了市场，线段树综合做完了，开始做图论例题。切了 P1948，二分答案+01bfs。

然后切了 P3008，之前做了一点。很巧妙的一道题，利用无负环、正边无向的性质，先将每个正边连通分量所为一个点，负边跑拓扑，过程中在连通分量内部跑 dij 即可，时间复杂度 O(m\log m)。

然后切了 P2886，最小环模版。注意不能枚举边，只能枚举点。运用 Floyd 的方法，从大到小加点，记录路径即可，时间复杂度 O(n^3)。然后切了 P2886，扩展矩阵乘法，应该属于模版吧。

然后切了 P10928，模拟 kru 算法的过程即可发现结论。然后想 UVA1537，自己想了个构造方法，但觉得可能是假的，感觉正确性不高。看了蓝书，写了出来，本以为会很难调，结果只挂了两发。这里总结一下方法：

首先，发现答案与 0 有关，考虑断开所有与 0 有关的边，使图变成若干连通块。对于每一个连通块，找到它的最小生成树，并从每个连通块中找到最小的一条边连向 0。设连通块个数为 cnt。

此时我们已经构造出了一棵生成树，如果 s=cnt，那么当前方案就是最优的。容易证明连通块内的非树边一定不会用到，即可能新加的边只可能是与 0 相连的边。考虑新加边时，一定会在两点路径上删一条边，贪心可知这条边是最大的。

这样换边策略就出来了，每次换边时枚举每一条可加的边，找到贡献最优的一条，替换。重复执行以上过程，直到度数顶满为止。至于最后一步的贪心，证明复杂，但是很显然。加强版需用 wqs，这道题直接 O(n^3) 就能过。

然后切了 P10929，简单最短路计数。

1.27

昨晚晚练炸了。早上切了水紫 P3629。然后切了 P10931。复习了一下线段树合并，理解了以前对复杂度的疑问。

空间复杂度：观察发现每个树节点会产生一个线段树的根，共有 n 个；update 函数每次调用最多新增 \log V 个，总共调用 m 次；merge 函数不会新增节点。所以，空间复杂度为 O(n+m\log V)。

时间复杂度：update 函数时间复杂度 \log V，调用 m 次；merge 函数若是两边节点均不为空节点，那么递归，调用次数加一，节点数量减一，因此最多递归 O(n+m\log V) 次；若是两边节点存在空节点，那么直接连边，不会继续递归，因此次数不会超过 merge 调用次数。总时间复杂度 O(n+m\log V)。

下午调过了 P1600，结果发现根本不需要用线段树合并，直接差分即可。就当复习了吧。开 P10930，只会劣且暴力的树剖，双 \log。太劣了不想写，看蓝书。

做法是将黑点按 dfn 序排成环，两两之间距离之和就是答案的两倍。为什么呢？蓝书上说“细心的读者可以发现...”。这太水了。

为了解决，我们先看到双倍经验 P3320。我们发现，最优路径一定是以一个黑点为根，然后对所有黑点进行深度优先搜索，经过的总距离就是答案。那么怎么确定经过点的顺序呢，考虑按 dfn 序排序，构成一个环，累加两两之间的距离。但是根节点不同，dfn 序不同怎么办？初始时以 1 为根计算 dfn 序，之后排序时就用这个 dfn 序，容易发现无论以哪一个节点为根排序后的环形都是相同的。维护就很简单了，用 set 维护排序后的序列，增删元素时对应增减贡献即可，两点距离用 lca 计算。再回到本题，我们发现这道题的边集与上述路径相同，只是由于 dfs 时每条边会被计算两遍，所以答案除以二即可。

1.28

上午切了 P1084，昨天题读错了，以为是每条边的两个端点都需有一个检查点。今天重读题后发现倍增部分很简单，难点在于根节点儿子的分配方法，仔细思考贪心策略后解决。总时间复杂度 O(n\log n\log V)。

然后切了 P4381，基环树一眼题。对每课树求直径和最长链，然后对于每棵基环树，在环的位置合并树的最长链可以使用单调队列维护滑动窗口最值。总时间复杂度 O(n)。

切了 P6066，欧拉回路模板。

下午做了 P2868。做之前先学习了分数规划，很简单巧妙的一个 trick。考虑到无法直接计算这种式子的最值：\frac{\sum a_i}{\sum b_i}。考虑二分，判断当前二分出的值 m 是否存在答案满足 \frac{\sum a_i}{\sum b_i}\ge m，即 \sum a_i\ge m\times \sum b_i，即 \sum (m\times b_i-a_i)\le 0。这道题就用这种方式二分，将单权和边权视为整体，这样只要存在负环就存在解。所以只用 spfa 判断是否存在负环即可，如果找到的是回路也没关系，因为负回路上一定存在负环。因此时间复杂度 O(nm\log V)。

然后切了 UVA1723，简单差分约束。复习了下割边割点和欧拉路径。原来求欧拉路径的算法其实很容易理解，就是使用栈的数据结构，不断对一个栈顶节点进行扩充环的过程，由于回溯时才会加这个节点，所以求出来的序列就是倒序的欧拉路径。

1.29

放假了。整天几乎啥都没干。

1.30

昨晚 CF 上紫了。返校了。

1.31

MX NOIP 集训。快速切了 P2801 和 abc174f。然后学习了普通莫队。有意思的算法，平面直角坐标系上走点是一种很好的理解方式。过了板子 abc405G。切了 P4462，板子。晚上写了 P5356，一开始只会 O(n\sqrt{n\log n}\log V) 的暴力双重二分，然后发现不用每次二分答案都处理散块，在二分答案前将散块合并成整块即可，时间复杂度降为 O(n\sqrt n \log V)，可以通过。

1 月结束了。