Codeforces试题乱做 Part3

Posted on Edited on

啊, 时间过的好快啊, 最近考试好多, 改题让我时间好少, 还是希望能多做点自己想做的题, 那就卷一点吧.

这个 $\text{Part}$ 怎么也得省选前搞定吧.

$\text{[CF1097G]Vladislav and a Great Legend}$

$\color{blue}{\text{[NORMAL]}}$

啊, 好的, 我以后知道怎么算 $\sum\limits_{n}{f(n)^k}$ 这种东西了.

这个考虑组合意义就行.

其实 $x^k$ 这种形式不一定只有斯特林数一种思路, 如果只想斯特林数早晚得寄.

推导式子可得,

外面枚举 $i$ 肯定没毛病, 那就考虑里面那个组合数怎么做, 考虑其组合意义, 对于每一个点集组成的生成树, 在树里面选 $i$ 条边染色的方案数.

设 $f_{x,i}$ 表示 $x$ 的子树内选出一个有 $i$ 条边被染色的非空生成树的方案数.

类似树形背包的转移, 但这个树形 $dp$ 有点细节我觉得, 很容易就会忘记考虑新的子树和父亲的边.

考虑新加入一个子树, 那么:

  1. 只有原来的子树.
  2. 只有新的子树 (加上 $x\rightarrow y$ 这条边).
  3. 原来的和新的共同组成 (加上 $x \rightarrow y$ 这条边).

时间复杂度 $\mathcal{O}(nk)$ .

$\text{[CF679E]Bear and Bad Powers of 42}$

$\color{blue}{\text{[NORMAL]}}$

因为 $42$ 的幂次越往大越在值域内的就越少, 线段树维护每个数到 $42$ 的幂次差多少, 以及区间 $\min$ , 若当前最小值小于要加的数, 那就递归下去暴力修改.

区间赋值也是好做的, 标记下传的时候注意顺序即可.

定义连续段的势能为值域内大于其值的 $42$ 的幂的个数, 那么一次操作最多会被递归 $\log_{42}{nV}$ 次. 单次操作复杂度为 $\mathcal{O}(\log_{42}{nV}\log{n})$ .

总体复杂度为 $\mathcal{O}(q\log_{42}{nV}\log{n})$ .

$\text{[CF889E]Mod Mod Mod}$

$\color{red}{\text{[HARD]}}$

令 $g(x,i) = x \bmod a_1 \bmod a_2 \bmod a_3 \dots \bmod a_i$ .

发现, 只要 $\forall i,g(x,i) \not = 0$ , 则有 $\forall i,g(x-1,i)=g(x,i)-1$ , 也就只要保证 $x \bmod a_i$ 都不是 $0$ , 可以随意降低 $x$ , 都不影响 $g(x,i)$ 之间的相对差.

设 $f(i,R)=y$ 表示如果 $x \bmod a_i$ 最后变成了 $0 \sim R$ , 这时多出来的部分的最大值都可以是 $y$ .

这时可以设计 $dp$ , 用 $map$ 存二元组 $(R,y)$ , 在 $i$ 处枚举所有二元组试图使其适配 $a_{i+1}$ .

  • 如果 $R < a_{i+1}$ , 则二元组不变.
  • 否则可以直接延展到 $a_{i+1}$ , 变为 $(R \bmod a_{i+1},y’)$ .
  • 如果 $R \geqslant a_{i+1}$ , 可以把 $R$ 降低到 $a_{i+1}-1$ , 使得 $i+1$ 成为卡着上界的地方, 变为 $(a_{i+1}-1,y’’)$ .

除了以上转移方案, 其他方式都不能保证 $R$ 存在一个位置卡满上界.

一共只会产生 $n$ 个新的 $R$ , 故复杂度为 $\mathcal{O}(n\log{a_i}\log{n})$ .

$\text{[CF571D]Campus}$

$\color{blue}{\text{[NORMAL]}}$

感觉这种集合合并的东西总能并查集离线做, 下次要牢记这种套路.

合并时新建一个虚电, 先把森林建出来, 问题就转化为两个森林分别子树加, 子树赋值.

注意到我们对于每个点只用关注它查询之前最后一次赋值为 $0$ 的时间以及之后的子树加, 询问就变成了区间求和, 树状数组维护即可.

时间复杂度 $\mathcal{O}(n+m\log{n})$ .

$\text{[CF1332G]No Monotone Triples}$

$\color{red}{\text{[HARD]}}$

这题首先要看出 $b$ 不会太长, 不能超过 $4$ .

证明大概是分类讨论, 用 $Dilworth$ 定理证明.

我们可以预处理出 $1 \sim n$ 中的每个 $i$ 作为 $b_1$ 时, 最近的 $b_3$ 或 $b_4$ 在哪.

这样对于每组询问只需要 $ST$ 表维护一下 $[l,r]$ 中最小值和最小位置, 判断一下最小位置是否在 $\leqslant r$ 即可.

分类讨论 $3,4$ ,

存在一个长度为 $3$ 的 $b$ , 只需要序列 $a$ 在 $[l,r]$ 中不单调.

对于每一个 $i$ , 处理出在它前面第一个不同于 $a_i$ 的位置 $pre_i$ , 和后一个不同于 $a_i$ 的位置 $nxt_i$ , 如果有 $(a_i-a_{pre_i})(a_{nxt_i}-a_i) < 0$ , 则存在一个长度为 $3$ 的 $b\{a_{pre_i},a_i,a_{nxt_i}\}$ .

在 $b_1=pre_i$ 上记录一个可能的 $b_3=nxt_i$ , $ST$ 表维护即可.

存在一个长度为 $4$ 的 $b$ , 需要满足 $b_1,b_4$ 既不是 $b$ 中的最大值, 也不是最小值.

从前往后维护一个单调不降的单调栈 $stk_1$ 和一个单调不升的单调栈 $stk_2$ .

为了使 $b_1,b_4$ 不成为 $b$ 中最大或最小值, 不难推出 $b_4$ 需满足两个条件,

  1. $b_4$ 既不在 $stk_1$ 中, 也不在 $stk_2$ 中.
  2. 在 $b_4$ 之前存在一个 $x$ 在 $stk_1$ 中, 且满足 $a_x \not= a_{b_4},x > b_1$ , 存在 一个 $y$ 满足 $a_y \not= a_{b_4},y > b_1$ .

也就是找到 $stk_1$ 中第一个严格大于 $a_{b_4}$ 的位置 $gt$ 和 $stk_2$ 中第一个严格小于 $a_{b_4}$ 的位置 $lt$ , 然后在 $(\max\{gt,lt\},n]$ 中找到即不在 $stk_1$ 中也不在 $stk_2$ 中的最小位置, 这就是符合条件的最小 $b_4$ , 可以用 $set$ 维护.

时间复杂度 $\mathcal{O}(n\log{n}+q)$ .

$\text{[CF453E]Little Pony and Lord Tirek}$

$\color{green}{\text{[EASY]}}$

考虑到如果一个位置曾变为 $0$ 那它的贡献是好算的, 如果一段全是 $0$ , 那这一段的贡献都是好算的.

这让我们联想到分块.

预处理出每个块 $i$ 从 $0$ 开始 $j$ 个单位时间后的和, 我们称一个块是未被限制的当且仅当它在某一时刻被清零, 且未被单点修改过, 这些块可以预处理出答案直接计算贡献, 否则一个块称为被限制的, 暴力计算贡献.

一开始所有块都是被限制的, 每次修改至多将两个块变成限制的, 所以复杂度均摊下来并没有问题.

预处理是采用两次前缀和, 时间复杂度 $\mathcal{O}(\frac{n^2}{B})$ , 其中 $B$ 为块长, 块长需自己调整, 以卡空间, 当然也可以通过技巧做到线性.

$\text{[CF643G]Choosing Ads}$

$\color{blue}{\text{[NORMAL]}}$

摩尔投票法, 受教了.

傻子也看的出答案不能超过 $5$ 个.

首先考虑 $p\geqslant 51$ 的情况, 也就是要求区间绝对众数, 摩尔投票法是这样的, 维护当前众数和它的血量 $HP$ , 每次新加入一个数, 如果它和现在的众数相等, 那么 $HP+1$ , 否则 $HP-1$ , 如果 $HP$ 变为 $0$ 了, 那么它就寄了, 用杀掉它的数来当新的众数, 其 $HP$ 变为 $1$ , 最后剩下的数就是可能的答案.

正确性也比较显然, 如果一个数超过了一半也不可能被别的数干寄.

然后推广到 $p=20$ 的情况, 维护当前 $5$ 个众数和 $HP$ , 合并两个区间就拿两个区间的 $10$ 个众数暴力合并就行了.

线段树维护即可, 时间复杂度 $\mathcal{O}(nk^2\log{n})$ , 其中 $k=\lfloor \frac{100}{p} \rfloor$ .