CF2057A 翻译

Bearbrother18 · 2025-01-23 21:05:15 · 个人记录

题目描述

给出 n 行 m 列的矩阵。将数字 0,1, \ldots,n\cdot m-1 在表中排列出来，并且每个数字只能使用一次。换句话说，需要你最大化：

\sum_{i=1}^n \ {mex}(\{a_{i,1},a_{i,2}\ldots,a_{i,m}\})+\sum_{j=1}^m(\{a_{1,j},a_{2,j},\ldots,a_{n,j}\})

我们定义 a_{i,j} 表示矩阵的第 i 行第 j 列，请你求出所有行和列中可以达到的 Mex 的最大值。

注意：排除（Mex）的最小整数合集 c_1,c_2,\ldots,c_k 定义为最小的非负整数 x 不会出现在集合 c 中。

例如：

第一行输入一个整数 t 表示测试的组数。接下来的 t 行每行输入两个整数 n 和 m 分别表示表的行数和列数。

对于每一组数据，输出一个 \operatorname {mex} 可能跨所有行和列的最大总和。

在第一组样例中，唯一的元素是 0，并且第一行中 \operatorname{mex} 的总和和第一列中 \operatorname{mex} 的总和是 \operatorname{mex}(\{0\})+\operatorname{mex}(\{0\})=1+1=2。

在第二组样例中，最佳的表的可能如下图所示：

## 数据范围对于所有数据保证 $1\le t \le 1000$，$1\le n,m\le 10^9$。