Atcoder Grand Contest 011

Posted on 2022-01-17 Edited on 2022-03-25

这场是好久以前就开始写了的, 但是 $F$ 题一直咕着, 就没写前面的题解.

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

$\text{[AGC011E]Increasing Numbers}$ 这题好厉害啊, 是我想不到的结论题没错了.

看到连通块计数, 很块就应该反应到是找代表源.

这里的代表源就应是 $(a,b)$ , 满足这个代表源是这个连通块中字典序最小的.

考虑新图有边实际上就是, 在原图上移动两个点.

新图上的一个连通块相当于在原图上的两个连通块的序号最小点开始走, 能走的所有情况都在一个连通块内.

不难想到分类讨论.

对于原图中独立的点$x$ , 新图的 $(x,i)$ 和 $(i,x)$ 均为独立点. 故设原图中独立点数量为 $p$ , 则其对答案的贡献为 $pn+(n-p)p$ .
对于原图的一个无奇环连通块, 由于是个二分图, 它可以与任一连通块组成新图的两个不同连通块. 设这种连通块个数为 $c$ , 那么两两组合对答案的贡献就是 $c \times c \times 2$ .
对于原图的一个有奇环的连通块, 它可以与任一连通块组成新图的两个不同的连通块(与不含奇环的组成两个). 设这种连通块个数为 $d$ , 那么对答案的贡献就是 $d \times (d+c \times 2)$ .

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

不难发现经过串 $S$ 后有两种情况.

$\mathcal{O}(k)$ 模拟可过.

正解也很简单, 事实上 $S$ 的转移是 $pho$ 形的, 且链的长度是 $2n$ 的因子, 环的长度是 $2$ 的因子.

令 $k = 2n+(k-2n)%2$ 即可.

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

不难发现, 上升数一定可以表示为最多 $9$ 个全是 $1$ 的数字的和.

我们设 $p_i = \underbrace{111\dots1}_{i}$ , $a_{i,j}$ 表示构成 $N$ 的第 $i$ 个上升数的第 $j$ 个全 $1$ 的数的位数.

那么可以写出这样的式子 $N = \sum\limits_{i=1}^k{\sum\limits_{j=1}^{9}{p_{a_{i,j}}}}$ .

我们发现这样的形式很不好做, 继续观察 $p_i$ 的性质, 发现 $p_i = \frac{10^i-1}{9}$ .

所以上式子可以写成,

$N = \sum_{i=1}^k{\sum_{j=1}^{9}{\frac{10^{a_{i,j}}-1}{9}}} \\ 9N+9k = \sum_{i=1}^k{\sum_{j=1}^9{10^{a_{i,j}}}}$

我们发现, 右边的东西, 如果在所有 $10$ 的幂次加起来的过程中, 能够不进位的话, 那么它的数位和一个是 $9k$ .

如果发生了进位的话, 因为进一次位一定是总数位和减 $9$ , 而 $9k$ 的 $9$ 的倍数, 所以这个东西的数位和一定是一个小于 $9k$ 的 $9$ 的倍数.

再看左边, 我们发现, 实际上我们只需要满足 $9N+9k$ 的数位和小于 $9k$ 且是 $9$ 的倍数, 而 $9N+9k$ 一定是 $9$ 的倍数.

所以我们只需要求出最小的 $k$ , 使得 $9N+9k$ 的数位和小于等于 $9k$ 即可.

不难发现 $k \leqslant len(N)$ .

枚举 $k$ 即可.

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