Codeforces Round 952 (Div. 4)

赛后一个题一个题做的

比赛链接

Problems	AC
A. Creating Words	○
B. Maximum Multiple Sum	○
C. Good Prefixes	○
D. Manhattan Circle	○
E. Secret Box	○
F. Final Boss	○
G. D-Function	○
H1. Maximize the Largest Component (Easy Version)	○
H2. Maximize the Largest Component (Hard Version)	○

A

Code

B

Code

C

Code

D

Code

E

Code

F

Code

G

假设 $D(n)$ 表示 $n$ 的数字之和。那么有多少个整数 $n$ 满足 $10^{l} \leq n < 10^{r}$ 且 $D(k \cdot n) = k \cdot D(n)$ ？输出答案模 $10^9+7$ 。

显然，不能进位。

令 $x = \lfloor\dfrac{9}{k}\rfloor$，那么一个合法数字最高位 $\in [1, x]$，其余位 $\in [0, x]$。

长度为 $len$ 的合法数总共有 $x(x + 1)^{len - 1}$

那么答案为 $x((x + 1)^l + \cdots + (x + 1)^{r -1}) = (x + 1)^r - (x + 1)^l$

Code

H1

Alex 有一个网格，其行数为 $n$ ，列数为 $m$ ，由 ‘.’ 和 ‘#’ 字符组成。如果从一组 ‘#’ 个单元格中的任何单元格出发，仅通过移动到集合中共享公共边的另一个单元格即可到达该集合中的任何其他单元格，则该集合构成连通分量。连通分量的大小是集合中的单元格数。

在一个操作中，Alex 选择任意行 $r$ ( $1 \le r \le n$ ) 或任意列 $c$ ( $1 \le c \le m$ )，然后将行 $r$ 或列 $c$ 中的每个单元格设置为 ‘#’。帮助 Alex 找到最多执行一次操作后可以实现的“#”个单元格最大连通分量的最大可能尺寸。

没什么好说的，并查集然后分别枚举哪一行或者哪一列即可，属于是 implement 题。

Code

H2

Alex 有一个网格，其行数为 $n$ ，列数为 $m$ ，由 ‘.’ 和 ‘#’ 字符组成。如果从一组 ‘#’ 个单元格中的任何单元格出发，仅通过移动到集合中共享公共边的另一个单元格即可到达该集合中的任何其他单元格，则该集合构成连通分量。连通分量的大小是集合中的单元格数。

在一个操作中，Alex 选择任意行 $r$ ( $1 \le r \le n$ ) 和任意列 $c$ ( $1 \le c \le m$ )，然后将行 $r$ 和列 $c$ 中的每个单元格设置为 ‘#’。帮助 Alex 找到最多执行一次操作后可以实现的“#”个单元格最大连通分量的最大可能尺寸。

每个联通块实际上会对一个十字形的矩形区域有贡献，这其实就是在矩形上面做矩形加法，二维差分即可。

Code