被自己蠢哭了

A

不解释

B

蠢哭了,还需要什么最小表示法...直接暴力转出来排序即可。

C

搞心态了

先试着前后同时跳,然后跳到一个地方停。然而非常难写。

然后开始二分时间,发现精度根本不够。

然后发现停的时间直接算出来,只要遍历每一段看是跳完还是跳剩下的时间能跳多少,然后顺便计算路程即可。

D

一个数要在另一个数之前在排列中出现,这样就是拓扑排序确定出现次数吧..

要求字典序最小的话就优先队列就可以了。

E

题解写的真好:sol

F

这个 F 不比 E 简单?

转成一个括号序列了之后,相当于每次交换两个括号就是单点修改,询问就是检查该区间每一个前缀和是否 $> 0$ 并且区间和 $=0$ 。然后我 SB 地写了一个暴力线段树每次进叶节点算前缀...

其实只需要改成线段树维护前缀和就行了...

G

感觉又是一个换根 DP,但是还是先考虑一下对每个点做一下的普通 DP 吧。

设 $f_{u,0/1}$ 表示以 $u$ 为根的子树的最大匹配,且 $0/1$ 分别表示 $fa_u \to u$ 这条边选还是不选。

转移:$f_{u,0} = \sum\limits_{v \in son_u} \max {(f_{v,0}, f_{v,1})}$, $f_{u,1} = \sum\limits_{v \in son_u} \max {(f_{v,0}, f_{v,1})} + [\exists v \in son_u f_{v,1} \geq f_{v,0}]$

换根即可。

H

不是题解做法。首先有一个暴力,用一棵线段树,每一个节点就维护对应区间的线性基,每次询问就把覆盖区间点的线性基合并即可。这样的可以过 $5 \times 10^4$ 的数据 (时限有 3s) ,复杂度:$O(60(n + q) \log n)$ 代码:Brute

但是对于每一组询问都查一遍区间,其实很有冗余。比如说一个区间对应的线性基,其实对很多组覆盖这个区间的询问都要贡献。但是每次合并都很浪费,我们考虑把询问插到一棵线段树上后,可以通过计算这个区间的前后缀线性基并,然后离线回答。

代码:Sol

最后修改:2021 年 10 月 23 日
如果觉得我的文章对你有用,请随意赞赏