2021.09.08模拟赛

回首向来萧瑟处，归去，也无风雨也无晴

2021.09.08模拟赛

手速场

A.a

a

因为 $n$ 非常小，考虑 $O(n^2)$ 枚举上下边界

然后钦定右端点为 $j$ 双指针维护当前能构成 $[l,r]$ 的左右边界即可

$O(n^2m)$

code

B.b

b

枚举 $\gcd$ 设 $f_i$ 表示 $\gcd = i | d$ 的方案数

显然 $f_i=\prod(cnt_{j,i}+1)-1$

$cnt_{j,i}$ 表示第 $j$ 个序列 $i$ 的倍数的个数

$-1$ 减去了空集

莫比乌斯反演即可

$O(nm\ln w)$

code

C.朝圣

朝圣

DAG 上大力 dp 即可

$O(nL)$

code

D.合并集合

合并集合

复制两倍断环成链然后区间 DP 即可

$O(2^3n^3)$

code

E.苹果树

苹果树

删边的弱化版

考虑一个树边和某一个非树边一同删去导致不连通要么是这个树边仅被这一个非树边覆盖，或者没被覆盖

所以没被覆盖的边贡献 $m$ ，所有仅被覆盖一次的树边贡献 $1$

code

F.d

d

枚举 $m$ 个删除里多少个删最小的 $a_i$ ，剩下的删最小的 $b_i$ 即可

code