Codeforces Round 953 (Div. 2)

比赛链接

Problems	AC
A. Alice and Books	○
B. New Bakery	○
C. Manhattan Permutations	○
D. Elections	○
E. Computing Machine	⊕
F. Large Graph	⊕

A

Alice 有 $n$ 本书。第 $1$ 本书包含 $a_1$ 页，第 $2$ 本书包含 $a_2$ 页，$\ldots$, 第 $n$ 本书包含 $a_n$ 页。Alice 执行以下操作：

• 她将所有书分成两个非空堆。因此，每本书最终都恰好属于两个堆中的一个。
• Alice 在每个堆中阅读了一本编号最高的书。

Alice 非常喜欢读书。通过将书分成两个堆，帮助她找出她可以阅读的最大总页数。

Code

B

Bob 决定开一家面包店。开业当天，他烤了 $n$ 个面包出售。一个面包的正常价格是 $a$ 个硬币，但为了吸引顾客，Bob 组织了以下促销活动：

• Bob 选择某个整数 $k$ ( $0 \le k \le \min(n, b)$ )。
• Bob 以修改后的价格出售前 $k$ 个面包。在这种情况下，售出的第 $i$ 个面包 ( $1 \le i \le k$ ) 的价格为 $(b - i + 1)$ 个硬币。
• 其余 $(n - k)$ 个面包以每个 $a$ 个硬币的价格出售。

请注意， $k$ 可以等于 $0$ 。在这种情况下，Bob 将以每个 $a$ 个硬币的价格出售所有包子。

帮助 Bob 确定通过出售所有 $n$ 个包子他可以获得的最大利润。

Code

C

我们将排列 $^{\dagger}$ $p$ 的曼哈顿值称为表达式 $|p _ 1 - 1| + |p _ 2 - 2| + \ldots + |p _ n - n|$ 的值。

例如，对于排列 $[1, 2, 3]$ ，曼哈顿值为 $|1 - 1| + |2 - 2| + |3 - 3| = 0$ ，对于排列 $[3, 1, 2]$ ，曼哈顿值为 $|3 - 1| + |1 - 2| + |2 - 3| = 2 + 1 + 1 = 4$ 。

给定整数 $n$ 和 $k$ 。找出长度为 $n$ 的排列 $p$ ，使得其曼哈顿值等于 $k$ ，或者确定不存在这样的排列。

在评论区大家都说这个 C 题比 DE 简单，但是感觉是个很直觉的题。

考虑最大化的话肯定是 1 和 n 交换，2 和 n - 1 交换，以此类推这个形式。

如果某一次这样移太大了就从后面那一个开始移就行了

Code

D

贝尔兰正在进行选举。有$n$位候选人参加选举，编号从1到$n$。第$i$位候选人有$a_i$位支持者会投票给他。另外，有$c$位尚未决定投给谁的人，我们称他们为未决定者。未决定者将投票给编号最小的候选人。

获得最多选票的候选人将赢得选举，如果有多名候选人获得相同的最多选票，则编号最小的候选人获胜。

你觉得这次选举太无聊和可预测了，所以你决定排除一些候选人。如果你不允许编号为$i$的候选人参加选举，那么他所有的$a_i$位支持者将变成未决定者，并投票给编号最小的候选人。

你想知道，对于每个从1到$n$的候选人来说，使编号为$i$的候选人赢得选举，最少需要排除多少名候选人。

首先，对于 i 这个候选人，如果他是最大的，那么就不用操作。

如果 i 不是最大的，那么所有大于 a[i] 的 a[j] 都要被删去。但是被删去以后的选票都加到了 a[1] 上面。本身 a[j] 已经大于 a[i] 了，加上 a[1] + c 就更会大于 a[i]，以此出发，a[1] 到 a[i - 1] 都要被删去。

因此对于每个 i，我们记 x = sum[i] + c，我们用一个堆维护 a[i + 1] ~ a[n]，每次把堆顶中最大的取出来加到 x 上面，直到 x 成为最大值。

Note: 可以发现右边这些数里面最多只删一个最大值就够了，所以其实答案只有可能是 0，i，i + 1

Code

E

萨莎有两个相同长度为$n$的二进制字符串$s$和$t$，它们由字符0和1组成。

还有一台计算机，它可以对长度为$k$的二进制字符串$a$和$b$执行两种类型的操作：

1. 如果$a_i = a_{i + 2} = 0$，那么你可以将$b_{i + 1}$赋值为1 ($1 \le i \le k - 2$)。
2. 如果$b_i = b_{i + 2} = 1$，那么你可以将$a_{i + 1}$赋值为1 ($1 \le i \le k - 2$)。

萨莎对以下问题感兴趣：如果我们考虑字符串$a=s_l s_{l+1} \ldots s_r$和字符串$b=t_l t_{l+1} \ldots t_r$，使用计算机后字符串$a$中最多可以有多少个字符1。由于萨莎非常好奇但又很懒，所以你需要回答他感兴趣的多个$(l_i, r_i)$对。

最优的操作肯定是先做 1，再做 2。而且不会反复操作。既然不会反复操作，你可以先对整个序列操作，每个询问只会有区间最左最右的一些数会被改变，暴力即可。

Code

F

给定一个长度为$n$的数组$a$。构造一个$n \times n$的方阵$b$，其中第$i$行包含数组$a$向右循环移动$(i - 1)$次的结果。例如，对于数组$a = [3, 4, 5]$，得到的矩阵是

$$
b = \begin{bmatrix}
3 & 4 & 5 \
5 & 3 & 4 \
4 & 5 & 3 \
\end{bmatrix}
$$

接下来构造如下图：

• 该图包含$n^2$个顶点，每个顶点对应于矩阵中的一个元素。记与元素$b_{i,j}$对应的顶点为$(i, j)$。
• 当且仅当$|i_1 - i_2| + |j_1 - j_2| \le k$ 且$\gcd(b_{i_1, j_1}, b_{i_2, j_2}) > 1$时，在顶点$(i_1, j_1)$和$(i_2, j_2)$之间画一条边，其中$\gcd(x, y)$表示整数$x$和$y$的最大公约数。

你的任务是计算所得图中的连通分量的数量。

连通分量是图中的一个顶点集合，其中任何一个顶点可以通过边到达集合中的任意其他顶点，并且添加任何其他顶点到集合中会违反此规则。

曼哈顿距离的几何意义就是一个旋转了 45度 的正方形。因为矩阵的构造方式是特殊的，所以每条斜对角线上的元素都是相同的。将这 $2n - 1$ 条斜对角线自左下到右上标号 $1, 2, \ldots, 2n - 1$，那么曼哈顿距离的限制就转化为每条斜对角线和上下相邻的各 k 条斜对角线。

那么现在转化为了一个序列大小为 $m = 2n - 1$ 的序列问题。不需要同时考虑两个方向，从左到右做，维护一个 las[p] 代表 p 这个质因子上次出现的位置，如果 i - las[p] <= k 则连边即可。

Code