Contest: AtCoder Beginner Contest 223(ABC223)

tony102

2021 年 10 月 19 日

2151 次浏览

1 条评论

1173字数

总结比赛记录

被自己蠢哭了

## A

不解释

## B

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

## C

搞心态了

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

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

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

## D

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

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

## E

题解写的真好：[sol](https://atcoder.jp/contests/abc223/editorial/2801)

## 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](https://atcoder.jp/contests/abc223/submissions/26680137)

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

代码：[Sol](https://atcoder.jp/contests/abc223/submissions/26680428)

最后修改：2021 年 10 月 23 日