CF Educational Round 53

A. Diverse Substring

某arc原题,原题的范围还是$1e5$。

直接判断$s[i]$和$s[i-1]$是否不同即可。

也可直接$O(n^2 \times 26)$大暴力。

B. Vasya and Books

简单题

C. Vasya and Robot

判断奇偶性以后,二分+前缀和。

D. Berland Fair

暴力统计有几个数满足条件,然后$O(n)$扫一遍。

因为$T$只会被膜$log$次,复杂度$O(nlogT)$。

E. Segment Sum

数位DP,用状压实现,注意前导零的贡献不能统计。

如果算数的和,其实可以带着算一下满足条件的个数就好了。

F. Choosing Two Paths

如图,如果找出两个点(红点和蓝点),设红到蓝之间的部分为公共部分。

剩下的部分就是这两个点的最长链和次长链的组成,这部分可以dfs的时候处理。

满足条件的红点和蓝点要求度数大于等于3。

根据题目中要求公共部分越长越好,那么可以类似找直径的过程,先从1号点dfs一次找到最远点,然后从最远点dfs找到另外一个点。

G. Yet Another LCP Problem

同bzoj3879 SvT。

SAM+虚树DP 或者是SA+单调栈。(我只会前者)

有一个不同点是有这个题两个集合。

那么在DP的时候维护两个点子树中的a关键点和b关键点的数量即可。

Leave a Reply

Your email address will not be published. Required fields are marked *