ARC 专题（4 题场）

“本着题是用来做的原则，我们从远古时期的 4 题场开始。”

PART I

什么东西呢。

ARC064

https://atcoder.jp/contests/arc064/tasks。

VP 通过 ABC，perf 2489，感觉一般。

A 吃了一发罚时，没注意到 $a_1>x$，注意细节！！

D 确实不是我能想出来的东西。

B. An Ordinary Game

Portal.

妙哉，妙哉！

手造几个东西发现最终之和两端的东西是否相等和长度的奇偶性有关，讨论一下不难得到答案。

代码。

C. Cosmic Rays

Portal.

考虑圆外的一点如何走到圆内的距离是最短的：很简单，将它和圆心连线即可。也就是说，我们将所有圆都看作圆心一个点，求出的距离必定是最短距离。

枚举任意两个圆和起点终点，计算出它们之间的暴露在宇宙射线中的距离，然后在这张完全图上直接暴力 Dijkstra 求出最短路即可，时间复杂度 $O(n^2)$。代码。

D. Rotated Palindromes

Portal.

考虑如何不重不漏地统计。如果一个回文串是由多个相同的回文串组成的，那么设它的最小循环节长度为 $t$，那么将其移动 $t$ 次后就会变成原来的回文串。

设 $f_i$ 表示长度为 $i$ 的回文串个数，我们只需要考虑 $i$ 为 $n$ 的约数的情况。

长度为 $i$ 的回文串有 $k^{\lceil i/2 \rceil}$ 种，根据上面所说的不重不漏，容斥得到 $f_i=k^{\lceil i/2 \rceil}-\sum_{j\mid i} f_j$。

如何统计答案？如果 $i$ 是奇数，那么操作 $i$ 次之后所构成的串均不相同，系数为 $i$；如果 $i$ 是偶数，那么操作 $i/2$ 次之后会变成一个新的回文串，为了防止算重，其系数为 $i/2$。代码。

ARC065

https://atcoder.jp/contests/arc065/tasks。妙哉！

VP 通过 ABD，C 不知道是个什么。

perf 2762，感觉还行。

B. Connectivity

Portal.

只有一个东西不难想到使用并查集维护。

两个信息只难在如何统计。只要知道其在两个信息里的编号就可以确定当前点的连通块了。那么开一个 map<pair<int, int>, int>，来代表一个 pair<int, int>，即分别给定其道路和地铁的连通块所对应的“大连通块”的点数。代码。

C. Manhattan Compass

Portal.

给定平面上的 $n$ 个点，选择两个点满足其曼哈顿距离等于 $d$，求方案数。

将曼哈顿距离转为切比雪夫距离，排序二分不难找出合法的点的区间。如何求方案数？对于 $i$ 所对应的合法区间 $[l,r]$，$i$ 向 $l$ 连边，然后区间内依次连边。对于连到了 $a$ 点的点，其方案数均可以被统计。

为了避免重复统计，需要注意对于 $y$ 统计时不能计算 $x$ 相等的情况。代码。

D. Shuffling

Portal.

考虑 $O(n^2)$ 的 DP。设 $f_{i,j}$ 代表前 $i$ 个数填了 $j$ 个 $1$ 的方案数。转移显然是 $f_{i,j}=f_{i-1,j}+f_{i-1,j-1}$。

问题在于什么样的 $j$ 是合法的。预处理出每个左端点可以“支配”到的右端点，这部分以内是可以随便交换的。显然，如果存在一个可交换区间 $[l,r]$，那么 $\forall x\in [l,r]$，$x$ 都能够支配到 $r$。

扫描到第 $i$ 个位置时，$1$ 的个数最多是将支配范围内的 $1$ 全部搞过来（当然不能超过 $i$），最少是能扔出多少 $1$ 到支配范围就扔多少（当然不能少于 $0$），直接转移即可。

代码。

ARC067

https://atcoder.jp/contests/arc067/tasks。

VP 通过 ABC。前期网有点卡，后面 C 做的太慢了，导致甚至没有见到 D，有点大失败。

perf 2121，感觉一般。

C. Grouping

Portal.

发现数据范围很小，因此直接考虑暴力 DP。

设 $f_{i,j}$ 代表考虑到分人数为 $i$ 的组，当前有 $j$ 个人的方案数。决策有两种：不存在这个人数的组，这个人数的组的个数在 $[c,d]$ 之间。那么有：

$$f_{i,j}=f_{i-1,j}+\sum_{j=c}^d f_{i-1,j-ki}\binom{n-(j-ki)}{ki}g_{i,k}$$

组合数代表在剩余的人中选择 $ki$ 个人来完成人数为 $i$ 的组的填充，$g_{i,k}$ 代表将 $ki$ 个人分成 $k$ 组，一组 $i$ 个人的方案数。

其计算的过程是这样的：现在 $ki$ 个人中选择 $i$ 个人，再在 $(k-1)i$ 个人中选择 $i$ 个人……由于组之间不区分，因此最后除掉 $k!$ 去重。因此：

$$g_{i,k}=\frac {\prod_{j=1}^k \binom{ji}{i}} {(ki)!}$$

直接递推分子，分母在计算 $f$ 时除掉即可。由于枚举 $j$ 的时候是调和级数复杂度，因此时间复杂度为 $O(n^2\log n)$。代码。

D. Yakiniku Restaurants

Portal.

发现走的必定是一条线段。从右端点开始枚举左端点，维护数组 $ans_i$ 表示右端点在 $i$ 的最优答案。每次考虑是否将贡献换到左端点，单调栈维护前缀最大值来计算贡献即可。代码。

UPD

可能不更新了，以后的 ARC 题会放在加训记录里。