VP: AtCoder Beginner Contest 222(ABC222)

博主： tony102
发布时间：2021 年 10 月 14 日
4864 次浏览
11 条评论
2033字数
分类：总结比赛记录

## A

不解释

## B

不解释

## C

石头剪刀布大模拟...

不解释

## D

类似于货币系统，背包转移即可。

## E

设每一条边被经过了多少次为 $c_i$，设有红蓝边各 $R$ 条，$B$ 条，那么很容易得到：

$R+B = \sum c_i, R-B = k$

可以直接解得：$R = \frac{\sum c_i + k}{2}, B = \frac{\sum c_i - k}{2}$

那么红蓝边各要染多少已经直接解出来了（$c_i$ 可以在 $O(n^2)$ 的时间内预处理），问题转化成：有红蓝物品各 $R,B$ 个，有 $n-1$ 个背包，第 $i$ 个容量为 $c_i$（强制 $c_i \geq 1$ 的必须选一个），求方案数。

然后还是背包转移就行了。

Code: [Code](https://atcoder.jp/contests/abc222/submissions/26515717)

## F

首先假如只从一个点出发，比如说 $1$ ，那就是计算以 $1$ 为根的子树的答案，DP 非常好做。现在是要求 $n$ 个的，看看能不能换根 DP

官方题解里面对换根 DP 的使用方法总结的不错，记录在这里：

> 1. DP 状态的值的类型
> 2. 在某一个点合并的方式和关键贡献
> 3. 计算当根转移到子节点时没有当前根的贡献（也就是关键贡献）

那么原来我们可以设 $f_u$ 表示以 $u$ 为根的子树答案，转移 ：$f_u = \max\limits_{v \in son_{u} } \{max(d_v, f_v) + w(u,v)\}$

我们可以在以 $1$ 为根的时候，记录每一次 $f_u$ 是从哪一个 $v$ 转移过来的，那么每次需要消除的关键贡献就是那个点的答案。

Code: [Code](https://atcoder.jp/contests/abc222/submissions/26516850)

## G

首先想到把 $222\dots222$ 这种数字拆开来，假如有 $n$ 位，数为 $s$ ，那么：

$$
s = \sum\limits_{i=0}^{n-1} 10^{i} \cdot 2
$$

可以等比数列求和，顺便复习一下等比数列求和公式，设首项为 $a$，公比为 $q$，项数为 $m$，那么 $sum = \frac{a(1 - q^n)}{1-q}$

所以 $s = \frac{2(10^n-1)}{9}$

那么现在问题就转化成了：要找到最小的 $n$ ，使得 $s \equiv 0 \mod {K}$

复习同余中的两个定理：

1. $\frac{x}{b} \equiv 0 \mod M \Longleftrightarrow x \equiv 0 \mod bM$
2. $ax \equiv 0 \mod M \Longleftrightarrow x \equiv 0 \mod \frac{M}{\gcd(a, M)}$

先转化一波式子，先用第一个式子，把分母中的 $9$ 移过去：$2(10^n-1) \equiv 0 \mod 9M$

再用第二条，发现 $gcd(a,M)$ 就是对 $M$ 的奇偶性进行讨论：

$$
M'=
\left\{
\begin{aligned}
9M , M \equiv 0 \mod 2 \\
\frac{9M}{2}, M \equiv 1 \mod 2
\end{aligned}
\right.
$$

所以现在要求的就是：$(10^n-1) \equiv 0 \mod M'$ 的最小的 $n$

再稍微换一下：$10^n \equiv 1 \mod M'$

因为 $\gcd(1, M') = 1$  ，根据欧拉定理则：$10^{\phi(M')} = 1 \mod M'$

猜想一下， $n$ 是 $\phi(M')$ 的约数是合法答案。

证明：

若 $n$ 不是 $\phi(M')$ 的约数，设 $n > d = \gcd(n, M')$，有：$pn + q\phi(M') = d$ ，则：$10^d = (10^n)^a(10^{\phi(M')})^q \equiv 1 \mod M'$ ，故存在 $d < n$ 满足题意与假设矛盾，所以 $n$ 是 $\phi(M')$ 的约数。

所以可以 $O(\sqrt{M'})$ 的时间内算出 $\phi(M')$ 和 $M'$ ，然后判断即可。

## H

多项式？生成函数？

不更

最后修改：2021 年 10 月 19 日

如果觉得我的文章对你有用，请随意赞赏

11 条评论

two.
October 15th, 2021 at 08:31 am

优先落实题目

回复
two.
October 15th, 2021 at 08:30 am

下课来我办公室一下

回复
???
October 15th, 2021 at 08:26 am

狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！狂暴膜托！！！

回复
???
October 15th, 2021 at 08:23 am

???

回复
abcyz
October 15th, 2021 at 08:20 am

回复
abcyz
October 15th, 2021 at 08:19 am

托老师F写的这么简洁？比我那个维护最大值和次大值的换根好到不知道到哪里去了

回复
abcyz
October 15th, 2021 at 08:18 am

可以帮我调下F吗，提交记录：https://atcoder.jp/contests/abc222/submissions/26480086

回复
abcyz
October 15th, 2021 at 08:17 am

S00021

回复
abcyz
October 14th, 2021 at 09:53 pm

S00021

回复
abcyz
October 14th, 2021 at 09:52 pm

可以帮我调下F吗，提交记录：https://atcoder.jp/contests/abc222/submissions/26480086

回复
abcyz
October 14th, 2021 at 09:50 pm

托老师F写的这么简洁？比我那个维护最大值和次大值的换根好到不知道到哪里去了

回复