首页 > 试题广场 >

小A取石子

[编程题]小A取石子

热度指数：1537 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小A也听说了取石子这个游戏，也决定和小B一起来玩这个游戏。总共有n堆石子，双方轮流取石子，每次都可以从任意一堆中取走任意数量的石子，但是不可以不取。规定谁先取完所有的石子就获胜。但是小A实在是太想赢了，所以在游戏开始之前，小A有一次机会，可以趁小B不注意的时候选择其中一堆石子拿走其中的k个，当然小A也可以选择不拿石子。小A先手。双方都会选择最优的策略，请问在这样的情况下小A有没有必胜的策略，如果有输出YES，否则就输出NO。

输入描述:

一行两个整数N,K，表示分别有N堆石子以及小A可以拿走的石子个数k。
接下来N个整数表示每一堆的石子个数

输出描述:

一行一个结果表示小A是否有必胜策略，如果有则输出YES，否则输出NO。

示例1

输入

3 2
1 1 1

输出

YES

示例2

输入

2 0
5 5

输出

NO

备注:

本题已于下方时间节点更新，请注意题解时效性：
1. 2026-01-15 加强数据。

算法知识视频讲解

BeauWill

发表于 2026-01-15 02:15:55

直接给结论，不考虑作弊的情况下，所有石子数的异或和不为0则先手胜利，否则后手胜利。此结论的推导和证明请自行搜索了解。若不作弊且先手的小A胜利即此时异或和xorSum不为0，则直接输出"YES"，否则考虑小A能否作弊（因为不作弊肯定输，所以看作弊能否改变输的局面）。对于这些堆石子，展开全文

风潇潇飒飒366

发表于 2026-01-16 12:30:22

一个Nim的游戏变种题Nim游戏的一个种类是：有n堆石子，每个人可以拿其中一堆石子的任意数量，不能不拿，而且每一步都是最优考虑，则有一下结论；如果所有石子的异或和为0，则后手必赢如果所有石子的异或和不为0，则先手必赢那么知道这这个结论之后，本题就是多加了一步（小A可以先拿k个//注意，是必须拿k个或展开全文

Minazuki_Hotaru

发表于 2026-01-15 02:26:16

先介绍一下Nim博弈如果这堆石头数量异或和为0，先手必败，否则先手必胜这边给出证明：一个人最终会输，也就是说他需要面对没有石头的那种情况，这边给两个概念：一个人面对石头数量异或和为0的时候，这个人处于必败态一个人面对石头数量异或和不为0的时候，这个人处于必胜态这个人处于必败态的时候，下一步无论取走多展开全文

BaiJay

发表于 2026-01-15 09:34:33

很明显这是Nim游戏的博弈规则，加上了一点小技巧。回忆博弈论，当所有数异或不为0的时候，先手必胜。而如果异或为0，如果k不为0，即我们可以进行操作，那么我们只要有一个数能让我们拿走k个，就能使得异或不为0。 #include <bits/stdc++.h&g 展开全文

牛客511341922号

发表于 2026-01-15 09:40:12

Step 1: 回顾 Nim 游戏结论。 Nim 游戏的必胜条件完全取决于所有堆石子数量的异或和。设。若，先手必胜。若，先手必败。 Step 2: 分析小A的处境。小A 局面的异或和。他有两种选择：不作弊：此时。作弊：选择第堆（要求），将其变为。此时展开全文

软件25_4刘卓生

发表于 2026-01-15 12:54:38

本题是经典 Nim 游戏的变种。核心思路核心观察本题基于经典 Nim 游戏，其胜负由所有石子堆数量的异或和（XOR sum）决定：若异或和，先手必胜；若异或和，先手必败。小A在游戏开始前可执行一次特殊操作：从某一堆中恰好拿走个石子注意不是（需满足该堆），之后正常开始展开全文

牛批宏宏

发表于 2026-01-15 13:13:32

n, k = map(int, input().split()) arr = list(map(int, input().split())) xor_sum = 0 for x in arr: xor_sum ^= x if xor_sum != 0: print("Y 展开全文

此在Dasein

发表于 2026-01-15 06:33:39

该问题属于经典的组合博弈论（Combinatorial Game Theory）范畴，具体为Nim游戏的一个变种。理论核心：Sprague-Grundy定理与Nim和在标准的Nim游戏中，每一个堆的石子数量对应一个Grundy值（即及其石子数本身）。游戏局面的胜负性由所有堆石子数量的异或和（XO 展开全文