寒假做题计划
2026-02-13 13:57:06
发布于:广东
Difficulty 前面是个人认为的综合难度,为 的数,难度越高数越大, 大概分别对应洛谷黄绿蓝紫黑。
后面的是个人思维难度,纯主观梦到那个评哪个。
但是题目顺序是按后面那个思维难度排的(
Solved
A85660 【模板】线段树分治 / 动态图连通性(离线)
Difficulty:5.3 / Template
Tag:线段树分治,可撤销并查集
我们画一条时间轴,所有边的存在时间都可看做一个区间。我们建一颗线段树,把每个区间分成 个小区间。发现这些小区间之间有这样一个关系:要么互不相关,要么包含。
我们从 开始递归左右子树,会发现最先结束的边一定是最后加的边,所以可以用可撤销并查集完成。
P1903 数颜色
Difficulty:5.7 / Template
Tag:莫队
带修莫队板子题。。
https://www.luogu.com.cn/record/262419890
最慢点成功跑过 @jodio9(
。
P2617 Dynamic Rankings
Difficulty:6.3 / Template
Tag:整体二分
思想就是对答案二分。
把所有答案在区间 的询问,修改的值在 的操作放一块处理,看看有多少答案在区间 ,多少在区间 。树状数组即可。
还有 std::stable_partition 太好用了你知道吗。
。
ARC214A 构造路径总和相同的方格图
Difficulty:3- / Easy
Tag:构造
先讲构造方法。只需要构造右上 左下的数相同即可。如果这种方法构造不出来那就不可能实现。
证明:
首先如果想要 只有一个值,那 每一个格子的值都得确定。这很显然吧,赛时没想出来。
所以每个格不管往上或往左倒推, 前面那一格的值都得相等。所以一直这么推就能发现如果两个格子到 曼哈顿距离相等,那它们的值也得相等。
然后分层就能 构造了。
A21061 / P1638 逛画展
Difficulty:3.2 / Easy
Tag:-
老师上课的时候提到的,偷偷摸鱼切了(
无脑双指针即可,不需要讲吧。
。
诶等等这节课不是讲莫队吗,我写这个干嘛。
P8767 冰山
Difficulty:3.7 / Easy
Tag:-
从 wcqk 和优先队列的提单里偷来的。
这题真有蓝吗。
注意到可以加个偏移代替整体加。
又注意到每次操作最多只会添加三种长度,所以可以暴力。
然后随便写写就行了。
在每次操作结束后取模应该也不会爆吧。
。
A21758 / P4396 作业
Difficulty:6.1 / Easy+
Tag:莫队
?!原来莫队还能这么用么这能还队莫来原!?
假设 同阶。
显然第二个查询就是不算重复元素,考虑莫队。显然可以 单点增删 查询。这样是 的。
但是注意到莫队这个神奇算法增删元素与查询的次数是不一样的,增删元素的次数是查询次数的 倍!所以搭配莫队的最佳数据结构其实是 增删 查询,这样整体还是 !
分块即可做到这一点。
A93227 / P2680 运输计划(1.3s)
Difficulty:5.8 6.3 / Easy+
Tag:线段树合并
这个之前口胡过了。
首先思考暴力怎么做。显然可以枚举每一条边,然后枚举每条路径,如果路径经过这条边,则将长度减去边权;否则不变,求最大值。这样是 的。
我们可以对每条边的答案拆分成“路径上包括这条边的长度最大值”与“路径中不包括这条边的长度最大值”。可以树剖 完成,还是太劣了。
注意到可以记录所有的查询,然后减去包括这条边的查询就是不包括这条边的查询了。如果有这两颗线段树,可以 完成。
然后线段树合并就可以了。
。
A93111 远行
不知道我的做法会不会假没假。
Difficulty:4.9 / Medium-
Tag:LCA,启发式合并,树的直径
显然题目指的就是会连成一个森林。
首先考虑静态树如何查询。
显然,离一个点最远的点是树任意一个直径的两端点。所以找到直径两端点然后 LCA 即可 。
然后考虑讲一个点加入树后,直径有何变化。根据上面的结论,直径要么不变,要么一端变为这个点。
所以我们合并时大小小的树逐个加入到大小大的点即可。
。
A92146 / P4688 掉进兔子洞
Difficulty:6.5 / Medium
Tag:莫队,bitset
查询三个区间,看似需要维护 个坐标,。实则不然。
我们可以将三个区间拆开来处理,变成 个询问。
但是这个时候询问顺序就打乱了,同一次询问的区间在不同的时间出现,怎么得到答案呢?
答案是通过 bitset 暴力记录下当前的信息,然后将同一次询问的信息按位与即可。
这样就做到了 了。
但空间也是 开不下啊。
可以将查询分成 组处理,只需要保证 能开的下就行。这时时间复杂度就是 了。挺宽松的,不需要卡常。
Dn't Solve Yet
P5906 【模板】回滚莫队
Difficulty:5.6 / Template
Tag:莫队
不知道啊,还没看呢,难度是蒙的。
P14312 【模板】K-D Tree
Difficulty:6.2 / Template
Tag:K-D Tree
没做喵。
P6082 salesman
Difficulty:4.1 / Easy
Tag:-
从 lbc 那偷来的。
这不直接做吗。先递归子树,然后拿子树最大收益就行了。
。
A93082 / P11833 推箱子
Difficulty:5.1 / Easy
Tag:线段树
你说得对,但是这不是反悔贪心,所有任务都需要完成,所以显然要先解决时间少的。
注意到先后顺序不变,所以第 个箱子位置一定是第 小,线段树二分即可找到。
推的过程也很显然,线段树二分+区间改即可。
其实有更简单的方法:先给第 个箱子加上偏移 。这样就允许箱子重合了,查询区间有多少个箱子即可。
。
A93110 Jewel Thief
Difficulty:???/ (Medium+~Hard)
Tag:DP,???
不会 qwq。
P11421 最大匹配 2
Difficulty:??? / (Medium~Hard)
Tag:???
从 lbc 那偷来的。 先挂这里,到时候再看。
A92616 / P14636 清仓甩卖
Difficulty:6.4 / Hard-
Tag:贪心,计数
没做。
A101467 / P11831 追忆
Difficulty:7+ / Hard
Tag:bitset,定期重构,数据结构
没做。
全部评论 15
d
2026-02-02 来自 广东
1666
2026-02-02 来自 浙江
1
做这么多了
2026-02-01 来自 浙江
1就做了一题
2026-02-01 来自 广东
1早上看还很多没写呢,可能是看错了
2026-02-01 来自 浙江
1
代码一个没打(
2026-02-01 来自 广东
1d
2026-02-01 来自 广东
1我也要写寒假做题计划吗
1周前 来自 重庆
0d
2026-02-06 来自 广东
0(震惊)线段树分治模板后面居然还跟着一个二分图
(震惊)线段树分治模板居然是蓝题2026-02-03 来自 广东
0你要不看看线段树分治讲的是啥(
2026-02-03 来自 广东
0没时间全看完
2026-02-03 来自 广东
0简单来说就是先离线,然后按时间建立一个线段树,然后递归时间区间
2026-02-03 来自 广东
0
回滚虚高了回滚4.5左右吧
2026-02-02 来自 广东
0?莫队不就蓝了吗
2026-02-02 来自 广东
0莫队也虚高(大悟)
2026-02-03 来自 广东
0其实本来就是
2026-02-03 来自 广东
0
目前切了0道黑(
2026-02-02 来自 广东
0记得我往做题计划里塞了追忆和其它经典黑题但是没做
2026-02-02 来自 广东
0太好了有可撤并哦哦哦我要学
2026-02-02 来自 广东
0原来线段树分治也有模板题,这必须切一下
但是如果CDQ能做就CDQ吧2026-02-02 来自 广东
0ddd
2026-02-02 来自 四川
0顶顶顶
2026-02-02 来自 浙江
0寒假c题计划,你只要写我就敢c(((
2026-02-01 来自 浙江
0


2026-02-01 来自 广东
0?
2026-02-01 来自 江西
0子涵你昨天和我单挑下手怎么那么狠呜呜呜我晚上不要和你睡了

2026-02-01 来自 广东
1







































有帮助,赞一个