目前来看,这大概是我最后一次打巅峰赛了。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
A
Difficulty:3- / Easy
Tag:-
糖丸了。删边看成删点然后写了神秘拓扑。如此视力,如何省选?
注意到树上割任意一条边一定会分成两个子树。所以答案只能是 max{0,k−1}\max\{0,k-1\}max{0,k−1}。
时间复杂度:O(m)O(m)O(m)。
B
不到啊,没调出来。
C
Difficulty:3- / Easy
显然这个就是让我们求最长合法括号子序列。贪心选就行了。
时间复杂度:O(n)O(n)O(n)。
D
Difficulty:3.8 / Easy+
Tag:双堆
好题。
先离散化一下。
注意到题目可以转化成 nnn 次区间 +1+1+1,可以删除不超过 kkk 个区间,求序列 max\maxmax 最小值。
遇到最小化最大值的,显然二分答案,转化成让序列 max\maxmax 不超过 xxx 的最小删除区间数量。
然后有个显然的贪心,枚举当前时刻,如果当前的所在区间超过 xxx 个,则按区间结束位置从大到小删除。感性理解证明不难。
现在我们需要一个数据结构支持单点增删求最大 / 最小值。显然可以 set。
但是 2log 还是太考验常数了,set 估计卡不过去。所以:
我们可以用双堆维护这个操作。具体实现看代码。
时间复杂度:O(nlog2n)O(n\log^2 n)O(nlog2n)。
E
Difficulty:3- / Easy
Tag:-
贪心,显然修改前面的最优。
时间复杂度:O(nV+∑∣Ai∣)O(nV+\sum |A_i|)O(nV+∑∣Ai ∣)。
F
Difficulty:4.6 / Easy
Tag:MST
考虑按时间建图。我们发现如果 x,yx,yx,y 已经连通,那再连 x→yx\to yx→y 的边是无意义的,可以直接删除。
删完以后发现会连成一个森林。考虑在这个森林中查询。
既然是树,我们会发现只有 x→yx\to yx→y 路径上所有边都连上 x,yx,yx,y 才能连通。所以答案就是路径上所有边的时间的最大值。边转点树剖套 ST 表即可。
时间复杂度:O(mα(n)+nlogn+qlogn)O(m\alpha(n)+n\log n+q\log n)O(mα(n)+nlogn+qlogn)。
F
Difficulty:6.3 / Easy+
Tag:整体二分,并查集
注意到这个查询是可二分的。显然吧。
所以每次二分我们只需要看 [1,k][1,k][1,k] 的边是否能让它们连通。
显然可以整体二分。
我们可以改一下递归顺序,逐层处理。显然每一层只会加 mmm 条边。
搭配并查集即可 O(mlogmα(n)+qlogn)O(m\log m\alpha(n)+q\log n)O(mlogmα(n)+qlogn),常数小。
code:你觉得我会写吗?
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> 目前来看,这大概是我最后一次打巅峰赛了。
这句话的意思是:我在 3/1 22:00 之前打的最后一场巅峰赛大概是这一场,用“大概”是因为题解是在 3/1 12:29 写的所以不能确定 3/1 12:29 - 22:00 这段时间是否还打过其它巅峰赛,体现了这篇题解的严谨性,没有别的意思。/bangbangt