#5750. 「CCO 2026」Asymmetry

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

译自 CCO 2026 Day2 T1「Asymmetry」。

Alice 和 Bob 在一个 $N$ 行 $M$ 列的网格上玩游戏，其中 $M$ 是偶数。游戏中还有一个正整数 $K$。最初，网格的每个单元格都包含一个在 $0$ 到 $K$ 之间（包含 $0$ 和 $K$）的数值，且所有单元格均未被标记。两名玩家轮流进行操作，由 Alice 先手。当当前玩家无法进行操作时，游戏结束。

在每名玩家的轮次中，他们需要选择网格中一个未被标记的单元格以及一个在 $0$ 到 $K$ 之间（包含 $0$ 和 $K$）的整数 $a$。随后，他们将该单元格的数值设定为 $a$，并标记该单元格所在列的所有单元格（包括所选的单元格）。

网格的不对称度定义为：网格中每个单元格与其关于网格中轴线水平镜像对称的单元格之间数值差的绝对值之和。更具体地说，不对称度计算公式如下：

$$\sum_{1 \leq i \leq N}\left(\sum_{1 \leq j \leq M / 2}\left|g_{i, j}-g_{i, M-j+1}\right|\right),$$

其中 $g_{i,j}$ 表示从上往数第 $i$ 行、从左往数第 $j$ 列的单元格数值。例如，下方这个 $2 \times 4$ 的网格的不对称度为 $|8-0| + |4-2| + |6-6| + |7-9| = 12$。

$$\begin{array}{|l|l|l|l|} \hline 8 & 4 & 2 & 0 \\ \hline 6 & 7 & 9 & 6 \\ \hline \end{array}$$

Alice 希望在游戏结束时最小化网格的不对称度，而 Bob 则希望将其最大化。如果两名玩家均采取最优策略，最终网格的不对称度是多少？

输入格式

第一行包含三个由空格隔开的整数 $N, M$ 和 $K$ $(1 \leq N, M \leq 2000, M$ 为偶数$,1 \leq K \leq 10^9)$。

接下来 $N$ 行，每行包含 $M$ 个整数。其中第 $i$ 行包含整数 $g_{i,1}, \dots, g_{i,M}$ $(0 \leq g_{i,j} \leq K)$，表示从上往数第 $i$ 行中从左到右每个单元格的数值。

输出格式

输出一个整数，表示在 Alice 和 Bob 均采取最优策略的情况下，最终网格的不对称度。

样例 1

输入

3 2 1
1 0
1 0
0 0

输出

2

网格只有 $2$ 列，因此每名玩家各操作 $1$ 次。由 Alice 先手，她可以执行以下操作：

• 选择第一列中某个初始值为 $1$ 的单元格，并将其值设为 $0$。此时 Bob 的最优操作是将第二列同一行的单元格数值设为 $1$。最终网格将与原始网格类似，但前两行中的某一行其 $0$ 和 $1$ 的位置发生了交换。此类网格的不对称度为 $|1-0| + |0-1| + |0-0| = 2$。
• 选择第二列在前两行中的某个单元格，并将其值设为 $1$。此时 Bob 的最优操作是将第一列同一行的单元格数值设为 $0$。最终网格的不对称度同样为 $2$。
• 选择第三行的某个单元格，并将其值设为 $1$。此时 Bob 的最优操作是将第三行的另一个单元格数值设为 $0$。请注意，所选的单元格原本的数值就是 $0$，此类操作是被允许的。最终网格的每一行都会包含一个 $0$ 和一个 $1$，导致不对称度为 $3$。
• 选择任意单元格并将其数值设为其当前的原始值。此时 Bob 的最优操作是在剩余的未标记列中，将第三行的单元格数值设为 $1$。最终网格的每一行都会包含一个 $0$ 和一个 $1$，导致不对称度为 $3$。

我们可以看到，无论 Alice 如何进行她的操作，Bob 都能通过某种方式使得不对称度至少为 $2$。如果 Alice 最优地选择她的第一步操作，她可以确保 Bob 无法让最终的不对称度超过 $2$。因此，在两名玩家均采取最优策略的情况下的不对称度为 $2$。

样例 2

输入

1 10 21
4 2 0 6 7 6 9 9 10 21

输出

55

网格只有一行，因此在每一步操作中，当前玩家都会选择一个未标记的单元格，并将其值设为 $0$ 到 $21$ 之间的任意整数。当每名玩家各完成 $5$ 次操作后，所有 $10$ 个单元格都将被标记，游戏结束。

样例 3

输入

4 6 986754321
219759391 882760615 762656191 423465948 621463211 136889371
215621504 385106915 740086459 417915224 551800597 572994766
176308756 365311996 635683450 907755406 590000050 586083433
607011121 457147795 837558908 684766852 946836347 303039615

输出

3972378656

请注意，答案可能会超过 $32$ 位整数的范围。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	$N$ 的范围	$M$ 的范围	$K$ 的范围
$1$	$8$	$N = 1$	$2 \leq M \leq 2000$	$1 \leq K \leq 10^9$
$2$	$12$	$1 \leq N \leq 2000$	$M = 2$	$K = 1$
$3$	$12$			$1 \leq K \leq 10$
$4$	$12$			$1 \leq K \leq 10^9$
$5$	$16$		$2 \leq M \leq 2000$	$K = 1$
$6$	$16$			$1 \leq K \leq 10$
$7$	$24$			$1 \leq K \leq 10^9$