http://acm.hdu.edu.cn/showproblem.php?pid=1525

題意：給你兩個數(shù)，每次都是大數(shù)減去小數(shù)的整數(shù)倍获洲，Stan先開始磨取，然后是Ollie，如果誰先出現(xiàn) 0,b 這種情況誰就獲勝了畔乙。

分析：1.當a=b時君仆，這時候先手必勝。
2.當a>b時牲距，這時候有兩種情況
①a%b=0返咱，此時a為b的倍數(shù)，先手必勝牍鞠。
②a>=2b咖摹，此時先手可以進行選擇，進行什么選擇呢皮服？每個人都想獲勝楞艾，所以他們采取的都是最利于自己的行動参咙，Stan或者Ollie肯定知道 a%b,b 是必勝態(tài)還是必敗態(tài)。如果是必敗態(tài)裹纳，先手將a,b變成a%b,b，使對手面臨必敗態(tài)，先手贏。如果是必勝態(tài)，先手將a,b變成 a%b+b,b 诸尽，破壞掉必勝態(tài)膀哲，那么對手只有將這兩個數(shù)變成 a%b,b ,先手獲勝兴喂。（ 25云矫，7 這個例子就能說明②這種情況 ）

綜上 關(guān)鍵是找到必勝態(tài)
a>b 與 b>a 情況一致
即a==b||a%b==0||a>=2*b時先手勝
否則就一步一步走巡揍，看到最后誰勝利痛阻。（ 15，24這個例子能說明這種情況）

#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
    long long a,b;
    while(scanf("%lld%lld",&a,&b)!=EOF,a+b)
    {
        if(a<b) swap(a,b);
        bool flag=true;
        while(1)
        {
            if(a%b==0||a>=2*b)break;
            a=a-b;
            if(a<b) swap(a,b);
            flag=!flag;
        }
        if(flag) printf("Stan wins\n");
        else printf("Ollie wins\n");
    }

    return 0;
}

http://acm.hdu.edu.cn/showproblem.php?pid=1564
題意：一個nn的棋盤腮敌，一開始的時候棋子在一個角落的格子里阱当，每次可以移動棋子到上下左右的相鄰格子中（不能超過邊界，而且不能走走過的格子）缀皱；當不能走時斗这，敗。現(xiàn)在8600先走啤斗，問最后誰贏表箭。
題解：這道題贏家的關(guān)鍵就是最先搶奪過程中剩余可以走的個數(shù)為奇數(shù)的狀態(tài)，總的個數(shù)為nn剛開始可以走的個數(shù)為nn-1钮莲，如果n為偶數(shù)nn-1為奇數(shù)免钻，則第一個走的人面臨的就是必贏狀態(tài)，否則第二走的人會贏崔拥。題解來源

#include<cstdio>
int main()
{
    int n;
    while(~scanf("%d",&n),n)
    {
       if(n&1) printf("ailyanlu\n");
       else printf("8600\n");
    }
    return 0;
}

對稱博弈
題目大意：給你n個硬幣极舔，把它圍成一個圓圈。現(xiàn)在有兩個人玩這樣的一個翻轉(zhuǎn)游戲链瓦，每次翻轉(zhuǎn)1--k個硬幣拆魏，最后一個翻轉(zhuǎn)硬幣者勝。
題解：1） 若k=1,則一次只能去翻一枚慈俯，奇數(shù)先手贏渤刃，偶數(shù)后手贏。
2）若k>1:
a: 先手一次翻完贴膘，先手贏卖子；
b: 先手不能翻完，第一次必定斷環(huán)刑峡。只要后手一次翻完洋闽，或?qū)⑵浞譃橄嗟葦?shù)量的兩段玄柠，
之后先手怎么操作后手就怎么操作，后手必贏诫舅。

#include<cstdio>
#include<string.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        if(k==1)
        {
            if(n&1) printf("Case %d: first\n",cas);
            else printf("Case %d: second\n",cas);
        }
        else {
            if(k>=n) printf("Case %d: first\n",cas);
            else printf("Case %d: second\n",cas);
        }
    }
    return 0;
}

階梯博弈
原作者的階梯博弈詳解
首先是對階梯博弈的闡述...博弈在一列階梯上進行...每個階梯上放著自然數(shù)個點..兩個人進行階梯博弈...每一步則是將一個集體上的若干個點( >=1 )移到前面去..最后沒有點可以移動的人輸..

如這就是一個階梯博弈的初始狀態(tài) 2 1 3 2 4 ... 只能把后面的點往前面放...如何來分析這個問題呢...其實階梯博弈經(jīng)過轉(zhuǎn)換可以變?yōu)镹im..把所有奇數(shù)階梯看成N堆石子..做nim..把石子從奇數(shù)堆移動到偶數(shù)堆可以理解為拿走石子..就相當于幾個奇數(shù)堆的石子在做Nim..( 如所給樣例..2³4=5 不為零所以先手必敗)為什么可以這樣來轉(zhuǎn)化羽利？
假設(shè)我們是先手...所給的階梯石子狀態(tài)的奇數(shù)堆做Nim先手能必勝...我就按照能贏的步驟將奇數(shù)堆的石子移動到偶數(shù)堆...如果對手也是移動奇數(shù)堆..我們繼續(xù)移動奇數(shù)堆..如果對手將偶數(shù)堆的石子移動到了奇數(shù)堆..那么我們緊接著將對手所移動的這么多石子從那個奇數(shù)堆移動到下面的偶數(shù)堆...兩次操作后...相當于偶數(shù)堆的石子向下移動了幾個..而奇數(shù)堆依然是原來的樣子...即為必勝的狀態(tài)...就算后手一直在移動偶數(shù)堆的石子到奇數(shù)堆..我們就一直跟著他將石子繼續(xù)往下移..保持奇數(shù)堆不變...如此做下去..我可以跟著后手把偶數(shù)堆的石子移動到0..然后你就不能移動這些石子了...所以整個過程..將偶數(shù)堆移動到奇數(shù)堆不會影響奇數(shù)堆做Nim博弈的過程..整個過程可以抽象為奇數(shù)堆的Nim博弈...
其他的情況...先手必輸?shù)?..類似推理...只要判斷奇數(shù)堆做Nim博弈的情況即可...
為什么是只對奇數(shù)堆做Nim就可以...而不是偶數(shù)堆呢？...因為如果是對偶數(shù)堆做Nim...對手移動奇數(shù)堆的石子到偶數(shù)堆..我們跟著移動這些石子到下一個奇數(shù)堆...那么最后是對手把這些石子移動到了0..我們不能繼續(xù)跟著移動...就只能去破壞原有的Nim而導(dǎo)致勝負關(guān)系的不確定...所以只要對奇數(shù)堆做Nim判斷即可知道勝負情況...

https://vjudge.net/problem/POJ-1704
http://blog.sina.com.cn/s/blog_6a6aa7830100p4nb.html
題意：給定n個不同的數(shù)表示n個位置上有棋子骚勘，兩個人輪流進行操作铐伴，不能操作的人輸，每次可以選一個棋子然后向左移動至少一步并且不能越過別的棋子并且一個格子最多只能有一個棋子俏讹。判斷先手能否必勝当宴。
題解：由于只能向左移，而且不能相互交叉泽疆。我們把兩個硬幣之間的空間看作石子堆户矢，一次左移相當于把某個石子堆(樓梯j)的石子移到了右邊那個石子堆(樓梯j-1)，最后的區(qū)間相當于最低的一層,題目實質(zhì)就變成了階梯博弈殉疼。

#include <cstdio>
#include<algorithm>
using namespace std;
int arr[1010];
int main()
{
    int t,n,k,res;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        arr[0]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",arr+i);
        }
        sort(arr+1,arr+n+1);
        if(n&1) k=1;
        else k=2;
        res=0;
        for(;k<=n;k+=2)
        {
            res^=(arr[k]-arr[k-1]-1);
        }
        if(res) printf("Georgia will win\n");
        else printf("Bob will win\n");
    }
}

http://acm.hdu.edu.cn/showproblem.php?pid=4315
題意：有一群人在爬山梯浪，每個人有個離山頂?shù)木嚯x，且沒有兩個人在同一位置瓢娜，可以多個人在山頂挂洛，其中有一個國王在位置k(標號)，兩個人輪流操作：任意選一個人然后將他向上移動至少位置1且不能越過其他人眠砾，誰將國王移動到山頂誰獲勝虏劲。
題解：首先考慮沒有king的情況，也就是說沒有合法操作的那個人判負褒颈。這樣的話柒巫，可以發(fā)現(xiàn)和上一道題的階梯博弈是等效的。只需要將區(qū)間的距離看成是一堆一堆的石子谷丸，然后將編號為奇數(shù)的堆異或起來就行了堡掏。 但是有一個比較特殊的地方，就是king需要特判一下刨疼。當一共有奇數(shù)個人并且king在第二個人時泉唁，需要將第一個區(qū)間的長度-1，因為如果將第一個區(qū)間直接移動到山頂?shù)脑捚鋵嵤且粋€必勝態(tài)揩慕，只有將第一個區(qū)間留下才是必敗態(tài)游两。并且如果king在第一個人的話Alice必勝。

#include <cstdio>
#include<algorithm>
using namespace std;
int arr[1010];
int main()
{
    int n,res,k;
   while(scanf("%d%d",&n,&k)!=EOF)
   {
      for(int i=1;i<=n;i++)
      {
          scanf("%d",arr+i);
      }
      if(k==1) {
        printf("Alice\n");
        continue;
      }
      res=0;
      if(k==2&&n&1) arr[0]=0;
      else arr[0]=-1;
      for(int i=n;i>=1;i-=2)
      {
          res^=(arr[i]-arr[i-1]-1);
      }
      if(res) printf("Alice\n");
      else printf("Bob\n");
   }
}

http://acm.hdu.edu.cn/showproblem.php?pid=3389
階梯博弈:
題意：有t組數(shù)據(jù)漩绵。每組數(shù)據(jù)有n個盒子，這n個盒子編號為12345678......肛炮。(注意不是從0開始的)每個盒子中有一定量的卡片止吐。每次取編號為B和編號為A的盒子宝踪， 要求滿足B<A &&(A+B)%2=1 && (A+B)%3=0，把A中的任意數(shù)量的卡片轉(zhuǎn)移給B碍扔，誰不能再轉(zhuǎn)移了誰輸.

題解：
1 3 4號盒子是不能夠再轉(zhuǎn)移卡片到其他盒子中去了的瘩燥，其他盒子中的卡片經(jīng)過若干步的轉(zhuǎn)移最終也一定會轉(zhuǎn)移到1 3 4號盒子中去。所以是階梯博弈不同。階梯博弈只需要考慮步數(shù)為奇數(shù)的盒子厉膀，步數(shù)為偶數(shù)的盒子不需要考慮。在本題中編號為1,3,4的盒子不能轉(zhuǎn)移卡片二拐，其余盒子均可轉(zhuǎn)移服鹅。例如：2->1, 5->4, 6->3, 7->2 ,8->1, 9->6...其本質(zhì)為有n級階梯，我們在%3的余數(shù)中進行轉(zhuǎn)移0->0, 1->2, 2->1;最后的結(jié)果一定是1或者3或者4,這些盒子中卡片轉(zhuǎn)移的步數(shù)的奇偶性是一定的百新。為什么這么說呢企软？因為即使有些盒子例如編號11的盒子，有11->4和11->10->8->1兩種選擇饭望，但是這兩種選擇的步數(shù)的奇偶性是相同的仗哨，都是奇數(shù)，所以奇偶性是一定的铅辞。所以我們把這個階梯博弈轉(zhuǎn)化為尼姆博弈就行了厌漂，對步數(shù)為奇數(shù)的盒子進行尼姆博弈≌迳海可以發(fā)現(xiàn)如下規(guī)律：盒子編號模6為0,2,5的位置的移動步數(shù)為奇苇倡，其余為偶。
原作者題解

#include <cstdio>
int main()
{
    int t;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++)
    {
        int n,tmp,res=0,mod;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&tmp);
            mod=i%6;
            if(mod==0||mod==2||mod==5) res^=tmp;
        }
        if(res) printf("Case %d: Alice\n",cas);
        else printf("Case %d: Bob\n",cas);
    }
    return 0;
}

海盜分金問題
原博主博客
有n個海盜倍宾，分m塊金子雏节，其中他們會按一定的順序提出自己的分配方案，如果不少于50%的人贊成（包括他自己）高职，則方案通過钩乍，開始分金子，如果不通過怔锌，則把提出方案的扔到海里寥粹，下一個人繼續(xù)。編號為n的人首先做決策埃元，求位置p的海盜能分到的金子數(shù)量涝涤。如果p被扔到海里，輸出"Thrown".

題解：
首先我們講一下海盜分金決策的三個標準：保命岛杀，拿更多的金子阔拳，殺人，優(yōu)先級是遞減的类嗤。
同時分為兩個狀態(tài)穩(wěn)定狀態(tài)和不穩(wěn)定狀態(tài):如果當n和m的組合使得最先決策的人(編號為n)不會被丟下海, 即游戲會立即結(jié)束, 就稱這個狀態(tài)時"穩(wěn)定的". 反之, 問題會退化為n-1和m的組合, 直到達到一個穩(wěn)定狀態(tài), 所以乘這種狀態(tài)為"不穩(wěn)定的".

接下來我們從簡單的開始分析：
如果只有兩個人的話：那么2號開始提出方案糊肠，這時候知道不管提什么辨宠，他自己肯定贊成，過半數(shù)货裹，方案通過嗤形，那么2號肯定把所有的金子都給了自己。
如果只有三個人的話：那么3號知道弧圆，如果自己死了赋兵，那么2號肯定能把所有金子拿下，對于1號來說沒有半點好處搔预。
那么他就拿出金子賄賂1號霹期，1號拿到1個金子，總比沒有好斯撮，肯定贊成3號经伙，剩下的3號拿下。
如果只有四個人的話：那么4號知道勿锅，如果自己死了帕膜，那么1號拿到1個金子，2號什么都沒有溢十，3號拿下剩下的金子垮刹。
那他就可以拿出部分金子賄賂2號，2號知道如果4號死了张弛，自己將什么都沒有荒典，他肯定贊成4號。
如此類推下去吞鸭，貌似就是第一個決策的時候寺董，與他奇偶性相同的人會被賄賂拿到1個金子，剩下的全歸提出方案的人所有刻剥。

但是會有一個問題便是遮咖，如果金子不夠賄賂怎么辦。
情況1造虏、我們首先歸納之前的御吞，如果n<=2m時候，前面與n相同奇偶性的得到1個金子漓藕，剩下的第n個人拿下陶珠。
情況2、如果n==2m+1享钞，第n個人拿出m個金子賄賂前面的m個人揍诽。自己不拿金子，這樣剛好保證自己不死，這就是之前提到的優(yōu)先級寝姿，首先得保命交排，如果自己拿了一個金子，那么前面就有一個人會反對饵筑，因為對于那個人，不管怎么樣都分不到金子处坪，則輪到第三個原則根资，殺人，肯定投反對票同窘。

剩下來我們考慮玄帕，錢不夠賄賂的情況：
我們將問題具體化：如果有500個海盜，只有100個金子想邦，那么前面201個已經(jīng)分析過了裤纹。
對于202號來說，自己不能拿金幣丧没，而賄賂上一輪沒有拿到金幣的101人中的100人就夠了鹰椒。
對于203號來說，需要102個人的支持呕童，顯然加上他自己漆际，還需要101票，而金子不夠賄賂夺饲，別人會反對奸汇，而達到殺人的目的。
對于204號來說往声，他知道一旦自己死了擂找，203號是必死，抓住這點浩销，203必然支持他贯涎，因為203號寧可不要金幣，也要保住性命撼嗓，所以204號把100個金幣分給之前的100個人柬采，然后203和他自己的兩票保證自己不死。
對于205號來說且警，203粉捻，和204是不會支持他的，因為一旦205死了斑芜，他們不僅可以保住性命肩刃，而且還可以看著205死掉。所以205是必死
那么206呢，雖然205必死盈包，會支持他沸呐，但是還是缺一票，所以必死呢燥。
對于207呢崭添，205和206之前是必死，會支持他叛氨，但是加上自己以及100個賄賂名額呼渣，還是必死
對于208號，205寞埠，206.屁置，207因為后面是必死的，肯定會支持208成功仁连，那么208剛好能湊齊104票蓝角，得以保命。

以下我們猜想：n=2m+2^k的情況下饭冬，是可以保命的使鹅，稱為穩(wěn)定狀態(tài)，否則為不穩(wěn)定狀態(tài)伍伤，我們證明一下：
首先對于n來說并徘，有m票賄賂，但是對于2m+2^{(k-1)以前必死的死扰魂，他們會支持2*m+2}(k-1)麦乞，因為他們肯定拿不到錢，而且支持2m+2^(k-1)劝评，另外根據(jù)殺人原則姐直，希望之后的人都死，輪到2m+2^(k-1)決策的時候保命就行了蒋畜。
同理2m+2^(k-1)到2m+2^k之間的2(k-1)-1個人來說声畏，他們必死，所以必定支持2m+2^{k,加上m個金幣賄賂的姻成，加上他自己插龄，剛好有m+2}(k-1)。這樣剛好湊齊一半科展，可以不死均牢。
證明完畢：2m+2^k的人可以保命，否則必死才睹。

我們考慮一下分金幣情況：
情況3：對于第2m+2^k個人來說徘跪，他可以保命甘邀，肯定分不到金子，而他手上的m個金子垮庐，可以賄賂m個人松邪，但是具體是哪些人是不定的。則不管是不能分到金子哨查，還是可能分不到金子的人來說逗抑，結(jié)果都為0。
情況4：對于2m+2^{(k-1)到2*m+2}k之間的來說寒亥，他們的決策是必死锋八，而在他們決策的時候，其它人分得金幣情況也為0。

我們來解釋一下金幣的不確定性：
金幣數(shù)量的不確定性:由上面的推理可知, 當n=2m+2時, 上一輪推理沒有分到金幣的人的金幣數(shù)量首次具有不確定性, 并且在n>2m+2時, 這種不確定性一定會延續(xù)下去, 輪到因為n號決策者之前的一個人決策時, 那個人肯定分不到金幣了, 所以在上一輪推理中沒有分到金幣的人的個數(shù)一定大于m.

綜合情況1吮炕，2镀脂，3，4便是本題的解政冻。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int fac[15]={2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};//保存2的冪 
void solve(int n,int m,int p)
{
    //金幣夠賄賂的情況  
    if(n<=2*m)
    {
        //不是決策者，而且奇偶性相同，都能被賄賂  
        if(n!=p&&(p%2==n%2)) printf("1\n");
        else if(n==p) printf("%d\n",m-(n-1)/2);//剩下的都是決策者擁有
        else printf("0\n");//其余人分不到金幣胸竞，他們的決策不影響全局 
        return;
    }
    else if(n==2*m+1)   //這時候的不同在于決策者不能拿金幣  
    {
        if(n==p) printf("0\n");//p是決策者
        else if(p&1) printf("1\n");//p不是決策者，p的奇偶性與決策者一樣参萄，p接受決策者的賄賂
        else printf("0\n");
        return;
    }
    
    
    int t=n-2*m;
    //這是剛好保命的情況卫枝，對于決策者來說，肯定沒有金幣  
    //對于其它人來說讹挎，要么肯定沒有金幣校赤，要么可能沒有金幣，不確定性  
    for(int i=1;i<14;i++)
    {
        if(t<fac[i])
        {
            if(2*m+fac[i-1]<p&&p<2*m+fac[i])//在這個位置上的p必死筒溃。
            {
                printf("Thrown\n");
            }
            else printf("0\n");//如果p是正好在2*m+2^k的位置上马篮，p可以保命。
            return;
        }
    }

}
int main()
{
    int t,n,m,p;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&p);
        solve(n,m,p);
    }
    return 0;
}