VP: AtCoder Beginner Contest 224(ABC224)

tony102

2021 年 10 月 25 日

1803 次浏览

暂无评论

1725字数

总结比赛记录

其实没开 vp，就是一路做下去的。昨天晚上写了几个，今天上午写到了 G

感觉这场风格有点诡异？整体码量很小。

## A

？不解释

## B

？？？很明显有更优的算法。但是只需要 $O(n^4)$ 随便跑就行了。

## C

只需要判断有多少个点组成的三元组，满足任意三点不共线即可。

## D

《八数码问题》，BFS + `map` 随便过吧

## E

注意到非零的格子只有 $\leq \min {(2 \times 10^5, HW)}$ 个，所以其实可以扩展出去的点规模不大。我们也只需要关心这些点。

记 $A_{i,j}$ 为当前的格子图。直接设 $f_i$ 表示第 $i$ 个格子可以扩展出去的最大步数。合法的转移应该满足如下两个条件：

1. $r_i = r_j \lor c_i = c_j$
2. $A_{r_j, c_j} > A_{r_i, c_i}$

直接转移是 $O(n^2)$ 的，考虑优化。

发现一件事情，假如两个非零的位置在同一行或者同一列，那么两个位置会走一段相同的路径。我们把这 $N$ 个格点按照 $a_i$ 的值分类，每次取 $\max {(rmax_{r_i}, cmax_{c_i})}$ 即可。这样是 $O(n \log n)$ 的（大概？

## F

肯定是要考虑每一个 $S_i$ 对答案的贡献的。一下钦定从左到右为从高到低。

最开始考虑的是，枚举当前在 $i$ 这个数，枚举它右边多少个符号位后填了第一个 `+` 号，这样就可以知道它在当前这个数中贡献的是几次幂。然后剩下的位置枚举填多少个符号，用一个组合数就可以。

式子大概长这个样子：$\sum \limits_{i = n}^{1} \sum \limits_{k=0}^{i-1} a_i \times 10^k \sum\limits_{j=0}^{\min {(i-2,i)}} \binom{i}{j}$

然后后面的组合数显然是个 $2^{p}$ 形式的把 $a_i$ 提出去，$10^k$ 等比数列求和。~~然后好像答案不太对~~，思路大概是对的，可能有点细节~~不太对~~。这样算都是 $O(n)$ 的。注意最外层 $i$ 的求和是逆序的。

题解里面有一种更简单的想法，从低位开始确定第 $i$ 的左边会不会出现 `+` 号，这个概率很好算吧...是 $\frac{1}{2^i-1}$，同样分母最大也是 $2^{n-2}$。然后每个数的贡献就是 $10^i \times a_i \times P$ （$P$ 表示这个概率）。然后就被秒了。

## G

？？？？G 题是一个需要 $O(1)$ 计算的题？？（逃

唔，但其实非常简单。首先看得出来，若 $S \leq T$ ，那么只需要操作 $1$ 一直加上去，就是最小的花费。这样就是 $A(T-S)$

现在难办的就是 $S > T$ 的情况，首先需要通过操作 2 把它变成 $X \leq T$，然后做操作 $1$。操作 2 的期望是 $\frac{BN}{X}$，操作 1 是：$\sum\limits_{i= T-X+1}^{T} A(T-i)/X = \frac{A(X-1)}{2}$

现在要选取最小的 $X$，可以通过上面的两部分答案得到一个函数 $f(x) = \frac{A(X-1)}{2} + \frac{BN}{X}$，要去 $f(x)_{\max}$ 时的 $x$，可以求出：$f'(x)= (\frac{A(x-1)}{2} + \frac{BN}{x}) = \frac{A}{2} + \frac{BN}{x^2}$，令 $f'(x) = 0$，得到：$x = \sqrt{\frac{2NB}{A}}$

注意我们要的 $x$ 必须是一个整数且 $1 \leq x \leq t$，所以计算向上取整、向下取整和 $f(t)$ 的取值取 $\min$ 即可。

## H

不懂，不更。

最后修改：2021 年 10 月 26 日