#PQJ1199x6315. QOJ 1199_6315

    ID: 2570 传统题 3000ms 1024MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:NOI 2023 统一省选枚举贪心

QOJ 1199_6315

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 页