#PQJ1898x9685. QOJ 1898_9685

    ID: 2751 传统题 3000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTS 2025

QOJ 1898_9685

第一试Nim 游戏(nim) IOI2025 中国国家队选拔 Nim 游戏(nim) 【题目描述】 小w 被迫卷入了一场决定一切的Nim 游戏! 有n 堆石子摆在小w 面前,从1 到n 编号,其中编号为i 的石子堆中有ai 个石 子。在Nim 游戏中,小w 和一位绝顶聪明的对手轮流操作,小w 后手。每次操作中, 操作方可以选择一堆石子,将这一堆石子中任意多的石子扔掉,但不能不扔。如果某个 人操作时,所有n 堆石子中都没有石子了,那么他就无法操作,从而失败。 熟练掌握OI 知识的小w 知道Nim 游戏的最优策略,还知道两个玩家都以最优策 略操作时,后手获胜当且仅当所有ai 的按位异或和为0。然而初始局面不一定满足这个 条件,于是小w 决定用些盘外招让所有ai 的异或和为0,然后赢下这盘游戏。为此小 w 准备了很多石子,他可以在游戏开始前在每个石子堆上添加任意多(也可以不添加) 石子。然而小w 不能从石子堆里取走石子,也不能创建新的石子堆。 小w 请你提供添加石子的方案。为了保持隐蔽,小w 希望添加尽可能少的石子,所 以他首先想要知道最少需要添加多少石子。除此之外他还希望准备m 套不同的添加石 子数最少的方案,以备不时之需。我们认为两种方案不同,当且仅当存在某堆石子,在 这两种方案中该堆石子所添加的石子数量不同。如果这样的方案没有m 种,则你需要 全部告诉他;如果这样的方案大于m 种,则你任意给出m 种即可。 【输入格式】 从文件nim.in 中读入数据。 .本.题.有.多.组.测.试.数.据。 输入的第一行包含两个整数c, T,分别表示测试点所属的子任务编号与测试数据组 数。对于样例有c = 0。 接下来依次输入每组测试数据,对于每组测试数据: 第一行包含两个整数n 和m,分别表示石子堆的数量以及小w 需要的方案数量。 第二行包含n 个非负整数a1, a2, · · · , an,描述每堆石子的石子数量。 【输出格式】 输出到文件nim.out 中。 对于每组测试数据: • 输出的第一行包含一个整数k,表示小w 最少需要添加多少石子。 • 输出的第二行包含一个整数m′,表示你提供给小w 的方案数量。如果添加石子 最少的方案数不少于m,你需要保证m′ = m,否则你需要保证m′ 恰好是添加 石子最少的方案数。 • 接下来依次输出m′ 个不同的方案,对于每个方案输出三行,其中: 第4 页 共9 页 第一试Nim 游戏(nim) IOI2025 中国国家队选拔 – 第一行包含一个整数n′,表示该方案中添加了石子的石子堆数量。 – 第二行包含n′ 个整数x1, x2, · · · , xn′,描述该方案中添加了石子的石子堆编 号。你需要保证1 ≤x1 < x2 < · · · < xn′ ≤n。当n′ = 0 时,这一行需要为 空行。 – 第三行包含n′ 个整数w1, w2, · · · , wn′,其中wj(1 ≤j ≤n′) 表示该方案中在 编号为xj 的石子堆中添加的石子数量。你需要保证对于任意的1 ≤j ≤n′, 有wj ≥1 且!n′ j=1 wj = k。当n′ = 0 时,这一行需要为空行。 你需要保证在单个测试点内输出的整数数量不超过107,可以保证总是存在这样的 输出满足题目条件。 【样例1 输入】 0 2 1 3 1 2 4 2 3 3 2 2 4 1 3 5 【样例1 输出】 3 1 1 2 2 3 1 3 4 2 1 5 2 6 1 7 1 8 1 9 2 10 【样例1 解释】 对于第一组数据,小w 共有两种使添加石子总数最小的方案: • 给第1 堆添加2 个石子,给第3 堆石子添加1 个石子。此时三堆石子数分别是 6, 2, 4,此时后手必胜。 • 给第3 堆添加3 个石子。此时三堆石子数分别是4, 2, 6,此时后手必胜。 第5 页 共9 页 第一试Nim 游戏(nim) IOI2025 中国国家队选拔 由于小w 只需要一种方案,输出任意一种方案均可,样例输出为第一种。 对于第二组数据,小w 只有一种使添加石子总数最小的方案: • 给第1 堆添加2 个石子。此时两堆石子的石子分别是3, 3,此时后手必胜。 尽管小w 需要两种方案,但由于总方案只有一种,故输出唯一的一种方案即可。 【样例2】 见选手目录下的nim/nim2.in 与nim/nim2.ans。 【子任务】 设! n 和! m 分别表示单个测试点中所有测试数据的n 和m 的和。对于所有测 试数据,保证 • 1 ≤T ≤2 × 104, • 2 ≤n ≤105,2 ≤! n ≤2 × 105,1 ≤m, ! m ≤2 × 104, • ∀1 ≤i ≤n, 0 ≤ai ≤260 −1, n! • ai ≥1。 i=1 ! n ≤ ! m ≤ 子任务编号 分值 特殊性质 n ≤ m ≤ ai ≤ 230 −1 105 无 1 4 2 24 −1 2 5 25 B 104 210 −1 104 3 6 30 12 A 4 105 2 × 105 5 1 230 −1 B 103 102 102 6 2, 000 16 7 104 104 105 2 × 105 8 无 8 260 −1 2 × 104 2 × 104 9 特殊性质A:对于每一个1 ≤i ≤n,ai 都是2 的非负整数幂次。 特殊性质B:a1 = 0。 【评分方式】 对于每个测试点,如果你在所有测试数据中都正确地输出了小w 需要的最小石子 数量(即输出格式中的k),你将获得该测试点50% 的分数。在此基础上,如果你在所 有测试数据中都按照要求给出了方案,你将获得该测试点100% 的分数。一个子任务的 分数取决于该子任务中所有测试点分数的.最.小.值。 第6 页 共9 页 第一试Nim 游戏(nim) IOI2025 中国国家队选拔 注意,即使你只想回答小w 需要的最小石子数量,也需要在回答的小w 需要的最 小石子数量后按照给定的格式输出方案数量以及.对.应.数.量.的,.正.确.的,.不.重.复.的方案。 简单地输出m′ = 0 即可完成这一点。 第7 页 共9 页