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
F
首先假如只从一个点出发,比如说 $1$ ,那就是计算以 $1$ 为根的子树的答案,DP 非常好做。现在是要求 $n$ 个的,看看能不能换根 DP
官方题解里面对换根 DP 的使用方法总结的不错,记录在这里:
- DP 状态的值的类型
- 在某一个点合并的方式和关键贡献
- 计算当根转移到子节点时没有当前根的贡献(也就是关键贡献)
那么原来我们可以设 $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
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}$
复习同余中的两个定理:
- $\frac{x}{b} \equiv 0 \mod M \Longleftrightarrow x \equiv 0 \mod bM$
- $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
多项式?生成函数?
不更
11 条评论
优先落实题目
下课来我办公室一下
狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!狂暴膜托!!!
???
托老师F写的这么简洁?比我那个维护最大值和次大值的换根好到不知道到哪里去了
可以帮我调下F吗,提交记录:https://atcoder.jp/contests/abc222/submissions/26480086
S00021
S00021
可以帮我调下F吗,提交记录:https://atcoder.jp/contests/abc222/submissions/26480086
托老师F写的这么简洁?比我那个维护最大值和次大值的换根好到不知道到哪里去了