A6637. 「联合省选 2023」填数游戏
编程题
NOI/NOI+/CTSC
知识点
题目描述
众所周知，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}, \cdots, b_{n}$ 互不相同。在此基础上，Bob 希望他写下的数与 Alice 写下的数对应位置相同的个数尽量少。
即设 Alice 写下的数为 $a_{1}, \cdots, a_{n}$，Bob 写下的数为 $b_{1}, \cdots, b_{n}$，记 $X$ 为满足 $1 \leq i \leq n, a_{i}=b_{i}$ 的下标 $i$ 的个数，则
- Alice 希望最大化 $X,$
- Bob 在**保证 $b_{1}, \cdots, b_{n}$ 互不相同的前提下**希望最小化 $X$。
你首先想知道 Bob 能否保证他写下的 $n$ 个数互不相同。如果 Bob 能够做到，你想知道**在双方均采取最优策略的前提下** $X$ 的值会是多少。
一开始，他们各自有一张空白的纸条。接下来，他们会在纸条上依次写 $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}, \cdots, b_{n}$ 互不相同。在此基础上，Bob 希望他写下的数与 Alice 写下的数对应位置相同的个数尽量少。
即设 Alice 写下的数为 $a_{1}, \cdots, a_{n}$，Bob 写下的数为 $b_{1}, \cdots, b_{n}$，记 $X$ 为满足 $1 \leq i \leq n, a_{i}=b_{i}$ 的下标 $i$ 的个数，则
- Alice 希望最大化 $X,$
- Bob 在**保证 $b_{1}, \cdots, b_{n}$ 互不相同的前提下**希望最小化 $X$。
你首先想知道 Bob 能否保证他写下的 $n$ 个数互不相同。如果 Bob 能够做到，你想知道**在双方均采取最优策略的前提下** $X$ 的值会是多少。
输入格式
**本题有多组测试数据**。
输入的第一行包含一个正整数 $T$，表示测试数据组数。
接下来包含 $T$ 组数据，每组数据的格式如下：
第一行包含两个正整数 $n,m$，表示纸条上需要写的数的个数和数的值域。
接下来 $n$ 行，每行输入的第一个整数为 $\left|S_{i}\right|$ 表示集合 $S_{i}$ 的元素个数，接下来输入 $\left|S_{i}\right|$ 个正整数描述 $S_{i}$ 中的元素。
接下来 $n$ 行，每行输入的第一个整数为 $\left|T_{i}\right|$ 表示集合 $T_{i}$ 的元素个数，接下来输入 $\left|T_{i}\right|$ 个正整数描述 $T_{i}$ 中的元素。
输入的第一行包含一个正整数 $T$，表示测试数据组数。
接下来包含 $T$ 组数据，每组数据的格式如下：
第一行包含两个正整数 $n,m$，表示纸条上需要写的数的个数和数的值域。
接下来 $n$ 行，每行输入的第一个整数为 $\left|S_{i}\right|$ 表示集合 $S_{i}$ 的元素个数，接下来输入 $\left|S_{i}\right|$ 个正整数描述 $S_{i}$ 中的元素。
接下来 $n$ 行，每行输入的第一个整数为 $\left|T_{i}\right|$ 表示集合 $T_{i}$ 的元素个数，接下来输入 $\left|T_{i}\right|$ 个正整数描述 $T_{i}$ 中的元素。
输出格式
对于每组测试数据输出一行：若 Bob 无法做到他写下的 $n$ 个数互不相同，输出
-1；否则输出在双方均予取最优策略的前提下 $X$ 的值。输入输出样例
输入 #1
1 3 4 1 3 2 1 2 2 3 4 2 1 2 2 2 3 2 3 4
输出 #1
1
说明/提示
表格中 $\sum n,\sum m$ 分别表示同个测试点内所有测试数据的 $n$ 总和和 $m$ 总和。 $\sum n^{2}, \sum m^{2}, \sum n^{3}, \sum m^{3}$ 的含义类似。
- 测试点 $1\sim 5$：$T\le 20,n,m\le 10$
- 测试点 $6\sim 11$：$n,m\le 200,\sum n^3,\sum m^3\le 4\cdot 10^7$
- 测试点 $12,13$：$n,m\le 2000,\sum n^2,\sum m^2\le 4\cdot 10^7$
- 测试点 $14\sim 22$：$n,m\le 1.5\cdot 10^5,\sum n,\sum m\le 3\cdot 10^5$
- 测试点 $23\sim 25$：$n,m\le 10^6,\sum n,\sum m\le 1.5\cdot 10^6$
- 测试点 $6,14$ 具有性质 A
- 测试点 $7,15,16$ 具有性质 B
- 测试点 $8,17,18$ 具有性质 C
- 测试点 $9,19,20$ 具有性质 D
特殊性质 A：对于任何 $1 \leq i \leq n,S_i$ 和 $T_i$ 互不相交，即 $S_i \cap T_i=\emptyset$。
特殊性质 B：$n \geq 3$，且对于任侏何 $1 \leq i<n, T_{1} =\{i,i+1\}$，且 $T_{n}=\{n,1\}$。
特殊性质 C：对于任何 $1 \leq i \leq n,|S_i|=1$。
特殊性质 D：对于任何 $1 \leq i \leq n,S_{i}=T_{i}$。
**提示**：本题部分测试点读入规模较大，我们建议你采取效率较高的读入方式。
- 测试点 $1\sim 5$：$T\le 20,n,m\le 10$
- 测试点 $6\sim 11$：$n,m\le 200,\sum n^3,\sum m^3\le 4\cdot 10^7$
- 测试点 $12,13$：$n,m\le 2000,\sum n^2,\sum m^2\le 4\cdot 10^7$
- 测试点 $14\sim 22$：$n,m\le 1.5\cdot 10^5,\sum n,\sum m\le 3\cdot 10^5$
- 测试点 $23\sim 25$：$n,m\le 10^6,\sum n,\sum m\le 1.5\cdot 10^6$
- 测试点 $6,14$ 具有性质 A
- 测试点 $7,15,16$ 具有性质 B
- 测试点 $8,17,18$ 具有性质 C
- 测试点 $9,19,20$ 具有性质 D
特殊性质 A：对于任何 $1 \leq i \leq n,S_i$ 和 $T_i$ 互不相交，即 $S_i \cap T_i=\emptyset$。
特殊性质 B：$n \geq 3$，且对于任侏何 $1 \leq i<n, T_{1} =\{i,i+1\}$，且 $T_{n}=\{n,1\}$。
特殊性质 C：对于任何 $1 \leq i \leq n,|S_i|=1$。
特殊性质 D：对于任何 $1 \leq i \leq n,S_{i}=T_{i}$。
**提示**：本题部分测试点读入规模较大，我们建议你采取效率较高的读入方式。