2021.09.15模拟赛

长梦不多时，短梦无碑记，普天下，梦南柯，人似蚁

2021.09.15模拟赛

A. wzoi

wzoi

贪心的考虑，维护一个栈即可

code

B. Divisors

Divisors

非常暴力的把所有的因子分解出来，排序然后统计即可

因为 $10^9$ 内的最多约数只有 $1200$ 左右，所以不是瓶颈，复杂度 $O(m\sqrt n)$

code

C. Market

Market

没做出来

$60$ 的暴力考虑到因为时间点只有 $300$ 个所以把每个时间点的答案预处理出来

观察满分的数据范围发现虽然代价很高，但是价值很小。只有 $300$ ，考虑记录 $f_V$ 表示价值为 $V$ 的最小代价，转移这个的复杂度是 $O(n\sum V)$ 的

然后想办法查询，RenaMoe 暴力排序过了 ，因为要价值尽可能的大，所以做一个后缀 $\min$ ，就有了单调性，就可以二分查询

复杂度 $O(n\sum v_i+m\log \sum v_i)$

code

D. 动态数点

动态数点

ST 表大力维护区间 $\gcd$ 二分区间长度 $O(n\log n)$ 可过

但是存在 $O(n)$ 做法，因为 $a|b $ 且 $b|c$ $\Rightarrow a|c$

所以以 $i$ 为左端点，最远能拓展到 $r$ ，那么 $[i,r]$ 这些点都没用，因为他们能拓展到的点都能被 $i$ 拓展到，直接从 $r+1$ 继续

这样每个数字只会被扫描一边，$O(n)$

code

E. 序列

序列

绝对值先去掉，考虑每次循环左移除了第一个数字其他的从 $x-i$ 变成 $x-(i-1)$

如果原来 $x-i$ 是负数，那么绝对值上就会少 $1$ 贡献，其他的会多 $1$ 贡献

这样记录下有多少个数字减去排列一开始是小于 $0$ 的，然后考虑 $-y$ 会在 $y$ 轮后变成正的，开个桶记录，到那一轮加减对应的 $\mathrm{cnt}$ 即可

特别处理第一个数，他减去 $n$ 后变成负数 $y$ 需要 $-y+i$ 轮

code

F. 最大战略储备

最大战略储备

先从最暴力的 Kruskal 开始，发现如果现在没有边，那么如果选定了一条 $(e.a_i) \rightarrow (e.b_i)$ 的边，所有的 $(e.a_i) \rightarrow (e.b_i)$ 都会选上，因为他们的权值一样，之后如果选定了 $(a_i,f) \rightarrow (b_i,f)$ 的边，因为 $(e.a_i) \rightarrow (e.b_i)$ 之前已经连起来了，所以这两个只需要连一条即可

反过来同理

所以我们想可以记录每行每列现在的连通块个数，每次连行/列边仅需要连列/行连通块数目，这样只需要做 $O(n+m)$ 的 Kruskal 即可

code