被自己蠢哭了
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
1 条评论
我C也被卡精度了。。