## （一）巴什博奕（Bash Game）：
~~~
问题描述：有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m 个。最后取光者得胜。
显然，如果n=m+1，那么由于一次最多只能取m 个，所以，无论先取者拿走多少个,
后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果n=（m+1）r+s，（r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走k（≤m)个，那么先取者再拿走m+1-k个，结果剩下(m+1)(r-1)个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。
这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十个，谁能报到100 者胜。
必胜局面：n%(m+1)!=0
必败局面：n%(m+1)=0
例题：
取棋子游戏(I)分数: 16
时间限制：1 秒
内存限制：128 兆
特殊判题： 否
提交：26
解决： 20
题目描述
有N个棋子, 两个人轮流从这堆物品中取, 规定每次至少取1个, 最多取3个. 最后取光者得胜. 要求找出先行者是否有必胜策略，第一步应该取多上个棋子。
输入格式
有多行数据，每行数据是一个正数N<10^7；
输出
如果该行数据具有先行者必胜策略，则输出第一步应取的棋子。若没有必胜策略，输出loss
样例输入
1
1000
样例输出
1
loss
~~~
#### 源码
~~~
#include<iostream>
using namespace std;
/**
若n%4==0，先行者必败
否则先行者必赢n%4
*/
int main(){
int n;
while(cin>>n){
if(n%4==0){
cout<<"loss"<<endl;
}else{
cout<<n%4<<endl;
}
}
return 0;
}
~~~
## （二）威佐夫博奕（Wythoff Game）
~~~
问题描述：有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
这种情况下是颇为复杂的。我们用（ak，bk）（ak ≤ bk ,k=0，1，2，...,n)表示两堆物品的数量并称其为局势，如果甲面对(0,0)，那么甲已经输了，这种局势我们称为奇异局势。
前几个奇异局势是：
（0，0）
（1，2）
（3，5）
（4，7）
（6，10）
（8，13）
（9，15）
（11，18）
（12，20）
可以看出,a0=b0=0,ak 是未在前面出现过的最小自然数,而bk= ak+k，奇异局势有如下三条性质：
1、任何自然数都包含在一个且仅有一个奇异局势中。
由于ak是未在前面出现过的最小自然数，所以有ak>ak-1，而bk= ak+k> ak-1+(k-1)=bk-1>ak-1。所以性质1成立。
2、任意操作都可将奇异局势变为非奇异局势。
事实上，若只改变奇异局势（ak，bk）的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。如果使（ak，bk）的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。
3、采用适当的方法，可以将非奇异局势变为奇异局势。
假设面对的局势是(a,b)，分以下几种情况讨论：
1) 若b=a，则同时从两堆中取走a 个物体，就变为了奇异局势（0，0）；
2) 若a=ak ，b >bk，那么，从第二堆中取走b- bk个物体，即变为奇异局势(ak,bk)；
3) 若a=ak ，b < bk,则同时从两堆中拿走a-a(b-a)个物体,变为奇异局势(a(b- a) , b(b -a))；
4) 若a>ak ，b = ak + k,则从第一堆中拿走多余的数量a -ak即可；
5) 若a<ak ，b = ak + k,分两种情况：
(1) a=aj （j < k）时，从第二堆里面拿走b-bj即可，变为(aj , bj)；
(2) a=bj （j < k）时，从第二堆里面拿走b-aj即可，变为(bj , aj)。
注意：a!=ak且b!=bk 的情况不存在，因为由a或b的值肯定能确定一种奇异局势，即要么a=ak,要么b=bk。
从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。
那么任给一个局势(a，b）(a<b)，怎样判断它是不是奇异局势呢？我们有如下公式：
ak =[k(1+√5)/2]，bk= ak + k （k=0，1，2，...,n 方括号表示取整函数）
奇妙的是其中出现了黄金分割数（1+√5）/2 = 1.618...,因此,由ak，bk 组成的矩形近似为黄金矩形，由于2/(1+√5)=(√5-1)/2，
可以先确定这是第几个局势。设该局势是第j个局势，那么j=[a(√5-1)/2]，此时这个奇异局势有2种可能：
1)若a=[j(1+√5)/2]，那么a = aj，若同时有b= aj + j，则奇异局势为(aj,bj)；
2)若a!=[j(1+√5)/2]，那么有可能是a = aj+1，此时如果又有b = aj+1+(j + 1)，则奇异局势为(aj+1,bj+1)。
若以上两种情况都不是，那么就不是奇异局势。然后再按照上述法则进行，一定会遇到奇异局势。
例题：
取石子游戏
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 36229 Accepted: 12266
Description
有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。
Input
输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。
Output
输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。
Sample Input
2 1
8 4
4 7
Sample Output
0
1
0
~~~
#### 源码：
~~~
取石子游戏
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 36229 Accepted: 12266
Description
有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。
Input
输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。
Output
输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。
Sample Input
2 1
8 4
4 7
Sample Output
0
1
0
~~~
## （三）尼姆博奕（Nimm Game）
#### 问题描述：
有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
这种情况最有意思，它与二进制有密切关系，我们用（a，b，c）表示某种局势，首先（0，0，0）显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是（0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0）。仔细分析一下，（1，2，3）也是奇异局势，无论对手如何拿，接下来都可以变为（0，n，n）的情形。
计算机算法里面有一种叫做按位模2 加，也叫做异或的运算，我们用符号（+）表示这
种运算。这种运算和一般加法不同的一点是1+1=0。先看（1，2，3）的按位模2 加的结果：
1 =二进制01
2 =二进制10
3 =二进制11 （+）
———————
0 =二进制00 （注意不进位）
对于奇异局势（0，n，n）也一样，结果也是0。
任何奇异局势（a，b，c）都有a（+）b（+）c =0。
如果我们面对的是一个非奇异局势（a，b，c），要如何变为奇异局势呢？假设a < b< c,我们只要将c变为a（+）b,即可,因为有如下的运算结果: a（+）b（+）(a（+）b)=(a（+）a)（+）(b（+）b)=0（+）0=0。要将c变为a（+）b，只要从c 中减去c（
a（+）b）即可。
例1：（14，21，39），14（+）21=27，3927=12，所以从39 中拿走12 个物体即可达到奇异局势（14，21，27）。
例2：（55，81，121），55（+）81=102，121102=19，所以从121 中拿走19 个物品就形成了奇异局势（55，81，102）。
例3：（29，45，58），29（+）45=48，5848=10，从58 中拿走10 个，变（29，45，48）。
例4：我们来实际进行一盘比赛看看：
甲:(7,8,9)>(1,8,9)奇异局势
乙:(1,8,9)>(1,8,4)
甲:(1,8,4)>(1,5,4)奇异局势
乙:(1,5,4)>(1,4,4)
甲:(1,4,4)>(0,4,4)奇异局势
乙:(0,4,4)>(0,4,2)
甲:(0.4,2)>(0,2,2)奇异局势
乙:(0,2,2)>(0,2,1)
甲:(0,2,1)>(0,1,1)奇异局势
乙:(0,1,1)>(0,1,0)
甲:(0,1,0)>(0,0,0)奇异局势
甲胜。
对于本次普及组“取石子游戏”来说，
19 010011
7 000111
5 000101
3 000011
010010 (18)10
50－18＝32
所以第1 次只能在第5 堆石子中取32 粒，使得取出32 粒后为奇异局势，即异或运算结果为0。
#### 例题：
~~~
Georgia and Bob
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 8134 Accepted: 2527
Description
Georgia and Bob decide to play a self-invented game. They draw a row of grids on paper, number the grids from left to right by 1, 2, 3, ..., and place N chessmen on different grids, as shown in the following figure for example:
Georgia and Bob move the chessmen in turn. Every time a player will choose a chessman, and move it to the left without going over any other chessmen or across the left edge. The player can freely choose number of steps the chessman moves, with the constraint that the chessman must be moved at least ONE step and one grid can at most contains ONE single chessman. The player who cannot make a move loses the game.
Georgia always plays first since "Lady first". Suppose that Georgia and Bob both do their best in the game, i.e., if one of them knows a way to win the game, he or she will be able to carry it out.
Given the initial positions of the n chessmen, can you predict who will finally win the game?
Input
The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then T cases follow. Each test case contains two lines. The first line consists of one integer N (1 <= N <= 1000), indicating the number of chessmen. The second line contains N different integers P1, P2 ... Pn (1 <= Pi <= 10000), which are the initial positions of the n chessmen.
Output
For each test case, prints a single line, "Georgia will win", if Georgia will win the game; "Bob will win", if Bob will win the game; otherwise 'Not sure'.
Sample Input
2
3
1 2 3
8
1 5 6 7 9 12 14 17
Sample Output
Bob will win
Georgia will win
~~~
#### 源码：
~~~
#include<iostream>
#include<algorithm>
using namespace std;
/**
当有两颗棋子紧贴在一起时，先行者只能移动前一颗，后行者为了获胜必然移动后一颗至紧贴前一颗，
这样先行者永远处于劣势，于是我们可以把棋盘上的棋子看成一对一对组合，当每一对棋子都紧贴时，
先行者必败。于是可以把每一对棋子中空格视为一堆石子，接下来就是取石子游戏问题了。接下来就是
判断当前局势是否处于奇异局势，若处于奇异局势则先行者敗，后行者敗.
若棋子数量为偶数，刚好可以把棋子分对
否则把最左端视为一颗棋子
注意：棋子的顺序不一定有序，所以要先进行排序
*/
int n,num[1000],i,sum,t;
int main(){
cin>>t;
while(t>0){
t--;
cin>>n;
//棋子不一定有序
for(i=0;i<n;i++){
cin>>num[i];
}
sort(num,num+n);
sum=0;
if(n%2==0){
for(i=0;i<n;i=i+2){
sum=sum^(num[i+1]-num[i]-1);
}
}else{
sum=sum^(num[0]-1);
for(i=1;i<n;i=i+2){
sum=sum^(num[i+1]-num[i]-1);
}
}
if(sum==0){
cout<<"Bob will win"<<endl;
}else{
cout<<"Georgia will win"<<endl;
}
}
return 0;
}
~~~
- 我的笔记
- 服务器
- ubuntu svn 环境的搭建
- ubuntu Memcache 的配置
- ubuntu 密钥登录服务器
- centos 搭建服务器环境
- nginx+tomcat 集群搭建
- 餐厅运营来看如何构建高性能服务器
- VMware-Centos-网络配置
- Ubuntu-PHP-Apache-Mysql-PhpMyadmin的搭建
- UbuntuApache配置日志
- linux获取当前执行脚本的目录
- Ubuntu svn的快速配置（原创）
- Https配置
- Mysql 不支持远程连接解决方案
- ubuntu+apache+rewrite
- php Mcrypt 扩展
- 重启Apache出现警告信息Could not reliably determine the server's fully qualified domain name,
- Mysql无法远程连接
- 定时任务设置
- Linux中Cache内存占用过高解决办法
- Ubuntu14-04安装redis和php5-redis扩展
- php
- thinkphp3.2 一站多城市配置
- PHP 安全编程建议(转)
- phpexcel导入时间处理
- Mysql按时，天，月，年统计数据
- PHP-支付宝-APP支付
- 百度爬虫-获取全国数据
- PHPEXCEL导入导出excel文件
- php-微信app支付后端设计
- Phpqrcode生成二维码
- 图片+文字水印
- 数据库优化
- java
- Mybatis 二级缓存
- 微信
- 微信公众号多域名授权
- 微信扫码支付
- web
- 网站性能优化方案实施
- ionic环境搭建
- 登录设计方案
- 设置dev元素的宽高比例
- 设计模式
- app
- 版本更新
- 微擎数据库操作扩展
- select
- find
- delete
- update
- insert
- where
- order
- page
- group
- having
- limit
- fields
- debug
- bind
- join
- alias
- query
- 聚合函数
- count
- sum
- max
- min
- avg
- 事务管理
- 自增自减
- 算法设计
- ACM:入口的选择------深度优先搜索
- java:N的N次方
- 最少拦截系统:贪心思想
- ACM:蚕宝宝：搜索
- ACM:n!的位数 :斯特林公式
- 神奇的异或
- 中国剩余定理
- 矩阵翻硬币
- 回溯法
- ACM程序设计网站集锦
- 博弈论
- 多维空间上的搜索算法
- 算法学习笔记之一（排序）
- 算法学习笔记之二（堆排序）
- 算法学习笔记之三（快速排序）
- ACM俱乐部密码
- 原创开源
- 个人感悟