1、检查网络是否连接;
原创攵章 5获赞 0访问量 568
给定n堆石子两位玩家轮流操作,每次操作可以从任意一堆石子中拿走任意数量的石子(可以拿完但不能不拿),最后无法进行操作的人视为失败
问如果两人都采用朂优策略,先手是否必胜
第二行包含n个数字,其中第 i 个数字表示第 i 堆石子的数量
如果先手方必胜,则输出“Yes”
1≤每堆石子数≤109
假设n堆石子的石子数量分别为:a1?,a2?,...,an?。
①、若每一堆石子都为0则每一堆石子数量异或值0?0?...?0=0,此时先手必败
②、若a1??a2??...?ai??...?an???=0,设a1??a2??...?ai??...?an?=x.假设x的二进制表示中最高位的1在第k位则a1?到an?中必存在一个数ai?,ai?的第k位是1
那么有ai??x<ai?,现从第i堆石子拿出一些石子使得剩下ai??x个石子。
③、若a1??a2??...?ai??...?an?=0则无论如何都不能保持所有堆的石子数量的异或值为0。
于是,只要先手的情况下各堆石子数量的异或值不为0,我们可以拿一些石子使得异或值为0直到所有石子被拿空。
而轮到对手时始终是异或值为零的情况,对手拿完后均会使得异或值非零。
因此只需判断各堆石子的异或值是否为零即可。
绑定GitHub苐三方账户获取
累计签到获取不积跬步,无以至千里继续坚持!
授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发
在《原力计划【第二季】》打卡挑战活动中,成功参与本活动并发布一篇原创文章的博主即可获得此勋章。
版权声明:本文为博主原创文章遵循
版权协议,转载请附上原文出处链接和本声明
1、检查网络是否连接;
原创攵章 5获赞 0访问量 568