Difficulty 前面是个人认为的综合难度,为 3∼73\sim 73∼7 的数,难度越高数越大,3,4,5,6,73,4,5,6,73,4,5,6,7 大概分别对应洛谷黄绿蓝紫黑。
后面的是个人思维难度,纯主观梦到那个评哪个。
但是题目顺序是按后面那个思维难度排的(
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
SOLVED
A85660 【模板】线段树分治 / 动态图连通性(离线)
Difficulty:5.3 / Template
Tag:线段树分治,可撤销并查集
我们画一条时间轴,所有边的存在时间都可看做一个区间。我们建一颗线段树,把每个区间分成 O(logq)O(\log q)O(logq) 个小区间。发现这些小区间之间有这样一个关系:要么互不相关,要么包含。
我们从 [1,q][1,q][1,q] 开始递归左右子树,会发现最先结束的边一定是最后加的边,所以可以用可撤销并查集完成。
P1903 数颜色
Difficulty:5.7 / Template
Tag:莫队
带修莫队板子题。O(n5/3)O(n^{5/3})O(n5/3)。
https://www.luogu.com.cn/record/262419890
最慢点成功跑过 @jodio9(
O(qlogqlogn)O(q\log q\log n)O(qlogqlogn)。
P2617 DYNAMIC RANKINGS
Difficulty:6.3 / Template
Tag:整体二分
思想就是对答案二分。
把所有答案在区间 [l,r][l,r][l,r] 的询问,修改的值在 [l,r][l,r][l,r] 的操作放一块处理,看看有多少答案在区间 [l,mid][l,mid][l,mid],多少在区间 [mid+1,r][mid+1,r][mid+1,r]。树状数组即可。
还有 std::stable_partition 太好用了你知道吗。
O(nlog2n)O(n\log^2 n)O(nlog2n)。
ARC214A 构造路径总和相同的方格图
Difficulty:3- / Easy
Tag:构造
先讲构造方法。只需要构造右上 →\rarr→ 左下的数相同即可。如果这种方法构造不出来那就不可能实现。
证明:
首先如果想要 (1,1)→(n,n)(1,1)\rarr (n,n)(1,1)→(n,n) 只有一个值,那 (1,1)→(1,1)\rarr(1,1)→ 每一个格子的值都得确定。这很显然吧,赛时没想出来。
所以每个格不管往上或往左倒推,(1,1)→(1,1)\rarr(1,1)→ 前面那一格的值都得相等。所以一直这么推就能发现如果两个格子到 (1,1)(1,1)(1,1) 曼哈顿距离相等,那它们的值也得相等。
然后分层就能 O(n2)O(n^2)O(n2) 构造了。
A21061 / P1638 逛画展
Difficulty:3.2 / Easy
Tag:-
老师上课的时候提到的,偷偷摸鱼切了(
无脑双指针即可,不需要讲吧。
O(n)O(n)O(n)。
诶等等这节课不是讲莫队吗,我写这个干嘛。
P8767 冰山
Difficulty:3.7 / Easy
Tag:-
从 wcqk 和优先队列的提单里偷来的。
这题真有蓝吗。
注意到可以加个偏移代替整体加。
又注意到每次操作最多只会添加三种长度,所以可以暴力。
然后随便写写就行了。
在每次操作结束后取模应该也不会爆吧。
O(qlogq)O(q\log q)O(qlogq)。
A21758 / P4396 作业
Difficulty:6.1 / Easy+
Tag:莫队
?!原来莫队还能这么用么这能还队莫来原!?
假设 n,q,Vn,q,Vn,q,V 同阶。
显然第二个查询就是不算重复元素,考虑莫队。显然可以 O(logn)O(\log n)O(logn) 单点增删 O(logn)O(\log n)O(logn) 查询。这样是 O(nnlogn)O(n\sqrt n\log n)O(nn logn) 的。
但是注意到莫队这个神奇算法增删元素与查询的次数是不一样的,增删元素的次数是查询次数的 O(n)O(\sqrt n)O(n ) 倍!所以搭配莫队的最佳数据结构其实是 O(1)O(1)O(1) 增删 O(n)O(\sqrt n)O(n ) 查询,这样整体还是 O(nn)O(n\sqrt n)O(nn )!
分块即可做到这一点。
A93227 / P2680 运输计划(1.3S)
Difficulty:5.8 6.3 / Easy+
Tag:线段树合并
这个之前口胡过了。
首先思考暴力怎么做。显然可以枚举每一条边,然后枚举每条路径,如果路径经过这条边,则将长度减去边权;否则不变,求最大值。这样是 O(nmlogn)O(nm\log n)O(nmlogn) 的。
我们可以对每条边的答案拆分成“路径上包括这条边的长度最大值”与“路径中不包括这条边的长度最大值”。可以树剖 O(mlog2n)O(m\log^2 n)O(mlog2n) 完成,还是太劣了。
注意到可以记录所有的查询,然后减去包括这条边的查询就是不包括这条边的查询了。如果有这两颗线段树,可以 O(logm)O(\log m)O(logm) 完成。
然后线段树合并就可以了。
O(mlogm)O(m\log m)O(mlogm)。
A93111 远行
不知道我的做法会不会假没假。
Difficulty:4.9 / Medium-
Tag:LCA,启发式合并,树的直径
显然题目指的就是会连成一个森林。
首先考虑静态树如何查询。
显然,离一个点最远的点是树任意一个直径的两端点。所以找到直径两端点然后 LCA 即可 O(qlogn)O(q\log n)O(qlogn)。
然后考虑讲一个点加入树后,直径有何变化。根据上面的结论,直径要么不变,要么一端变为这个点。
所以我们合并时大小小的树逐个加入到大小大的点即可。
O(nlog2n+qlogn)O(n\log^2 n+q\log n)O(nlog2n+qlogn)。
A92146 / P4688 掉进兔子洞
Difficulty:6.5 / Medium
Tag:莫队,bitset
查询三个区间,看似需要维护 666 个坐标,O(n116)O(n^{\frac{11}{6}})O(n611 )。实则不然。
我们可以将三个区间拆开来处理,变成 3m3m3m 个询问。
但是这个时候询问顺序就打乱了,同一次询问的区间在不同的时间出现,怎么得到答案呢?
答案是通过 bitset 暴力记录下当前的信息,然后将同一次询问的信息按位与即可。
这样就做到了 O(nmw+mm)O(\frac{nm}{w}+m\sqrt m)O(wnm +mm ) 了。
但空间也是 O(nmw)O(\frac{nm}{w})O(wnm ) 开不下啊。
可以将查询分成 kkk 组处理,只需要保证 O(nmkw)O(\frac{nm}{kw})O(kwnm ) 能开的下就行。这时时间复杂度就是 O(nmw+mmk)O(\frac{nm}{w}+m\sqrt{mk})O(wnm +mmk ) 了。挺宽松的,不需要卡常。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
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 那偷来的。
这不直接做吗。先递归子树,然后拿子树最大收益就行了。
O(nlogn)O(n\log n)O(nlogn)。
A93082 / P11833 推箱子
Difficulty:5.1 / Easy
Tag:线段树
你说得对,但是这不是反悔贪心,所有任务都需要完成,所以显然要先解决时间少的。
注意到先后顺序不变,所以第 iii 个箱子位置一定是第 iii 小,线段树二分即可找到。
推的过程也很显然,线段树二分+区间改即可。
其实有更简单的方法:先给第 iii 个箱子加上偏移 i−1i-1i−1。这样就允许箱子重合了,查询区间有多少个箱子即可。
O(nlogV)O(n\log V)O(nlogV)。
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,定期重构,数据结构
没做。