Codeforces Round 951 (Div. 2)

比赛链接

Problems	AC
A. Guess the Maximum	○
B. XOR Sequences	○
C. Earning on Bets	○
D. Fixing a Binary String	○
E. Manhattan Triangle	○
F. Kostyanych’s Theorem

A

Alice 和 Bob 想出了一个相当奇怪的游戏。他们有一个整数数组 $a_1, a_2,\ldots, a_n$ 。Alice 选择某个整数 $k$ 并将其告诉 Bob，然后发生以下情况：

• Bob 选择两个整数 $i$ 和 $j$ ( $1 \le i < j \le n$ )，然后在整数 $a_i, a_{i + 1},\ldots, a_j$ 中找到最大值；
• 如果获得的最大值严格大于 $k$ ，则 Alice 获胜，否则 Bob 获胜。

帮助 Alice 找到她保证获胜的最大值 $k$ 。

考虑长度为 2 的时候即可

Code

B

给定两个不同的非负整数 $x$ 和 $y$ 。考虑两个无限序列 $a_1, a_2, a_3, \ldots$ 和 $b_1, b_2, b_3, \ldots$ ，其中

• $a_n = n \oplus x$ ;
• $b_n = n \oplus y$ 。

您的任务是找出序列 $a$ 和 $b$ 的最长公共子段的长度。

想象一下，假如 x 是 111 0011，y 是 000 0011。那我们必然可以找到一组 (i, j) 使得 i xor x = j xor y。并且只要 (i, j) 的后 4 位都为 0，将前几位构造到 xor 后相同，那么就能无限加下去，知道第 5 位改变为止。所以答案为 lowbit(x ^ y)

Code

C

你被邀请玩一个游戏。在这个游戏中，有 $n$ 个可能的结果，对于每个结果，你必须下注一定数量的硬币。如果第 $i$ 个结果获胜，你将获得等于你对该结果下注的硬币数量乘以 $k _ i$ 的硬币数量。请注意， $n$ 个结果中只有一个会获胜。

你的任务是确定如何分配硬币，以便在任何获胜结果出现时你都能领先。更正式地说，你对所有结果下注的硬币总数必须严格小于每个可能获胜结果收到的硬币数量。

设总花费为 $S$

任意结果的收益必须大于总支出，$x_i k_i > S$，即 $x_i > \frac{S}{k_i}$

两边求和，$\sum{x_i} > \sum{\frac{S}{k_i}}$，即 $S > \sum{\frac{S}{k_i}}$，即 $1 > \sum{\frac{1}{k_i}}$

即 $lcm > \sum{\frac{lcm}{k_i}}$

Code

D

对于 01 串 $s$, 能否将 $s$ 分成 $s=s_1+s_2$, 使得 $s^{\prime}=s_2+r e v\left(s_1\right)$ 是 01 交替 $\mathbf{k}$ 次出现的。

含义是字符串形如 $\underbrace{00 \cdots 011 \cdots 100 \cdots 011 \cdots 1}_{k \uparrow} \cdots$, 保证 $k$ 是字符串总长 $n$ 的一个因子。

E

两点 $(x _ 1, y _ 1)$ 和 $(x _ 2, y _ 2)$ 之间的曼哈顿距离定义为：

$$
|x _ 1 - x _ 2| + |y _ 1 - y _ 2|.
$$

我们称曼哈顿三角形为平面上的三个点，每对点之间的曼哈顿距离相等。

给定一组成对的不同点和一个偶数 $d$ 。您的任务是找到由给定集合中的三个不同点组成的任何曼哈顿三角形，其中任何一对顶点之间的曼哈顿距离等于 $d$ 。

假设第一个点是 $O_1$，到 $O_1$ 曼哈顿距离相同点的构成的是一个旋转 45 度的正方形。画一下图你会发现，当 $O_2$ 在 $O_1$ 的正方形上滑动的时候，要么 $O_{1}O_{2}$ 的斜率为 $\pm 1$，要么 $O_{1}O_{3}$ 的斜率为 $\pm 1$。

换言之，我们可以枚举 $O_1$，然后在它的 斜率 $\pm 1$ 方向上找第二点 $O_2$。找到第二点以后，在两个矩形的交线段上面找第三点。

关于这个找第三点的过程。以交线段斜率为 $1$ 举例，在交线段上的点都有相同的 $b = y - x$，那么可以按照这些点在斜率为 $-1$ 的直线上的截距 $b’ = y + x$ 排序，每次二分查找有无在 $\left[ x_{O_1} + y_{O_1}, x_{O_2} + y_{O_2} \right] $ 的点即可

Note: 这其实完成了曼哈顿距离和切比雪夫距离的转换，见常见距离算法小记

Code

F

这是一个交互式问题。

Kostyanych 选择了一个具有 $n$ 个顶点的完全无向图 $^{\dagger}$ ，然后从中移除了恰好 $(n - 2)$ 条边。您可以提出以下类型的查询：

• “？ $d$ ” — Kostyanych 告诉您度数至少为 $d$ 的顶点 $v$ 的数量。在所有可能的此类顶点中，他选择度数最小的顶点，如果有多个这样的顶点，则选择数量最小的顶点。他还告诉您图中另一个顶点的数量，该顶点与 $v$ 没有边连接（如果未找到，则报告 $0$ ）。在所有可能的此类顶点中，他选择数量最小的顶点。然后他删除顶点 $v$ 以及从该顶点出来的所有边。如果未找到所需的顶点 $v$ ，则报告“ $0\ 0$ ”。

在最多 $n$ 次查询中，在原始图中找到一条汉密尔顿路径 $^{\ddagger}$ 。可以证明，在这些约束条件下，汉密尔顿路径始终存在。

$^{\dagger}$ 完全无向图是任意一对不同顶点之间恰好有一条无向边的图。因此，具有 $n$ 个顶点的完全无向图包含 $\frac{n(n-1)}{2}$ 条边。

$^{\ddagger}$ 图中汉密尔顿路径是一条恰好经过每个顶点一次的路径。