Stone Game II

HDU - 4388

题目大意:

给出n堆物品,每堆物品都有若干件,现在A和B进行游戏,每人每轮操作一次,按照如下规则:

1. 任意选择一个堆,假设该堆有x个物品,从中选择k个,要保证0<k<x且0<(x^k)<k。

2. 再增加一个大小为x^k的堆(也就相当于将一个x个物品的堆变成一个k个物品的堆和一个x^k个物品的堆),另外有一个技能,可以将这个大小为x^k的堆变成(2*k)^x的堆,但是这个技能每个人只有一次机会可以使用。

现在问两人轮流操作,都采取最优策略,最后不能操作的人输,问谁会赢。

/*
先不考虑技能,其实每轮的操作就是将一个大小为x的堆分成大小为k和(x^k)的堆,这里很关键的一点是要能发现分堆之前x中二进制1的个数与分堆之后k与(x^k)的二进制1个数和的奇偶性是相同的。这个结论可以这样想,考虑x的某一位p,分四种情况:
1. 如果x的第p位为1且k的第p位也为1,那么(x^k)的第p位就是0.
2. 如果x的第p位为1且k的第p位也为0,那么(x^k)的第p位就是1.
3. 如果x的第p位为0且k的第p位也为1,那么(x^k)的第p位就是1.
4. 如果x的第p位为0且k的第p位也为0,那么(x^k)的第p位就是0.
可以发现无论哪种情况,奇偶性都不会发生变化,这是本题的关键。
另外考虑游戏怎么终止,很显然当一个堆x的二进制1的个数只有1个的时候,就不能再分了,那么如果所有的堆都这样,游戏就终止了,关键看从开始到终止需要奇数步还是偶数步就能判断输赢。
假设这些堆最后会分成y个堆,那么一共就分了y-n次,每个堆大小的二进制1个数都是1,这样二进制1的总是就是y,而y和x二进制1的个数z已经证明奇偶性相同,所以y-n和z-n奇偶性就是相同的,所以我们只需要判断z-n的奇偶性,这题就解决了,非常巧妙。
*/
#include<iostream>
#include<cstdio>
using namespace std;
int n,T;
int count(int x){
int res=;
while(x){
res+=x&;
x>>=;
}
return res;
}
int main(){
freopen("Cola.txt","r",stdin);
scanf("%d",&T);
for(int c=;c<=T;c++){
printf("Case %d: ",c);
scanf("%d",&n);
int cnt=,x;
for(int i=;i<=n;i++){
scanf("%d",&x);
cnt+=count(x);
}
cnt-=n;
if(cnt&)puts("Yes");
else puts("No");
}
return ;
}

最新文章

  1. AngularJS------认识AngularJS
  2. 细节小bug
  3. 【转载】HTTP 错误 500.19 - Internal Server Error
  4. codeforces gym 100286 H - Hell on the Markets (贪心算法)
  5. windows和linux共享文件
  6. hdu 3401 单调队列优化动态规划
  7. 我对Backbone中url属性的理解
  8. uva 10014 Simple calculations
  9. java中setDate(Date date)方法和String与Date之间的转换
  10. C++ 中捕获整数除零错误
  11. tostring的用法
  12. HBase文件格式演变之路
  13. ASCII码对应表chr(9)、chr(10)、chr(13)、chr(32)、chr(34)、chr(39)
  14. 【Shell】使用Shell脚本发布项目
  15. python函数前篇
  16. Jupyter Notebook中的快捷键
  17. 记录几个爬取动态网页时的问题(下拉框,旧的元素无法获取,获取的源代码和f12看到的不一致,爬取延迟)
  18. Windowns Server 2016 + Nginx 1.10.2 + PHP 7.1.0 + Laravel 5.3 + Mariadb 10.1.19 开发环境设置
  19. ionic2 调用 cordova非本地化native 插件方法
  20. &lt;1&gt;Python生成高质量Html文件:Pyh模块+Bootstrap框架

热门文章

  1. node.js redis对事务的控制
  2. 使用命令行生成 APNG 图片
  3. 关于COM组件调用
  4. VC++6.0编译环境介绍
  5. 2017-2018-1 20179203《Linux内核原理与分析》第二周作业
  6. bzoj 1069: [SCOI2007]最大土地面积 凸包+旋转卡壳
  7. Linux编程之错误代码
  8. 深入理解javascript中的立即执行函数
  9. OpenStack安装后检查流程总结
  10. TS学习之基础类型