P9170 [省选联考 2023] 填数游戏

众所周知，Alice 和 Bob 是一对好朋友。今天，他们约好一起玩游戏。 一开始，他们各自有一张空白的纸条。接下来，他们会在纸条上依次写 $n$ 个 $[1,m]$ 范围内的正整数。等 Alice 写完，Bob **在看到 Alice 写的纸条之后开始写他的纸条**。 Alice 需要保证她写下的第 $i$ 个数在集合 $S_{i}$ 中，Bob 需要保证他写下的第 $i$ 个数在集合 $T_{i}$ 中。**题目保证** $1 \leq\left|S_{i}\right|,\left|T_{i}\right| \leq 2$ 。 Alice 喜欢相同，因此，她希望她写下的数与 Bob 写下的数对应位置相同的个数尽量多。Bob 喜欢不同，因此，他希望他写下的 $n$ 个数 $b_{1}, \ldots, b_{n}$ 互不相同。在此基础上，Bob 希望他写下的数与 Alice 写下的数对应位置相同的个数尽量少。 即设 Alice 写下的数为 $a_{1}, \ldots, a_{n}$，Bob 写下的数为 $b_{1}, \ldots, b_{n}$，记 $X$ 为满足 $1 \leq i \leq n, a_{i}=b_{i}$ 的下标 $i$ 的个数，则 - Alice 希望最大化 $X,$ - Bob 在**保证 $b_{1}, \ldots, b_{n}$ 互不相同的前提下**希望最小化 $X$。 你首先想知道 Bob 能否保证他写下的 $n$ 个数互不相同。如果 Bob 能够做到，你想知道**在双方均采取最优策略的前提下** $X$ 的值会是多少。

无

无

**【样例 1 解释】** 在这组样例中，$S_{1}=\{3\}, S_{2}=T_{1}=\{1,2\}, S_{3}=T_{3}=\{3,4\}, T_{2}=\{2,3\}$。Alice 的填法有 $4$ 种，列举如下： 第一种：$a_{1}=3,a_{2}=1,a_{3}=3$。 第二种：$a_{1}=3,a_{2}=1,a_{3}=4$。 第三种：$a_{1}=3,a_{2}=2,a_{3}=3$。 第四种：$a_{1}=3,a_{2}=2,a_{3}=4$。 由于 Bob 必须保证他所填的数互不相同，所以他有以下填法: 第一种：$b_{1}=1,b_{2}=2,b_{3}=3$。 第二种：$b_{1}=2,b_{3}=3,b_{3}=4$。 第三种：$b_{1}=1,b_{2}=2,b_{3}=4$。 第四种：$b_{1}=1,b_{2}=3,b_{3}=4$。 若 Alice 选择第一种填法，则 Bob 为最小化 $X$，选择第二种填法，得到 $X=0$。 若 Alice 选择第二种填法，则 Bob 为最小化 $X$，选择第一种填法，得到 $X=0$。 若 Alice 选择第三种填法，则 Bob 为最小化 $X$，选择第一种填法，得到 $X=0$。 若 Alice 选择第四种填法，则 Bob 无论选择哪种填法，$X$ 均不小于 $1$。 因此，Alice 为最大化 $X$ 的值，她会选择第四种填法。 **【子任务】** 表格中 $\sum n,\sum m$ 分别表示同个测试点内所有测试数据的 $n$ 总和和 $m$ 总和。 $\sum n^{2}, \sum m^{2}, \sum n^{3}, \sum m^{3}$ 的含义类似。  特殊性质 A：对于任何 $1 \leq i \leq n,S_i$ 和 $T_i$ 互不相交，即 $S_i \cap T_i=\emptyset$。 特殊性质 B：$n \geq 3$，且对于任何 $1 \leq i