Codeforces Round 963 (Div. 2)

比赛链接

Problems	AC
A. Question Marks	○
B. Parity and Sum	○
C. Light Switches	○
D. Med-imize	⊕
E. Xor-Grid Problem	待补
F1. Dyn-scripted Robot (Easy Version)	⊕
F2. Dyn-scripted Robot (Hard Version)	⊕

B

给定一个包含 $n$ 个正整数的数组 $a$ 。

在一次操作中，您可以选择任何一对索引 $(i, j)$ ，使得 $a_i$ 和 $a_j$ 具有不同的奇偶校验，然后将较小的一个替换为它们的总和。更正式地：

• 如果是 $a_i < a_j$ ，则将 $a_i$ 替换为 $a_i + a_j$ ；
• 否则，将 $a_j$ 替换为 $a_i + a_j$ 。

找到使数组的所有元素具有相同奇偶校验所需的最少操作数。

按奇偶性分组然后 sort，从小到大扫偶数。如果小于当前最大的奇数，就把奇数加上他。

C

有一套公寓，由 $n$ 个房间组成，每个房间的灯最初都是关闭的。

为了控制这些房间的灯光，公寓的主人决定在房间里安装芯片，以便每个房间都只有一个芯片，并且芯片的安装时间不同。具体来说，这些时间由数组 $a_1, a_2, \ldots, a_n$ 表示，其中 $a_i$ 是在第 $i$ 个房间安装芯片的时间（以分钟为单位）。

安装芯片后，它会每 $k$ 分钟更改一次房间的灯光状态 - 它会打开灯 $k$ 分钟，然后关闭灯 $k$ 分钟，然后重新打开灯 $k$ 分钟，依此类推。换句话说，芯片在第 $a_i$ 、 $a_i + k$ 、 $a_i + 2k$ 、 $a_i + 3k$ 、 $\ldots$ 分钟为第 $i$ 个房间更改灯光状态。

公寓中所有房间的灯最早什么时候亮？

$2k$ 是一个周期，每个灯的区间都是 $[(a[i] \mod 2k), (a[i] \mod 2k) + k - 1]$。直接 $t = max(a[i])$ 开始，扫每一个灯，如果不在开灯周期里面就后移到下个开灯周期的起点，这样可以保证最小。最后再扫一遍检查是否合法。

D

给定两个正整数 $n$ 和 $k$ ，以及另一个包含 $n$ 个整数的数组 $a$ 。

在一个操作中，您可以选择 $a$ 中大小为 $k$ 的任意子数组，然后将其从数组中删除而不更改其他元素的顺序。更正式地，让 $(l, r)$ 成为子数组 $a _ l, a _ {l+1}, \ldots, a _ r$ 上的操作，使得 $r-l+1=k$ ，则执行此操作意味着将 $a$ 替换为 $[a _ 1, \ldots, a _ {l-1}, a _ {r+1}, \ldots, a _ n]$ 。

例如，如果是 $a=[1,2,3,4,5]$ ，并且我们在此数组上执行操作 $(3,5)$ ，它将变为 $a=[1,2]$ 。此外，操作 $(2, 4)$ 的结果为 $a=[1,5]$ ，操作 $(1,3)$ 的结果为 $a=[4,5]$ 。

您必须在 $a$ 的长度大于 $k$ (即 $|a| \gt k$ )时重复该操作。经过此过程后，数组 $a$ 中所有剩余元素的最大可能中位数是多少？

假如不存在删除操作，询问数列的中位数，就是二分答案，$O(n)$ 扫一遍，记录下 $>=$ 他的数量和 $<$ 他的数量。如果前者大于后者，就往更大的搜。

假如带上删除操作呢？首先最后剩下的数的数量是固定的 $m = (n - 1) % k + 1$。假如剩下的 $m$ 个数里面的第 $i$ 个数在原数组下标是 $j$，那 $i + 1$ 的下标只有可能是 $j + k + 1, j + 2k + 1 ……$

也就是说，剩下来这 $m$ 个数 (在原数组里的下标 - 1) mod k + 1 以后就是 1 ~ m。所以就可以 dp 了。

dp[j] = max(dp[j], dp[j - 1] + (a[i] >= x ? 1 : -1))

E

给定一个大小为 $n \times m$ 的矩阵 $a$ ，其每个单元格包含一个非负整数。位于矩阵 $i$ 行和 $j$ 列交点处的整数称为 $a_{i,j}$ 。

我们将 $f(i)$ 和 $g(j)$ 分别定义为 $i$ 行和 $j$ 列中所有整数的 XOR。在一次操作中，您可以：

• 选择任意行 $i$ ，然后为每个 $1 \le j \le m$ 分配 $a_{i,j} := g(j)$；
• 或选择任意列 $j$ ，然后为每个 $1 \le i \le n$ 分配 $a_{i,j} := f(i)$ 。

对矩阵的列 $2$ 应用操作的示例。

在此示例中，当我们对列 $2$ 应用操作时，此列中的所有元素都会更改：

• $a_{1,2} := f(1) = a_{1,1} \oplus a_{1,2} \oplus a_{1,3} \oplus a_{1,4} = 1 \oplus 1 \oplus 1 \oplus 1 = 0$
• $a_{2,2} := f(2) = a_{2,1} \oplus a_{2,2} \oplus a_{2,3} \oplus a_{2,4} = 2 \oplus 3 \oplus 5 \oplus 7 = 3$
• $a_{3,2} := f(3) = a_{3,1} \oplus a_{3,2} \oplus a_{3,3} \oplus a_{3,4} = 2 \oplus 0 \oplus 3 \oplus 0 = 1$
• $a_{4,2} := f(4) = a_{4,1} \oplus a_{4,2} \oplus a_{4,3} \oplus a_{4,4} = 10 \oplus 11 \oplus 12 \oplus 16 = 29$

您可以多次应用这些操作。然后，我们通过对所有相邻单元格对之间的绝对差求和来计算最终矩阵的 $\textit{beauty}$ 。

更正式地说，对于所有单元格 $(x, y)$ ，其结果为 $\textit{beauty}(a) = \sum|a_{x,y} - a_{r,c}|$ ；如果单元格相邻，则结果为 $(r, c)$ 。如果两个单元格共用一条边，则认为它们是相邻的。

在所有可获得的矩阵中找出最小值 $\textit{beauty}$ 。

由异或的自反性，可以很容易的将问题转化成：在一个 $(n + 1) \times (m + 1)$ 的矩阵中删除一行和一列，使得美丽值最小

F1 + F2

这是问题的简单版本。唯一的区别是此版本为 $k \le n$ 。只有解决了两个版本的问题后，您才能进行 hack。

给定一个 $Oxy$ 平面上的 $w \times h$ 矩形，其中点 $(0, 0)$ 位于矩形的左下角，点 $(w, h)$ 位于矩形的右上角。

您最初在点 $(0, 0)$ 处有一个机器人，脚本 $s$ 包含 $n$ 个字符。每个字符要么是 L、R、U 或 D，分别指示机器人向左、向右、向上或向下移动。

机器人只能在矩形内移动；否则，它将更改脚本 $s$ ，如下所示：

• 如果它尝试移动到垂直边界之外，它会将所有 L 字符更改为 R（反之亦然，所有 R 更改为 L）。
• 如果它尝试移动到水平边界之外，它会将所有 U 字符更改为 D（反之亦然，所有 D 更改为 U）。

然后，它将从无法执行的字符开始执行更改后的脚本。

脚本 $s$ 将连续执行 $k$ 次。对字符串 $s$ 的所有更改即使重复也会保留。在此过程中，机器人总共会移动到点 $(0, 0)$ 多少次？请注意，初始位置不计算在内。

学到了，在这类反射问题上，有一个套路是不改变操作本身，改变坐标系。例如在光线反射的时候直接让光线穿过去。

这题同理，让机器人直接穿过去，这样相当于在一个 (mod 2w, mod 2h) 的矩形里运动

设操作完一次序列会偏移到 dx, dy

对于 esay 版本，直接枚举操作次数，每次操作以后 会偏移 dx, dy，所以每次操作前 (-dx, -dy) 会对答案有贡献，map 统计即可。

对于 hard 版本，k 很大不能枚举操作，但是可以枚举初始的位置 x, y。

设进行一整轮后会偏移 dx, dy。进行到第 i 次偏移到 x, y。

则我们需要统计满足 $x + t \times dx \equiv 0(\bmod 2 w)$, $y + t \times dy \equiv 0(\bmod 2 h)$，且 $0 \leq t < k$ 的 $t$ 的数量

根据基础数论知识，假如有方程 $a x + b \equiv 0(\bmod c)$，我们可以在 $d=\operatorname{gcd}(a, c) \mid b$ 时转化为 $x \equiv$ $-\frac{b}{d}\left(\frac{a}{d}\right)^{-1}\left(\bmod \frac{c}{d}\right)$

于是问题转化为 $t \equiv x^{\prime}\left(\bmod M_x\right)$, $t \equiv y^{\prime}\left(\bmod M_y\right)$

使用 exCRT 合并：设 $t=p M_x+x^{\prime}$ ，则 $p M_x+x^{\prime} \equiv y^{\prime}\left(\bmod M_y\right)$