企业官网建设流程全解析

排名做网站优化,python做笔记的网站,谷歌aso优化,国外网站设计的网站小A取石子 时间限制#xff1a;1秒 空间限制#xff1a;32M 网页链接 牛客tracker 牛客tracker 每日一题#xff0c;完成每日打卡#xff0c;即可获得牛币。获得相应数量的牛币#xff0c;能在【牛币兑换中心】#xff0c;换取相应奖品#xff01;助力每日有题…小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是否存在必胜策略。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpairll,llpii;constll p1e97;constll N2e610;intmain(){ll n,k,d;cinnk;ll num0;boolok0;vectorlla(n1);vectorllpre(n1,0);for(ll i1;in;i){cina[i];num^a[i];pre[i]pre[i-1]^a[i];}if(num)ok1;for(ll i1;in;i){if(a[i]k){if(num^a[i]^(a[i]-k))ok1;}}if(ok)coutYES\n;elsecoutNO\n;return0;}