亟隐

朝不闻道,夕亦死可矣

05/28
21:22
算法区

Codeforces Round #305 (Div. 1)

地址:戳这里

A:从H1到A1不会超过m次,枚举即可,H2也一样。然后就得考虑A1和A2可能不会经过若干次操作后变回本身。否则A1变成A1不会超过m次,也可以枚举。

B:重点是求出每个数左边和右边最大的连续不存在小于本身的数的区间。将每个数排序,然后从大到小处理,每次合并左边右边相邻的已经处理过的数的所在区间,用并查集维护。

C:每个数的约数不会超过200,暴力处理出来。添加或者删除一个数只需要处理非互质的数有多少,这里用容斥或者直接用莫比乌斯函数都可以。

D:如果存在一个环,使得每个点都连接一条横边和一条竖边,也就是每个点都是转折点,那么可以相邻的涂成不同颜色,这样环内每个点对行列共享的不同的颜色都是一样的。去掉全部环后只剩下链,相邻的不同颜色就可以。关键在于如何找环,可以每个点随意连接最多一条横边和最多一条竖边,每个联通块只能一条链或者一个简单环,相邻不同色即可。

E:有个简单粗暴代码略长的做法。首先拼接字符串然后跑一遍sa,每次查询call(i,k)的时候,先通过rank[]找出第k个字符串在sa[]的位置,向两边分别二分使得前缀都为这个字符串,得出区间[l,r]。答案即为在这[l,r]内每个sa[]后缀所属的字符串序号在询问字符串区间之间的数目。可以得出sa[]后根据每个位置的所属字符串编号建一颗主席树,每次二分得出区间[l,r]就直接在主席树统计。作为E这题还是太水了,套上两个模板就能A了,复杂度O(nlogn),不过正解并非这个。

A~D代码:戳这里 , E题:戳这里