LightOJ-1253-Misere Nim-nim博弈
Alice and Bob are playing game of Misère Nim. Misère Nim is a game playing on k piles of stones, each pile containing one or more stones. The players alternate turns and in each turn a player can select one of the piles and can remove as many stones from that pile unless the pile is empty. In each turn a player must remove at least one stone from any pile. Alice starts first. The player who removes the last stone loses the game.
Input
Input starts with an integer T (≤ 200), denoting the number of test cases.
Each case starts with a line containing an integer k (1 ≤ k ≤ 100). The next line contains k space separated integers denoting the number of stones in each pile. The number of stones in a pile lies in the range [1, 109].
Output
For each case, print the case number and 'Alice' if Alice wins otherwise print 'Bob'.
Sample Input
3
4
2 3 4 5
5
1 1 2 4 10
1
1
Sample Output
Case 1: Bob
Case 2: Alice
Case 3: Bob
题意:
有n堆石子,每堆石子里面至少有一个石子,有A、B两人。A先取,取完所有石子的一方获胜,问当双方都采取最优策略时,谁能获胜。
思路:
nim博弈模板,谁面临平衡态势谁就会输。
特判一种情况:当每一堆石子的个数全部都为1的时候,这个时候只能每次拿一个,根据1的奇偶性进行判断。
#include<stdio.h> int main()
{
int t,tt=;
scanf("%d",&t);
while(t--)
{
int n,xx;
scanf("%d",&n);
int x=,flag=;
for(int i=; i<n; i++)
{
scanf("%d",&xx);
if(xx!=)
{
flag=;
}
x^=xx;
}
if(flag==)
{
if(n%==)
printf("Case %d: Alice\n",tt++);
else
printf("Case %d: Bob\n",tt++);
}
else
{
if(x!=)
printf("Case %d: Alice\n",tt++);
else
printf("Case %d: Bob\n",tt++);
}
}
return ;
}
最新文章
- 由java的八个基本数据类型说开去
- java的三大框架(三)---Hibernate
- 利用百度云免费备份SQL数据库
- Heka 的编译 和 Heka 插件的编译
- JS仿Android Toast提示效果
- hdu1798(几何面积计算)
- 获取当前 Python 版本
- django访问静态文件
- java中IO流的操作
- mongodb 简单部署方案及实例
- html图片滚动效果
- 如何处理 Windows Phone 8 动态砖变成黑白砖
- 543. Diameter of Binary Tree
- Spring HandlerInterceptor
- python科学计算_numpy_广播与下标
- thinphp 整合ueditor
- ShellExecuteEX打开iqy文件导致excel hang的原因分析
- 将一台电脑上的虚拟机上的系统复制到另一台电脑的虚拟机上!!!and想询问大神们问题的解决办法??
- f5电源模块损坏
- mysql使用存储过程,自动生成新的表单
热门文章
- python的代码块缓存机制,小数据池机制。
- BZOJ 4698: Sdoi2008 Sandy的卡片(后缀数组+差分+二分答案)
- LInux文件基础知识和文件目录操作(二)文件I/O操作
- plsql初次连接oracle报错解决方案
- python 读取设备的另一个方法
- IDM自定义报错页面
- std::locale与boost::locale的学习
- java.util.Arrays,java.lang.Math,java.lang.System 类的常用方法汇总
- Rollei SL66 使用说明
- mysql shell脚本