小A取石子【牛客tracker 每日一题】

小A取石子

时间限制：1秒 空间限制：32M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

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

输入描述：

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

1 ≤ n ≤ 10 5 ; 1 ≤ a i ≤ 10 5 ; 0 ≤ k ≤ 10 5 1≤n≤10^5; 1≤a_i≤10^5; 0≤k≤10^51≤n≤105;1≤ai​≤105;0≤k≤105

输出描述：

一行一个结果表示小A AA是否有必胜策略，如果有则输出Y E S YESYES，否则输出N O NONO。

示例1

输入：

3 2 1 1 1

输出：

YES

示例2

输入：

2 0 5 5

输出：

NO

解题思路

本题基于经典尼姆博弈的核心规则，先手必胜的条件是所有石子堆数量的异或和不为0 00；首先计算所有石子堆的总异或和n u m numnum，若初始n u m ≠ 0 num≠0num=0，小A AA本就有必胜策略，直接标记为可行；随后遍历每一堆石子，若当前堆石子数a [ i ] ≥ k a[i]≥ka[i]≥k，计算将该堆减少k kk个后的新总异或和n u m a [ i ] ( a [ i ] − k ) num^a[i]^(a[i]-k)numa[i](a[i]−k)，只要存在任意一堆修改后异或和不为0 00，说明能通过此次操作获得必胜态，同样标记可行；遍历完成后，若标记为可行则输出Y E S YESYES，否则输出N O NONO。该方法时间复杂度为O ( n ) O(n)O(n)，完美适配n ≤ 10 5 n≤10^5n≤105的规模，依托尼姆博弈定理结合单次修改枚举，精准判断小A AA是否存在必胜策略。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=2e6+10;intmain(){ll n,k,d;cin>>n>>k;ll num=0;boolok=0;vector<ll>a(n+1);vector<ll>pre(n+1,0);for(ll i=1;i<=n;i++){cin>>a[i];num^=a[i];pre[i]=pre[i-1]^a[i];}if(num)ok=1;for(ll i=1;i<=n;i++){if(a[i]>=k){if(num^a[i]^(a[i]-k))ok=1;}}if(ok)cout<<"YES\n";elsecout<<"NO\n";return0;}