VP: AtCoder Regular Contest 126 (ARC126)

博主： tony102
发布时间：2021 年 10 月 27 日
1865 次浏览
暂无评论
2123字数
分类：总结比赛记录

？？？`puts("nan")`

## A

贪心：

1. 一个 $2$ 的木棍和一个 $3$ 的木棍绑成一个 $5$ 的木棍，能搞多少搞多少。
2. 一个 $2$ 的木棍和两个 $1$ 的木棍绑成一个 $5$ 的木棍，能搞多少搞多少。
3. 两个 $2$ 的木棍和一个 $1$ 的木棍绑成一个 $5$ 的木棍，能搞多少搞多少。
4. 一个 $2$ 的木棍和三个 $1$ 的木棍绑成一个 $5$ 的木棍，能搞多少搞多少。
5. 五个 $1$ 的木棍绑成一个 $5$ 的木棍，能搞多少搞多少。

然后得到有多少 $5$ 的木棍，做完了。

[sol A](https://atcoder.jp/contests/arc126/submissions/26816051)

## B

巧妙题。

我们先来定义两条线段的大小比较。若两条线段分别为 $(x_1, y_1)$、$(x_2,y_2)$，首先按照 $x$ 的升序排，若 $x_1 = x_2$，则按照 $y$ 的升序排。

我们发现，若 $x_1 < x_2, y_1 < y_2$ ，那么两条线段没有交点。我们排序后，相当于在 $y$ 上要找到一个 LCS，要求 $O(n \log n)$ 找，单调栈即可。

[sol B](https://atcoder.jp/contests/arc126/submissions/26817520)

## C

神题 + 1

首先描述一下题目，可以给 $a_i$ 每次 $+1$ ，一共可以加 $k$ 次，要求操作完后 $x_{\max} = \gcd {(a_1,\dots,a_n)}$ 。

直接求，求不出。考虑枚举这个 $x$ ，平凡的情况是 $x \in [1, \max \{a_i\}]$ 。那么要求 $\forall i, x \mid a_i$。所以有 $(k-1)x < a_i \leq kx$。

假如 $a_i$ 在这个范围内，那么我们要对 $a_i$ 做的 $+1$ 操作就是 $kx-a_i$ 次。那么总共的就是：$\sum_{i} kx-a_i$

化一下式子，$\sum_{i} kx - \sum_{i} a_i$，两项都可以通过前缀和来算。即 $\sum_{i} kx-a_i = ckx - s$，其中 $s$ 为所有满足条件的 $i$ 的 $a_i$ 的和，$c$ 为满足条件的 $i$ 的个数。

复杂度为预处理前缀和的复杂度、计算每一个 $x$ 的答案的复杂度之和：$O(n + A_{\max} \log {A_{\max}})$ 。

还有一种特殊情况，就是允许加到 $x > A_{\max}$ 。单独算一下就可以了。

[sol C](https://atcoder.jp/contests/arc126/submissions/26839077)

## D

~~麻雀知识~~

Pure Straight 指一气通贯，就是拥有同种数牌的 123 456 789 三个顺子。门前两番，副露（鸣牌）一番，下图例子即与清一色复合，还多见于与混一色复合。容易平和。

![清一色一气通贯.png](https://tony102.com/usr/uploads/2021/10/1541863020.png)

正经的。神题 + 2

看到 $K \leq 16$ 的数据范围，就是说最后要组成的这个 $\exists n, A_n = 1, A_{n+1} = 2,\dots,A_{n+K-1}=K$ 的这一段很短。

给的操作相当于冒泡排序，因为最后这个 $A$ 是要升序的，又是每次交换相邻两个数。

首先看见这一段要是一个 $K$ 阶的排列，联考题里面有一个题包含了这个题的一个重要结论：排列冒泡排序成有序的交换次数为其逆序对数。那么，假如我们一旦确保某一段 $A$ 里面已经有 $1 \sim K$  这些数了，那么排成有序的次数我们可以知道了。

$K$ 的范围很小，我们可以用状压来表示 $f_{S}$ 为当前选的数集合为 $S$，搞出这个排列的最小次数。加入我们选出的是 $I=(i_1,i_2,\dots,i_K)$ ，我们要把它排成一个有序的 $J=(j_1, j_2,\dots,j_K)$ 。要最小这个操作步数。结论太强了：记 $m = \lceil \frac{K}{2} \rceil$，那么 $i_m = j_m$。明确一件事情：当 $I$ 确定的时候， $J$ 就被确定了。

记 $d(p)$ 表示 $|i_p - j_p|$ （就是起始位置到目标位置的距离），发现当 $\mathrm{popcnt(S)} = m$ 的时候，也就是正好加入了 $i_m = j_m$ 这个位置确定的数。其它位置的 $d(p)$ 考虑在这第 $m$ 个数加进来的时候计算。只需要分别讨论 $p$ 与 $m$ 的大小关系即可。

当 $p<m$ 的时候，$d(p) = j_p - i_p = (j_m + p - m) - i_p$ ；当 $m \leq p \leq K$ 的时候，$d(p) = i_p - j_p = i_p - (j_m + p - m)$。特别考虑 $i_m = j_m$ 时，若 $K$ 为奇数，$j_m$ 被抵消，若 $K$ 为偶数，$i_{m+1}$ 没被消掉。需要特判。

[sol D](https://atcoder.jp/contests/arc126/submissions/26841553)

## E

神题 +3

操作选的位置 $(i,j)$ 无序，但是每次 $+x$ 只统计一次，这个操作会一直进行到这些数都相同位置就无法操作了。那么每两个数之间的差值都会被填平。设 $F(A) = \sum_{i<j} |A_i - A_j|$，则 $\lim\limits_{n \to \infty} f(n) = \frac{F(A)}{2}$

问题就变成了，我们每次要单点该一个数，然后算 $F(A)$。这个 $i < j$ 限制是我们开始加上去的，挺无聊的，删掉。那么 $F'(A) = \frac{\sum_{(i,j) |A_i - A_j|}}{2}$。考虑怎么算，对于一个数，分别考虑它对比它小的数的贡献和比它大的数的贡献。假如有 $x$ 个数比它小，比它大的数的和为 $s$，那么贡献就是 $\frac{s \cdot x \cdot A_i}{2}$。

可以权值线段树，可以平衡树。

[sol E](https://atcoder.jp/contests/arc126/submissions/26843409)

懒得卡常了，直接 `define int long long`

## F

不会，极限+积分？？？？？都 2021 年了，还有无聊出题人出这种东西....

最后修改：2021 年 10 月 27 日

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

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

rlenitkthe
真好呢
暴力膜托
暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托%%%
TosakaUCW
前排狂暴膜托！
菲兹克斯喵
竟然……又找到一个校友……而且初中和高中都是同一个学校……天哪...
暴力膜托
快给黄明珍开个方子吧，可怜孩子补太猛了

VP: AtCoder Regular Contest 126 (ARC126)

tony102 • 2021 年 10 月 27 日

？？？`puts("nan")`

## A

贪心：

然后得到有多少 $5$ 的木棍，做完了。

[sol A](https://atcoder.jp/contests/arc126/submissions/26816051)

## B

巧妙题。

我们先来定义两条线段的大小比较。若两条线段分别为 $(x_1, y_1)$、$(x_2,y_2)$，首先按照 $x$ 的升序排，若 $x_1 = x_2$，则按照 $y$ 的升序排。

我们发现，若 $x_1 < x_2, y_1 < y_2$ ，那么两条线段没有交点。我们排序后，相当于在 $y$ 上要找到一个 LCS，要求 $O(n \log n)$ 找，单调栈即可。

[sol B](https://atcoder.jp/contests/arc126/submissions/26817520)

## C

神题 + 1

首先描述一下题目，可以给 $a_i$ 每次 $+1$ ，一共可以加 $k$ 次，要求操作完后 $x_{\max} = \gcd {(a_1,\dots,a_n)}$ 。

直接求，求不出。考虑枚举这个 $x$ ，平凡的情况是 $x \in [1, \max \{a_i\}]$ 。那么要求 $\forall i, x \mid a_i$。所以有 $(k-1)x < a_i \leq kx$。

假如 $a_i$ 在这个范围内，那么我们要对 $a_i$ 做的 $+1$ 操作就是 $kx-a_i$ 次。那么总共的就是：$\sum_{i} kx-a_i$

复杂度为预处理前缀和的复杂度、计算每一个 $x$ 的答案的复杂度之和：$O(n + A_{\max} \log {A_{\max}})$ 。

还有一种特殊情况，就是允许加到 $x > A_{\max}$ 。单独算一下就可以了。

[sol C](https://atcoder.jp/contests/arc126/submissions/26839077)

## D

~~麻雀知识~~

![清一色一气通贯.png](https://tony102.com/usr/uploads/2021/10/1541863020.png)

正经的。神题 + 2

看到 $K \leq 16$ 的数据范围，就是说最后要组成的这个 $\exists n, A_n = 1, A_{n+1} = 2,\dots,A_{n+K-1}=K$ 的这一段很短。

给的操作相当于冒泡排序，因为最后这个 $A$ 是要升序的，又是每次交换相邻两个数。

[sol D](https://atcoder.jp/contests/arc126/submissions/26841553)

## E

神题 +3

可以权值线段树，可以平衡树。

[sol E](https://atcoder.jp/contests/arc126/submissions/26843409)

懒得卡常了，直接 `define int long long`

## F

不会，极限+积分？？？？？都 2021 年了，还有无聊出题人出这种东西....

VP: AtCoder Regular Contest 126 (ARC126)

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

名人传

VP: AtCoder Beginner Contest 222(ABC222)

写在 CSP-S2021 前

机房标准化岚语发音对照

VP: AtCoder Beginner Contest 221(ABC221)

PETS游记

3D Gaussian Splatting for Real-Time Radiance Field Rendering

從四時陰陽之氣的變化，看五臟藏象與生理特點

CF101D Castle

PKUSC2021 Day2

VP: AtCoder Regular Contest 126 (ARC126)

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

VP: AtCoder Regular Contest 126 (ARC126)

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款