这场ABC都是Div2 ABC种偏难的。。但是后面难度就上不去了(可能是我只会做一点点套路题的原因?)

A

这里的反转是 reverse,不是取反。。自闭了。。

设这两个数是 $a,b$,其中 $a > b$,由于字典序最小,所以我们从低位向高位看,要求尽量是 $0$。

我们找到 $b$ 的 $\text{lowbit}$ $p$,发现比 $p$ 低的位都是无法改变的(由 $a$ 决定),我们可以通过一些移动,让 $p$ 对齐比它高的某个 $a$ 上的 $1$,消去这个 $1$。按照字典序的贪心策略,就找比 $p$ 高的第一个位置就行了。

比如样例的第二组数据:

10001
  110
b 的 lowbit 是从低到高第二位,我们让它消去能到达的最近的位(a 的最高位)
0010001
0110
1000001
reverse: 1000001

B

相当于在 $\bmod 10$ 下加法,只需要预处理 $f_{a,b,c}$ 表示满足 $ax+by = c \pmod {10},a \geq 0,b \geq 0$ 的最小的 $x+y$ 就行了。这个可以对于每个 $(a,b)$ 跑个 bfs。

那么每次就暴力模拟走就行了。注意 $f_{a,b,0}$ 不一定是 $0$,所以最初 bfs 的时候应该将 $f_{a,b,a},f_{a,b,b} = 1$,然后把 $a,b$ 扔进队列扩展。

C

行列独立,现在转化为一维问题。

现在我们要判断是否能通过增加一个操作使得影响区间长度 $-1$。

我们分类讨论是要减少最大值还是增加最小值:以减少最大值为例,如果在时间 $p$ 加入一个操作,必须要满足 $p$ 前面没有出现过最大值,后面没有出现过最小值(这样能保证所有最大值都被 $p$ 影响,并且所有最小值不会被 $p$ 影响而导致 $-1$),所以求出来最大值时间轴上的最小位置,和最小值时间轴上的最大值,判断一下中间是否能放就行了(注意最大值和最小值紧挨着是不合法的)

D

一种基本思路是构造 1333.....3337,设 $3$ 的个数为 $x$,答案就是 $\binom x 2$。

我们将 $n$ 分解为若干个 $\sum_{i=1}^m \binom {x_i} 2$ 的形式,我们只需要在对应 $x_i$ 的位置插入 7 就好了。

比如:$8 = \binom 4 2 + \binom 2 1 + \binom 2 1$,对应的序列是 13377337

E

感觉全场最简单题。。

先枚举分割点 $i$,如果求出 $pre_i,suf_i$ 表示匹配到 $i$ 前缀结尾/$i$ 后缀开头的串有多少个,对答案的贡献就是 $pre_i \times suf_{i+1}$。

$pre_i$ 可以对小串建 AC 自动机,就是 fail 树上到根的标记和。$suf_i$ 对反串做就行了。

注意:AC自动机 不保证 $fail_i \leq i$,所以统计 fail 树信息请手动建树!!

F

引理 $1$:对于任何 $|\Sigma| \geq 2$ 的串,一定存在一种重排列方式满足其最小正周期为 $n$。

这个显然,直接排序就行了。

设 $n = a+b$,我们首先枚举一个 $k$ 观察如何检查答案。

那么相当于 $k$ 个分成一段,我们可以求出整段个数 $g = \lfloor \frac{n}{k} \rfloor$。

那么设第一段用了 $x$ 个 A,$y$ 个 B,首先我们要保证 $k=x+y$,然后为了保证数量够,有限制 $xg \leq a,yg \leq b$,然后我们要保证最后一段能拼成前面的一部分周期,于是还有 $a-xg \leq x,b-yg \leq y$,解出来是

$$ \begin{aligned} \lceil \frac{a}{g+1}\rceil\leq x \leq \lfloor \frac{a}{g} \rfloor\\ \lceil \frac{b}{g+1}\rceil\leq y \leq \lfloor \frac{b}{g} \rfloor\\ \end{aligned} $$

我们对 $g$ 除法分块,用上面的不等式可以得到 $k=x+y$ 的限制,算一下交就行了。

Last modification:October 10th, 2020 at 11:12 am
如果觉得我的文章对你有用,请随意赞赏