Codeforces Round 956 (Div. 2) and ByteRace 2024

印度 Round = 拉马努金 Round

要做出题需要一点灵感，但是在某些方面还挺有启发性的。

比赛链接

Problems	AC
A. Array Divisibility	○
B. Corner Twist	○
C. Have Your Cake and Eat It Too	○
D. Swap Dilemma	○
E. I Love Balls	⊕
F. array-value	⊕
G. Your Loss

A

如果满足以下条件，则整数数组 $a _ 1,a _ 2,\cdots,a _ n$ 是整数 $k$ 的优美对象：

• $a _ {j}$ 与所有 $j$ 之和，使得 $j$ 是 $k$ 的倍数，而 $1 \le j \le n $ 本身是 $k$ 的倍数。
• 更正式地说，如果对于所有 $1 \le j \le n$ ， $\sum _ {k | j} a _ {j}$ 都能被 $k$ 整除，则数组 $a$ 是对于 $k$ beautiful。这里，符号 ${k|j}$ 表示 $k$ 能整除 $j$ ，也就是说， $j$ 是 $k$ 的倍数。

给定 $n$ ，找到一个正非零整数数组，每个元素都小于或等于 $10^5$ ，并且对于所有 $1 \le k \le n$ beautiful。

可以证明答案总是存在的。

输出 1 到 n 即可。

Code

B

您将获得两个数字网格 $a$ 和 $b$ ，行数为 $n$ ，列数为 $m$ 。网格中的所有值均为 $0$ 、 $1$ 或 $2$ 。

您可以对 $a$ 执行任意次以下操作：

• 在网格中选取任意子矩形，其长度和宽度为 $\ge 2$ 。您可以选择整个网格作为子矩形。
• 子矩形有四个角。取所选子矩形的任意对角，并将 $1$ 添加到它们的值中，以 $3$ 为模。
• 对于未选中的角对，将 $2$ 添加到它们的值中，以 $3$ 为模。

请注意，此操作仅更改所选子矩形的角的值。

是否可以通过多次(可能是零次)应用上述操作将网格 $a$ 转换为网格 $b$ ？

一个显然的性质是，所有的操作都可以被分解成若干个 2 * 2 的操作

Code

C

Alice、Bob 和 Charlie 想要分享一块切成 $n$ 块的矩形蛋糕。每个人认为每块蛋糕的价值都不同。Alice 认为第 $i$ 块蛋糕的价值为 $a_i$ ，Bob 认为是 $b_i$ ，Charlie 认为是 $c_i$ 。

所有 $a_i$ 、所有 $b_i$ 和所有 $c_i$ 的总和相同，等于 $tot$ 。

鉴于每个人每块蛋糕的价值，您需要给每个人一块连续的蛋糕。换句话说，这些子数组左端和右端的索引（分配给每个人的切片）可以分别表示为 Alice、Bob 和 Charlie 的 $(l_a, r_a)$ 、 $(l_b, r_b)$ 和 $(l_c, r_c)$ 。除法需要满足以下约束：

• 没有一块分配给超过一个人，即 $[l_a,\ldots,r_a]$ 、 $[l_b, \ldots, r_b]$ 和 $[l_c, \ldots, r_c]$ 之间的任何两个子数组都不相交。
• $ \sum_{i = l_a}^{r_a} a_i, \sum_{i = l_b}^{r_b} b_i, \sum_{i = l_c}^{r_c} c_i \geq \lceil \frac{tot}{3} \rceil$ 。

直接枚举

Code

D 逆序对、树状数组

给定两个不同的正整数数组 $a$ 和 $b$ ，长度为 $n$ ，我们希望使这两个数组相同。如果对于所有 $1 \le i \le k$ ，都是 $x_i = y_i$ ，则两个长度为 $k$ 的数组 $x$ 和 $y$ 相同。

现在，您只需一步，即可在 $a$ ( $l \le r$ ) 中选择某个索引 $l$ 和 $r$ 并交换 $a_l$ 和 $a_r$ ，然后在 $b$ 中选择某个索引 $p$ 和 $q$ ( $p \le q$ )，使得 $r-l=q-p$ 并交换 $b_p$ 和 $b_q$ 。

是否可以使两个数组相同？

可以每次都用长度为 2 的进行交换，那相当于上下同时进行冒泡排序

只要排序次数相同，即逆序对数相同，就能同时到达有序的状态

upd: 赛后发现普通清空树状数组容易被卡，需要用时间戳清空

Code

E 期望、组合数学

Alice 和 Bob 正在玩游戏。有 $n$ 个球，其中 $k$ 个是特殊的。每个球都有一个与之关联的值。

玩家轮流玩游戏。在每个回合中，玩家随机挑选一个球并将球的值添加到他们的分数中，游戏开始时的分数为 $0$ 。选定的球将从游戏中移除。如果球是特殊的，则同一玩家在至少剩余一个球的情况下进行下一轮。如果挑选的球不是特殊的，则下一个玩家轮到他们。

他们玩这个游戏，直到游戏中没有剩余的球。Alice 先玩。

求出游戏结束时两位玩家的预期分数，模数为 $10^9+7$ 。

正式地，设 $M = 10^9+7$ 。可以证明答案可以表示为不可约分数 $\frac{p}{q}$ ，其中 $p$ 和 $q$ 为整数和 $q \not \equiv 0 \pmod{M}$ 。输出等于 $p \cdot q^{-1} \bmod M$ 的整数。换句话说，输出这样一个整数 $x$ ，即 $0 \le x < M$ 和 $x \cdot q \equiv p \pmod{M}$ 。

神笔题，这场感觉都是脑筋急转弯。

整个过程相当于先选完普通的球，然后把特殊的球放进去插空。

那么现在我们先来考虑普通的球，假如 $n$ 个都是普通球

Alice 先选的话，他能选到 $\lfloor\frac{n + 1}{2}\rfloor$ 个球，每个球的价值平均下来是 $\frac{\sum v_i}{n}$。所以他的期望收益是 $\lfloor\frac{n + 1}{2}\rfloor \cdot \frac{\sum v_i}{n}$

现在考虑有特殊球的情况，相当于 $n - k$ 个普通球的序列有 $n - k + 1$ 个空，每个特殊球随机插空。

假如先拿普通球，Alice 期望拿 $\lfloor\frac{n - k}{2}\rfloor$ 个球，那么 Alice 期望有 $\lfloor\frac{n - k}{2}\rfloor + 1$ 个空。

总共是 $k$ 个特殊球，一共是 $n - k + 1$ 个空，那么每个空期望有 $\frac{k}{n - k + 1}$ 个特殊球。

那么在 Alice 这边，期望的空的数量乘上每个空期望的特殊球数量，就是 Alice 一共期望遇到的特殊球数量：$(\lfloor\frac{n - k}{2}\rfloor + 1) \cdot \frac{k}{n - k + 1}$

所以 Alice 的期望收益是：

$$
\frac{(\lfloor\frac{n - k}{2}\rfloor + 1) \cdot k}{n - k + 1} \cdot \frac{\sum_{i = 1}^{k}v_i}{k} + \lfloor\frac{n - k + 1}{2}\rfloor \cdot \frac{\sum_{i = k + 1}^{n}v_i}{n - k}
$$

Code

F 二分、Trie

您有一个非负整数数组 $a_1, a_2, \ldots, a_n$ 。

长度 $\ge 2$ 的子数组的值, $a[l, r] = [a_l, a_{l+1}, \ldots, a_r]$ 是 $a_i \oplus a_j$ 的最小值，使得 $l \le i < j \le r$ ，其中 $\oplus$ 是异或 (排他或) 运算符。

您必须在所有长度为 $\ge 2$ 的子数组中找到 $k$ -th 最小的值。

有一个观察是这个东西是随着区间变大单调不增的，也就是说我们可以固定一端，通过某个方式查询另一个端点的位置。

首先二分答案，这样你要查的值就确定了。从左往右对于每个数，在 Trie 上面贪心找答案，然后加入 Trie。

Implemention 有细节，具体看代码。

总结：Trie 可以类似线段树维护信息，因为不好维护区间信息，常常是搭配动态加入使用

Code