#2261. 填数游戏

    ID: 2261 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>PROV赛事:contest1199来源:qoj.ac数据:公开样例贪心枚举

填数游戏

填数游戏

题目描述

NOI2023 省选 DAY2 填数游戏(game) 填数游戏(game) 【题目描述】 众所周知,Alice 和Bob 是一对好朋友。今天,他们约好一起玩游戏。 一开始,他们各自有一张空白的纸条。接下来,他们会在纸条上依次写n 个[1, m] 范围内的正整数。等Alice 写完,Bob .在.看.到Alice .写.的.纸.条.之.后.开.始.写.他.的.纸.条。 Alice 需要保证她写下的第i 个数在集合Si 中,Bob 需要保证他写下的第i 个数在 集合Ti 中。.题.目.保.证1 ≤|Si|, |Ti| ≤2。 Alice 喜欢相同,因此,她希望她写下的数与Bob 写下的数对应位置相同的个数尽 量多。Bob 喜欢不同,因此,他希望他写下的n 个数b1, · · · , bn 互不相同。在此基础上, Bob 希望他写下的数与Alice 写下的数对应位置相同的个数尽量少。 即设Alice 写下的数为a1, · · · , an,Bob 写下的数为b1, · · · , bn,记X 为满足1 ≤ i ≤n, ai = bi 的下标i 的个数,则 • Alice 希望最大化X, • Bob 在.保.证b1, · · · , bn .互.不.相.同.的.前.提希望最小化X。 你首先想知道Bob 能否保证他写下的n 个数互不相同。如果Bob 能够做到,你想 知道.在.双.方.均.采.取.最.优.策.略.的.前.提.下X 的值会是多少。 【输入格式】 从文件game.in 中读入数据。 .本.题.有.多.组.测.试.数.据。 输入的第一行包含一个正整数T,表示测试数据组数。 接下来包含T 组数据,每组数据的格式如下: 第一行包含两个正整数n, m,表示纸条上需要写的数的个数和数的值域。 接下来n 行,每行输入的第一个整数为|Si| 表示集合Si 的元素个数,接下来输入 |Si| 个正整数描述Si 中的元素。 接下来n 行,每行输入的第一个整数为|Ti| 表示集合Ti 的元素个数,接下来输入 |Ti| 个正整数描述Ti 中的元素。 【输出格式】 输出到文件game.out 中。 对于每组测试数据输出一行:若Bob 无法做到他写下的n 个数互不相同,输出−1; 否则输出在双方均采取最优策略的前提下X 的值。 【样例1 输入】 第6 页 共12 页

NOI2023 省选 DAY2 填数游戏(game) 1 1 2 3 4 3 1 3 4 2 1 2 5 2 3 4 6 2 1 2 7 2 2 3 8 2 3 4 【样例1 输出】 1 1 【样例1 解释】 在这组样例中,S1 = {3}, S2 = T1 = {1, 2}, S3 = T3 = {3, 4}, T2 = {2, 3}。 Alice 的填法有4 种,列举如下: 第一种:a1 = 3, a2 = 1, a3 = 3。 第二种:a1 = 3, a2 = 1, a3 = 4。 第三种:a1 = 3, a2 = 2, a3 = 3。 第四种:a1 = 3, a2 = 2, a3 = 4。 由于Bob 必须保证他所填的数互不相同,所以他有以下填法: 第一种:b1 = 1, b2 = 2, b3 = 3。 第二种:b1 = 2, b3 = 3, b3 = 4。 第三种:b1 = 1, b2 = 2, b3 = 4。 第四种:b1 = 1, b2 = 3, b3 = 4。 若Alice 选择第一种填法,则Bob 为最小化X,选择第二种填法,得到X = 0。 若Alice 选择第二种填法,则Bob 为最小化X,选择第一种填法,得到X = 0。 若Alice 选择第三种填法,则Bob 为最小化X,选择第二种填法,得到X = 0。 若Alice 选择第四种填法,则Bob 无论选择哪种填法,X 均不小于1。 因此,Alice 为最大化X 的值,她会选择第四种填法。 【样例2】 见选手目录下的game/game2.in 与game/game2.ans。 第7 页 共12 页

NOI2023 省选 DAY2 填数游戏(game) 这个样例满足测试点1 ∼5 的条件。 【样例3】 见选手目录下的game/game3.in 与game/game3.ans。 这个样例满足测试点6 的条件。 【样例4】 见选手目录下的game/game4.in 与game/game4.ans。 这个样例满足测试点7 的条件。 【样例5】 见选手目录下的game/game5.in 与game/game5.ans。 这个样例满足测试点8 的条件。 【样例6】 见选手目录下的game/game6.in 与game/game6.ans。 这个样例满足测试点9 的条件。 【样例7】 见选手目录下的game/game7.in 与game/game7.ans。 这个样例满足测试点10 ∼11 的条件。 【样例8】 见选手目录下的game/game8.in 与game/game8.ans。 这个样例满足测试点12 ∼13 的条件。 【样例9】 见选手目录下的game/game9.in 与game/game9.ans。 这个样例满足测试点23 ∼25 的条件。 【子任务】 对于所有的数据,保证:1 ≤T ≤1000;1 ≤n, m ≤106;1 ≤|Si|, |Ti| ≤2; 集合Si, Ti 都是{1, 2, · · · , m} 的子集且集合内元素两两不同。 第8 页 共12 页

NOI2023 省选 DAY2 填数游戏(game) 表格中∑n, ∑m 分别表示同个测试点内所有测试数据的n 总和和m 总和。 ∑n2, ∑m2, ∑n3, ∑m3 的含义类似。 测试点编号 数据范围 特殊性质 1 T ≤20, n, m ≤10 2 3 4 5 6 n, m ≤200, ∑n3, ∑m3 ≤4 · 107 A 7 B 8 C 9 D 10 11 12 n, m ≤2000, ∑n2, ∑m2 ≤4 · 107 13 14 n, m ≤1.5 · 105, ∑n, ∑m ≤3 · 105 A 15 B 16 17 C 18 19 D 20 21 22 23 n, m ≤106, ∑n, ∑m ≤1.5 · 106 24 25 特殊性质A:对于任何1 ≤i ≤n,Si 和Ti 互不相交,即Si ∩Ti = ∅。 特殊性质B:n ≥3,且对于任何1 ≤i < n,Ti = {i, i + 1},且Tn = {n, 1}。 特殊性质C:对于任何1 ≤i ≤n,|Si| = 1。 特殊性质D:对于任何1 ≤i ≤n,Si = Ti。 【提示】 本题部分测试点读入规模较大,我们建议你采取效率较高的读入方式。 第9 页 共12 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

1
3 4
1 3
2 1 2
2 3 4
2 1 2
2 2 3
2 3 4
1

样例 2

20
9 10
2 8 4
2 3 6
2 5 3
2 6 7
2 7 3
2 2 8
2 9 2
2 5 6
2 6 2
2 5 4
2 3 2
2 4 3
2 7 6
2 7 8
2 9 8
2 2 1
2 5 6
2 4 10
9 10
2 8 2
1 2
2 6 7
2 6 5
1 3
2 6 3
1 4
2 8 7
1 2
2 8 9
2 2 1
2 7 6
2 5 6
2 4 3
2 2 3
2 5 4
2 8 7
2 10 8
9 10
1 4
1 5
2 8 6
2 4 3
1 6
1 9
2 4 7
2 3 1
1 2
2 4 3
2 5 4
2 7 8
2 10 6
2 5 6
2 8 9
2 7 6
2 2 3
2 1 2
9 10
2 6 7
2 1 10
2 9 2
2 9 5
2 10 5
1 3
2 2 10
1 1
2 5 8
2 5 1
2 2 1
2 2 7
2 8 1
2 1 6
2 3 1
2 2 9
2 4 2
2 8 10
10 10
1 5
1 7
2 5 2
2 1 5
2 7 4
2 8 3
1 3
2 10 6
2 5 2
2 2 1
2 5 6
2 8 7
2 3 2
2 6 1
2 4 5
2 4 3
2 3 7
2 10 6
2 5 9
2 2 1
9 10
2 6 7
2 10 5
2 2 7
2 1 4
1 9
1 8
2 6 3
1 7
2 3 2
2 7 6
2 10 8
2 1 2
2 5 4
2 6 5
2 9 8
2 3 4
2 8 7
2 3 2
9 8
1 6
1 2
2 3 4
2 4 2
2 2 4
2 3 4
2 8 5
1 2
2 4 1
2 2 5
2 1 2
2 6 3
2 3 2
2 4 5
2 4 3
2 5 8
1 7
2 7 4
10 10
2 2 3
1 2
2 5 6
2 8 3
2 9 2
2 10 2
2 5 4
2 8 4
1 8
2 2 5
2 7 3
2 2 1
2 5 6
2 7 3
2 3 2
2 10 2
2 4 5
2 4 3
2 2 8
2 9 2
10 10
2 1 7
2 2 3
2 1 2
2 5 6
2 1 3
2 10 1
2 9 6
2 7 8
2 8 9
2 4 5
2 1 7
2 3 2
2 2 1
2 5 6
2 4 3
2 1 10
1 6
2 7 8
2 8 9
2 4 5
9 10
1 8
2 3 1
2 10 2
2 4 5
1 2
2 10 7
2 6 5
1 3
2 7 6
2 9 8
2 3 2
2 2 10
2 4 5
2 1 2
2 8 7
2 5 6
2 4 3
2 7 6
9 10
2 4 3
2 2 6
1 7
2 8 4
1 5
2 10 1
2 9 10
2 3 6
2 3 10
2 3 6
2 5 3
2 7 4
2 1 2
2 5 9
2 4 1
2 6 10
2 8 2
2 2 3
9 10
2 6 7
2 5 10
2 7 8
2 4 3
2 4 3
2 5 4
2 7 2
2 4 5
2 7 8
2 6 7
2 10 5
2 7 8
2 3 4
2 3 2
2 4 5
2 1 2
2 6 5
2 9 8
9 10
2 4 8
2 4 3
2 2 8
2 7 4
2 6 5
2 8 3
2 3 7
2 6 2
2 10 3
2 5 4
2 6 7
2 9 8
2 8 7
2 5 6
2 3 2
2 3 10
2 2 1
2 3 4
10 10
2 9 1
2 4 3
2 4 8
2 10 7
1 3
2 4 5
1 2
2 5 4
2 10 2
1 3
2 9 2
2 4 3
2 4 8
2 7 3
2 3 2
2 6 5
2 2 1
2 5 4
2 1 2
2 10 3
10 10
1 7
1 6
2 4 3
1 7
2 6 9
1 1
2 9 10
2 2 1
1 9
2 4 5
2 8 7
2 2 6
2 3 4
2 7 5
2 6 5
2 1 2
2 10 9
2 3 2
2 9 1
2 5 4
9 10
1 10
2 3 2
2 9 7
2 4 6
2 7 1
2 6 1
1 4
2 1 2
2 10 3
2 10 9
2 2 3
2 9 4
2 4 8
2 7 1
2 1 6
2 4 5
2 1 2
2 4 3
9 10
1 3
2 8 1
2 2 3
1 6
2 9 5
1 5
2 10 2
1 7
2 4 5
2 2 3
2 8 7
2 1 2
2 6 5
2 9 8
2 4 5
2 2 10
2 6 7
2 3 4
9 10
1 2
1 3
2 10 9
2 3 8
2 5 6
1 3
2 6 7
2 4 7
1 4
2 2 1
2 4 3
2 5 10
2 9 8
2 5 6
2 2 3
2 6 7
2 8 7
2 4 5
9 10
2 8 2
2 6 7
2 3 9
2 1 4
2 6 3
2 8 7
2 3 8
2 4 10
2 6 5
2 2 1
2 6 7
2 2 3
2 4 5
2 3 4
2 7 8
2 8 9
2 1 10
2 6 5
9 10
2 8 6
2 2 10
1 3
2 8 4
2 4 3
1 10
2 7 4
2 5 6
2 7 6
2 8 9
2 1 2
2 3 2
2 4 5
2 4 3
2 9 10
2 8 7
2 5 6
2 6 7
2
2
0
0
3
2
-1
7
10
3
2
3
1
7
6
4
1
3
3
3