小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;}