VP: AtCoder Beginner Contest 227 (ABC227)

tony102

2021 年 11 月 16 日

2485 次浏览

暂无评论

1389字数

总结比赛记录

它也有资本家赞助，所以有一个很流批的名字叫做：KEYENCE Programming Contest 2021 (AtCoder Beginner Contest 227)

总而言之就是最近想报复性学习，加上睡眠质量很差，但是一到了晚上特别兴奋完全睡不着，导致第二天早上只想睡觉。不过今天是周末，晚上不睡觉开 vp 是没有问题的。

## A

不解释

## B

不解释

## C

不解释

## D

二分答案 $mid$ 然后 check，若 $s = \sum\min(a_i,mid) \leq mid \times k$ ，那么合法。

## E

开始在想，这题是不是爆搜剪剪支应该能过。最开始其实想的是，把 `K` 看成 $0$，`E` 和 `Y` 同理分别为 $1, 2$ 。那么每个串相当于一个加法式子，然后要求 $\sum c_i = n, c_i \in\{0,1,2\}$ 且两两之前存在一个前缀和不同的位置。这个时候我在想是不是枚举一下划分数，但是这三个字母数量都分别有限制。所以搞不了。

但是看见 $n \leq 30$ 这种奇特数据范围，就该想想暴力 dp。有一个小套路就是，考虑从一个空串 $t$ 开始填成 $s$，那么每次只需要考虑填这三个字母能不能匹配上一段 $s$，就设 $f_{i,x,e,y}$ 表示前 $i$ 个位置已经和 $s$ 匹配上了且需要 $x$ 次操作，包含了 $e$ 个 `E` 和 $y$ 个 `Y` 的答案。随便转移即可。

[Submission for E](https://atcoder.jp/contests/abc227/submissions/27243902)

## F

真的艹，一场 ABC 出两个这种暴力 dp

上来你想直接计数（rnm cdqz 一场 noip 联考两道神仙计数。发现 $H + W \leq 30$ 就感觉很不对劲。

还是一个套路，考虑第 $k$ 大的数已经确定，设 $f_{i,j,k}$ 表示到 $(i,j)$ 已经填到第 $k$ 大的数，每次从 $k-1$ 转移即可。

[Submission for F](https://atcoder.jp/contests/abc227/submissions/27244232)

## G

upd: 2021.11.16 0:04

后来发现，这个 G 比 E 和 F 都简单，但是值 600 分，就有一个 vp 怪把我卷到了 rk2

直接算 $\binom{n}{k}$ 因为 $n \leq 10^{12}$ 所以直接算算不了。但是知道算术基本定理：$x = \prod c_i^{p_i}$  那么 $x$ 的约数个数就是 $\prod (p_i+1)$ 。把组合数拆成阶乘：$\frac{n!}{k!(n-k)!} = \frac{(n-k+1)\cdot \dots \cdot n}{k!}$ ，那么只要上下算一下就行了。

[Submission for G](https://atcoder.jp/contests/abc227/submissions/me)

## H

咕咕咕咕咕

最后修改：2021 年 11 月 16 日