山东省第七届省赛

A:水

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T,A,B;
    while(~scanf("%d",&T)){
        for(int i=0;i<T;++i){
            cin>>A>>B;
            if(A%B){
                cout<<(A/B)+1<<endl;
            }else{
                cout<<(A/B)<<endl;
            }
        }
    }
    return 0;
}

B:二分(或者可以暴力,只有45个FB)结论题,用到斐波那契博弈里的一个结论:任何数都可以被拆成不同斐波那契的和,进而猜测直接从最大的小于N的FB往下找即可

我吐槽下SDUT的OJ…尼玛10^9能写成109,劳资找了大大大大大大半天错硬是不知道错哪里了艹

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=45;
int Fb[maxn],M;
int vis[maxn],has_ans;

void init(){
    Fb[0]=1;
    Fb[1]=2;
    for(int i=2;i<maxn;++i){
        Fb[i]=Fb[i-1]+Fb[i-2];
        //printf("%d\n",Fb[i]);
    }

}

void solve(int N){
    stack<int> ans;
    int mx=maxn;
    while(N!=0){
        int ind=lower_bound(Fb,Fb+mx,N)-Fb;
        if(Fb[ind]>N)ind-=1;
        N=N-Fb[ind];
        ans.push(Fb[ind]);
    }
    printf("%d=",M);
    int t=0;
    while(!ans.empty()){
        if(!t){
            printf("%d",ans.top());t++;
        }else printf("+%d",ans.top());
        ans.pop();
    }
    printf("\n");
}

int main(){
    init();
    int T;
    scanf("%d",&T);
    while(T--){
        memset(vis,0,sizeof(vis));
        has_ans=0;
        scanf("%d",&M);
        solve(M);
    }
    return 0;
}

/***************************************************
User name: 奥术大师大所大
Result: Accepted
Take time: 40ms
Take Memory: 196KB
Submit time: 2018-03-04 13:39:50
****************************************************/

E:简单枚举

#include<bits/stdc++.h>
using namespace std;
const int maxn=110;

int T,N,M;
char mp[maxn][maxn];
int dist[4][2]={{1,0},{-1,0},{0,-1},{0,1}};

bool check(int x,int y){
    if(x<1 || x>M || y<1 || y>N) return false;
    return true;
}

int main(){
    scanf("%d",&T);
    while(T--){
        int ans=0;
        scanf("%d%d",&M,&N);
        for(int i=1;i<=M;++i){
            scanf("%s",mp[i]+1);
        }
        for(int i=1;i<=M;++i){
            for(int j=1;j<=N;++j){
                if(mp[i][j]=='#'){
                    for(int k=0;k<4;++k){
                        int x=i+dist[k][0],y=j+dist[k][1];
                        if(check(x,y)){
                            if(mp[x][y]=='#')continue;
                            int room=0;
                            for(int kk=0;kk<4;++kk){
                                int xx=x+dist[kk][0],yy=y+dist[kk][1];
                                if(check(xx,yy)){
                                    if(mp[xx][yy]=='#')++room;
                                }
                            }
                            if(room==1)ans++;
                        }else ++ans;
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}


/***************************************************
User name: 奥术大师大所大
Result: Accepted
Take time: 228ms
Take Memory: 212KB
Submit time: 2018-03-04 14:46:06
****************************************************/

G:找规律,不像博弈,抱歉,会打表,但是规律想不出来,对不起

打表

#include<bits/stdc++.h>
using namespace std;

int solve(int N){
    int ans=0;
    for(int i=1;i<N;++i){
        for(int j=i;j<N-i;++j){
            int k=N-i-j;
            if((i^j^k)==0) ans++;
        }
    }
    return ans;
}

int main(){
    for(int i=1;i<=200;++i){
        printf("%d: %d\n",i,solve(i)/3);
    }
    return 0;
}

找的规律,知道规律了,直接粘的别人代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int ans,pp;
    int i;
    long long int f[100];
    f[2]=1;
    f[1]=0;
    f[0]=0;
    for(i=3;i<30;i++)
        f[i]=f[i-1]*3+1;
    long long int a;
    int T;
    cin>>T;
    while(T--)
    {
        cin>>a;
        ans=0;
        if(a%2)
        {
            cout<<0<<endl;
            continue;
        }
        while(a!=0)
        {
            pp=a%2;
            if(pp)
                ans++;
            a/=2;
        }
        cout<<f[ans]<<endl;
    }
}

J:题目翻译: http://www.bubuko.com/infodetail-1612259.html 说实话,完全理解题意了基本就是水题.但对我不是.

#include<bits/stdc++.h>
using namespace std;
int T;
char str[1000];
int main(){
    cin>>T;
    while(T--){
        int N,M;
        cin>>N>>M;
        int c=0,m=0,o=0,b=0;
        getchar();
        for(int i=0;i<N;++i){
            gets(str);
            if(str[0]=='C'){
                c++;
            }else if(str[0]=='M'){
                m++;
            }else if(str[0]=='O'){
                o++;
            }else if(str[0]=='B'){
                b++;
            }
        }
        int ans=o*(2+(N-1)+m*2)+b*(2+m*2);
        if(ans>=M){
            puts("Mrghllghghllghg!");
        }else puts("Tell you a joke, the execution of Paladin.");
    }
    return 0;
}

K:水

#include<bits/stdc++.h>
using namespace std;
const int maxn=10010,maxm=5010;
int N;
stack<char> st;
int main(){
    while(~scanf("%d\n",&N)){
        char qb;
        while(N--){
            int f=0;
            do{
                do{
                    qb=getchar();
                    if(isalpha(qb)) st.push(qb);
                }while(qb!=' ' && qb!='\n');
                if(f==0)f++;
                else printf(" ");
                while(!st.empty()){
                    printf("%c",st.top());
                    st.pop();
                }
            }while(qb!='\n');
            printf("\n");
        }
    }
    return 0;
}

2018年全国多校算法寒假训练营练习比赛(第五场) G 斐波那契博弈

斐波那契博弈模板题,我凑…

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
set<int> st;
int FB[maxn];
int n;
inline void init(){
    FB[1]=1ll;FB[0]=1ll;
    int i;
    for(i=2;FB[i-1]<=1e9+7;++i){
        FB[i]=FB[i-1]+FB[i-2];
        st.insert(FB[i]);
    }
}

int main(){
    init();
    while(~scanf("%d",&n)){
        if(st.find(n)!=st.end()){
            cout<<"Sha"<<endl;
        }else{
            cout<<"Xian"<<endl;
        }
    }
    return 0;
}

2018全国多校算法寒假练习赛(三) D

这道题以前在lrj上见过,不过没注意.

Link

https://www.nowcoder.net/acm/contest/75/D

Type: 博弈论

题目

链接:https://www.nowcoder.net/acm/contest/75/D
来源:牛客网

小牛和小客玩石子游戏,他们用n个石子围成一圈,小牛和小客分别从其中取石子,谁先取完谁胜,每次可以从一圈中取一个或者相邻两个,每次都是小牛先取,请输出胜利者的名字(小牛获胜输出XiaoNiu,小客获胜输出XiaoKe)(1 2 3 4 取走 2 13 不算相邻)

约束

输入包括多组测试数据
每组测试数据一个n(1≤n≤1e9)

输出

每组用一行输出胜利者的名字(小牛获胜输出XiaoNiu,小客获胜输出XiaoKe)

题解

我直接说推出的结论了
很明显的是:

n=0时,先手必败,n=1,2时,先手必胜

然后我们看n>=3:

  1. n=3时很明显先手必败
  2. n=4时,无论先手者取1还是2,只需要和他取一样的即可,把当前的石子堆分成两部分,每部分有一样的石子,可以发现,该情况下先手必败(只需要和先手者操作一样即可获胜).

    然后我们可以发现只要是偶数都可以这样乱搞

  3. n=5时,无论先手者取1还是2,只需要和他取相反的即可,其余和以上一样,同样将石子堆分为两堆.

    然后我们发现只要是奇数都可以这样乱搞

Code

/**

                                                                       :;LaEaHKEEGpPXU7;,
                                                                  .:75pKH11252U252XapZgRQgD6XJscLr;,.
                                                               :LXpRgGaX521JLw1JswJJsJs22XHPPEZEGDOMMRDOa7.
                                                           .r2EDDZEpZPZP6KpHX5SXH5XXa5KwaXaSX5UJ1c77sLs2GMQQ6r                                       .
                                                        ,LpgOGpEZGZEZEpZKpHHU5wP5HEDgpXpHa2SSa5aSXULr7rrirrJXRBp;                                   ;B
                                                     ,J6MRZH6EgEEZE6E6EZZPZXXwSSGQXr::aPpP5USUHaHaKa5Lvrr7ri;rLHBB2:                                Kc
                                                   rpQDOpPPOGGZOGOZG6GEOEOEDPPGBa.  .PaSSUXSUUUaUSaKXKS177r7rrrirSBBR7                             .O,
                                                :UBQOKPK6ZOOOEDEO6GZE6EpEpDgDBR:   UBpXHa5aSaUS5SUS5XapPHJc7rrv7rr7sgBBs                           .g.
                                              ;gBMPXpO6GEOEOEOEGEOEE6EZEEDRGBB    EB5pKSXpHKaHSX552S5aUHHEX17c7vr7777s5RBS:                        .R;
                                           .sQBPXpDZOODOgODGOGgEDEOEOGgGgOOMB:   LBKKSXSHa52aaKXHXKaa5aSaaHXSJLcL7vcc777JDBBg2;.                    Qi
                                         ;2ggp2EDDOggGEDGgDDOgGGZDOOZOGg6gEBX    vBZaHUKaaUXXXSXXKXpXHXH5wwaa52U1wssLsLJccv1UDQBQ67.                O7
                                       :ZZUU5PROOEOZOZGGOODZOGgODZOOgOggRgRB; ;:..R6XaKKpP6PGppKPHpHpPX5aU21UUa5Sw52UwUJJv77L77sSpQMDU;            ;B5
                                     ,SRJ7sSHGggEOZOEG6OODpOZgggOQQBBBBBQBBQ.,;;. LBOgOgDRDDZODMgQRgRDaa552a252UUa25w5UaU2sLvccs7r7sJZBBMr       ,XQJ:
                                    LQHr77J6RGOZDZOEGEDGgDRORQBBBQRDPU1Jscwa7.,::.:J7r;::::.  ..,:;i7UOgRRRgDPH5SUSU52U2HHa1JJJLJLccLr71RBB,    7R2,
                                  :RZv;77JSgGOZEODEDGOEggQBBBMS7;:,:,,.,.,.:7L;:,;.:  ,: . .....       .:;rJU6GgGRggEZHPaKXX2S221Js1Lc7r:7QB. .XX:
                                 7g1;;7rcXG6gpGDZGgZOOQBBQpr.   ::::;:;:::Jr::sr;::;:.:vs,:::::::::::,,         ,:7L5HGOggRgZUUU5wSUaJLc7r7BOiDr  ...
                               .XX;;;irLHGKpZZZEKgDRBBB6i    ,;;:;;;;r;;:s177:,;L7:;7:.rHi,:::::::::::::::::,.         .,;7ZRQgO6KUUJsLwsJ7KBM. .....
                               JZ:;rrrc5EPHp6XgpRBBBE;     :i:;;;;;:;;;:c7::r7;,::::::::rv:,:::::::::::,:,:,:,,,,            .;sORQRGX21wsXU:  .... .
                              .Br;iir72EHPHZ6EgBBR7.   ..;ii:;;;;;;;;;:71r::.:7,  .::7;:;H;.::,:::::::,:::::,,,::,,,              ,7wEDRZBMr  .......
                              1D;:r;rwOPXPKH6BBX,   .:;:;;;:::;:;;;;;::Ls,;ss..r.  ,c77;sLU,:,:::,:::,:,:,:,,,:,,,:::.                  .:.rP:.......
                              D2:i;rJpKHXHXgg7    .,,::::;:::::;:;:;;:;SL7sS2, :.   ::::,:U7.:::,:::,:,,,,,:,,.,,,.,:,                    ;L:. .. ...
                             :Qc;i7LGZPa6gBM,  ...,,::::::::::::;;::;.JJ;ic:         ;:::,v1,.:::;7,,,:,:,:,,,,.:,,,,..                :2wr.  .......
                             sRr:rrwZGgBQR7.  .,,::::::::::::::;::;:::Hr:7i          ,;;:::U: .,,,:r.,,:,:,:,,,:,,,.....             7K2:. ..........
                             OX:irsXgQZ:.   .,,:::,,:::,::::::::;;;::r5;r7:           :;;;:7L ..,.,;:,:,:,,,:,:,,,,......        .rU6w;..............
                            .BJ71EK5;.   .,,::,:,:,,,:,:,::::::::;:;.Ls;r7             :;:::s, ..,,,r:.:.,,,.:, .,..... .    .;s5XJr,..,.............
                            1Mv::.     .:,:,,,,,,,:::::::,;:::;:;::..J7;c:          ,. ,rri:27  , .,:;. ,:,:,,:..,....    .rpPL;:.. ... .............
                       ..7Ls:        .,,,:,,,:,:,:::,:,:::::,:::::: .Srrr,  .,:;;;::::..:7r;r1    .: :E:..,,:,...,,.., ..XBQ7, ................... ..
                  ,;7v7r7:,         ,,,,:.,,,,,,:,,::,:,,.::.,:.,:, :Jrr; ,r7,:..        ,:::L:  .  .7RJ .,.:.,......,,:MBs   ..............,........
            .:;vJs7i,              ,,,., ..,,:,,,:,,,:,:.,rs,,.:,,  ;J;c,                .,::;;     Lr.E: .,...,....:,:1Z:  .........,.,...........:,.
   .;,,:r7J1wv;,.               ....,.:. .,.,,:,,,:,,::::,sS;.:::,  cLrr.     .       .,. .,..:    ;;  r5 ........,,:;s7. ....,.,.,...........,.,.,,.
   ,BBs:::                   . ........,.,,,,,.:,,,:,:,,.;s7r,,,,,  cc7;         ,.,,.      .:7rrJGMPOEL1, ..... ,,:rSr, : ,.,.,.,.,.........,,,,,. ..
     rZL.                   ....... ..,,,.,,,..,,,.,;,...7J:s: ..  .wr7,        ...    .rJpQBBBBBBBQgKP77s  ..  .,7S2,,....,....,.,.,......,,.,. .:cX2
       ;SH7,               . . . .. .,.,.,.,,,...,..r, ::Ur;7L .   .57;.           .rPBBQBBBPws:;r::::.,:P.    .;S5;,..,...,.,.,.,.... ..,,, ..,7HSJvr
          r7r;:             . ... ..........,...,.. 7L;,rS;;ivr .   1r:       .  .rZBBK7;.JL,::Jrs;.:;,:;J, .,;LDv..:.,...,.,.,.,...,.,,:,, ,7sKGwc77;
             .:7L7:,            . ,r,..,.,,,...,..:iLL  7s;r;cv:    U7.         :vi;:. .. :Er:::.Ls. . ,7::::vHEi ,:,,.,,,.,.,,,,,,::::, .:1QBKJJUsssc
                .:rvw1JsL7;,      ,;..........,.:ir :r .ELr77v:,.   Pr          ..      .  Ls    ,w.   rr.r:JPr. ::,..,,,.,,,,:,:::,:,..7XgRE52US25w1c
                      .:;7JRQpX:   ; .........,i:  .,J ;gri;7r  :   1;                     .X:    .   ,v :aK1, ,,:.,,,.,,,,:::::,;::::cOBB6K55UXUX5XUw
                           ;J,XQB7,:    . ...,:   .:7Z.7Zi7;r:   ,  v,                      :w:;,.,:::7LUsc:..:,:.:,,,,,:,:::::::,:;c5BBPS5wSUSUaUaUa2
                           J7  rEBBg..,. ..... .  ,L1PLKr:,:;r;;::, :,                       :;SXsJU1XLLr....:,,,,,,::::,::::::,::LL,,rZXUJU25552aUUUU
                           JL .:sXBB:... ., .    ,OH777;,rZRBBBQL ..r,                     ,:r7::r:,;;....:,,,,,,,,.::::;::;:::.7gL    UK2UUS1aw2wU25J
                           U7 .r71BB;  . :.. .. :QJ;.;1pBBBBBGRBRi  i:                   .      .w7.   ..,,:,,,,,:,:,:::::::,.,2BR:   .DSaUSUUS525w5U1
                           2r :7rJBQ7   .;. .   KL::JGBBBgE6Hp6XMQ;     .                    ... ,2s    ,,,,:::::,:::::::,,.:sQQB2    ;DHa5U52S2U25USJ
                           a: :7;1BB2   .v,    sL;LPQgDBPH6KPQBpGBG    .                   ... ..  aP:. .. ,::,:::::,,,,.;rSgBQDa;    :gSSwSUUU525US2U
                           5; ;;r2QBB,  .s:  :a7:PBZ2,:BEaZPKgBZOgB,                        .   ...:LEHri::,:.,,.,,,::rsXRBgGKEJi,    2GH252SUS5S11wH5
                           U: ;:rwDBBr  .c, rB6r 167.,,RQPpEP6OpKEBc      .,                 .   : ::sS7;cKB6HHa1XOQRRQBRgEZDBH; ..  ;RZUPSSU525USSpK2
                           s; ;::aBg,   .; .Gv,H::,,::,;BQDOGHPXpKBs      .,.                 . .,.  .r:;:6gOEBQRRRDggQgOHgMGL,    .;PEHHXaaKaPXPKPaXS
                           s7.:,sBa     :..S,  vE::::;  7BBMgZH6pQBr             .             ,:,   ,.,r2RHSSpMZPKRRZpgggav,    ;UpEZaaaKHHUHPPaUJHGO
                           a;.775:    .::rU.    gR:,:.   :;:BBBBQar                         .  ,,   ,.,7rggJwU6DDGMgOGgXc:,   ,rPGOpKSXSXSKUKHU1UHgOEP
                          1i :SZJrLXpBBMRB:  .v  Ba,.       :sv:                             .        irsBUSpEEGPPpg65r:..,;sKZDZHSX5XaHU55K2wUGMRZ6Z6
                         :K  :7asvwc2MgEQB, :gg.:iB7  .,,,:.                      ...,.   .     ..   .:iM6GEpSSXZOEs:...;spZpKKXXSX5Xa5Ja5wwKGQDEpp6OZ
                         w; ,LXLr77sLwL5aR. gRgQgaQBi ,vJwvi,.                 .;;:;7:   .   .  ,...  rRDRJUSXpgas:,.:;U66SaHa2X5aUa552X12SgQgpZpEpGOD
                         H: ;XJ;77rv7rJUaQ;rgaPgXXHBB;        . .              .ri:;;          ,: . :6QZEKHXpXXL:,::r1PKXaa2XSS5a5S5UJ22aOBgEpOppZOOgG
                         iwsJsr7rsLrrLcJ2gQGXHwa1SUHBB:  . ... .                 ..,           :   1BRKpOEGp2Jr;::rsXP1Uaa2U5a5aUa5SsSpgQRZGZEEZZOOgDg
                           ,cs5aXaP552ssLwRSHXaSS5asXBB.      . .                             .  LBBgGgZHsr;vrr;rcXpP5UUS5X5S2XS5SS1URBggpEZgDDGOGggRD
                              ,;irrs2KgQRPJJJSUXKXSHJpBM   . . .                                ZBBOUsr;:.  ,,,rHgZPUaSaUSUSSXaUPXsSBB6ZZp6EEGOOGDEggO
                                       ;BBQQZaSJ5J15SJDQ7                                    .iEBL:.  . .,:,:;SRQGZXPXXSHaS2UUSUSswQB6OZgG6pZZGODEOGDE
                                      JgUri1aGEpEpXSS5LBQ,                              .rLap2Jr     ;712OO6ZggRDZXHXpKK2211LLLc7wgBa2PODRGE6OZgDgGDGD
                                    7QB; ,Jc76DaZXOZgDPEBBX,                       :c1HEZ1c;:,.,:;cHDgQQggMZgGOZO6OEGpXsLLsJXHPOBBBc;vss5EMggZDODOgED6
                                   LZJ::iwrrr72EPgXU5OBBBBBBBp7:               .i5P6wL;,   .:LS6DMgMgZKgEOPOGGDDGEXULvLSOBBBBBQBgDQDJ5rrr7JOQQDDZGEgDD
                                   wp rR5,       .HQRX7r72RQBBBBBQBMEK6Uc7sc7cHOU:,     .:LHgOQg6ZOPZpZGGEDERZPwcr7LKDDaJr:.      rBX;;:r:ir1DBQMgRgDp
                                   7D,sw:      ,   Z.      .LgBBQBBOsJaQBBBBBBXrr.  .:rwZBBQgROgDgDOERRMgROOScrLsPP5r,             7Qs,::::::rUgRgZOG6
                                   ,Q57:r  ,:  ,r  U:         .;;   .vL7L;r:UG7.:sr;JSgQBgDEZXXUSXpHa21svr7r7s2v:.                  iQK...:,:::;LLJJws
                                    OBHs;.  :;;,v  H:             :6X;       rpL;7pSrrr7r;::,....,,:;iirrvvvr,                       :BBPs;;:,,,,::;::
                                    ::rPDEL:..7:c;7r              pK  .:      :KL.:r:..     ..:icsS5sr:,.                              JgGgBQDOSJss77r
                                         :r;:::  ,                PH r,       ,;5: ,::::;7Ls7Lc7;:                                         ,:7JP17rJUs
                                                                  .:J: :;  .,:K6BQS7:.,.,.
                                                                    :r7Ji;r7;::;;.**/
                                                                        .
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        if(n<=2)cout<<"XiaoNiu"<<endl;
        else cout<<"XiaoKe"<<endl;
    }
    return 0;
}

HDU 1849

【Nim博弈】
这道题一开始看上去不像Nim博弈,但它为什么会是Nim博弈呢?
首先我们可以看原题上的那个图:

原题说我们需要将每个格子内的棋子进行移动,当所有棋子都位于最左边编号为0的格子时,游戏结束.

首先我们将棋盘竖起来(自己画的,所以会少一点,但大体意思一样).

然后我们将其中的棋子分开来:

这样我们就可以将其转化为Nim博弈了.我们可以视为当前棋子所在的位置代表当前堆的石子个数.因为只能向左移动,即只能减少石子的数量.当棋子移动到0时,即代表石子已取空.

Code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int K;
    while(~scanf("%d",&K)){
        if(K==0) break;
        int ans=0;
        while(K--){
            int a;
            scanf("%d",&a);
            ans^=a;
        }
        if(ans==0)puts("Grass Win!");
        else puts("Rabbit Win!");
    }
    return 0;
}

HDU 1847

【博弈论 – SG函数】

题目:

Good Luck in CET-4 Everybody!

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 11483 Accepted Submission(s): 7446

大学英语四级考试就要来临了,你是不是在紧张的复习?也许紧张得连短学期的ACM都没工夫练习了,反正我知道的Kiki和Cici都是如此。当然,作为在考场浸润了十几载的当代大学生,Kiki和Cici更懂得考前的放松,所谓“张弛有道”就是这个意思。这不,Kiki和Cici在每天晚上休息之前都要玩一会儿扑克牌以放松神经。
“升级”?“双扣”?“红五”?还是“斗地主”?
当然都不是!那多俗啊~
作为计算机学院的学生,Kiki和Cici打牌的时候可没忘记专业,她们打牌的规则是这样的:
1、 总共n张牌;
2、 双方轮流抓牌;
3、 每人每次抓牌的个数只能是2的幂次(即:1,2,4,8,16…)
4、 抓完牌,胜负结果也出来了:最后抓完牌的人为胜者;
假设Kiki和Cici都是足够聪明(其实不用假设,哪有不聪明的学生~),并且每次都是Kiki先抓牌,请问谁能赢呢?
当然,打牌无论谁赢都问题不大,重要的是马上到来的CET-4能有好的状态。

Good luck in CET-4 everybody!

Input

输入数据包含多个测试用例,每个测试用例占一行,包含一个整数n(1<=n<=1000)。

Output

如果Kiki能赢的话,请输出“Kiki”,否则请输出“Cici”,每个实例的输出占一行。

SampleInput

1
3

SampleOutput

Kiki
Cici

题解

首先我们要知道SG函数代表的是当前状态的数值.如果是0,则为先手必败(SG函数值为可到达状态中未出现的最小的整数).然后我们从SG函数延伸一下–

1.我们假设当n=0时,先手必败.
2.当n=1时,因为S(0)=0,所以当前状态是非奇异局势.先手必胜,即,你可以通过拿走一定的牌使下一个拿牌的人的局势变成奇异局势(必败态).
即转移给下一个抽牌者状态为S(0).
3.当n=2是,因为S(0)=0,S(1)=1.所以当前状态是非奇异局势,先手必胜.
即你可以把下一个抽牌者状态转换成S(0).
4.当n=3时,可到达状态为S(3-1)=S(2)=1.S(3-2)=S(1)=1.因为无论往那个状态走,都会使对方先手必胜,所以该局势为奇异局势.先手必败.

故我们可以根据以上推理过程将全部的1000个状态是否必胜预处理处来.其预处理过程为检查可以到达的状态是否存在奇异局势,如果存在,则该局势为非奇异局势,即先手必胜态.

因为可拿牌数都是2^n.所以预处理复杂度为O(nlg(n)).

PS…:其实预处理完以后你会发现.每当n%3==0时,为奇异局势.

Code:

//SG函数
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

bool game[1001];

void init(){
    memset(game,false,sizeof(game));
    for(int i=1;i<=1000;++i){
        int t=1;
        while(i-t>=0){
            //如果i-t是奇异局势,则先手必胜
            if(!game[i-t]){
                game[i]=true;
                break;
            }
            t<<=1;
        }
    }
}

int main(){
    init();
    int n;
    while(~scanf("%d",&n)){
        if(game[n]){
            printf("Kiki\n");
        }else{
            printf("Cici\n");
        }
    }
    return 0;
}

POJ 1067

【威佐夫博弈】

//威佐夫博弈
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        int k=max(n,m)-min(n,m);
        int ak=k*(1+sqrt(5))/2;
        int bk=ak+k;
        if(min(n,m)==ak&&max(n,m)==bk){
            printf("0\n");
        }else{
            printf("1\n");
        }
    }
    return 0;
}

HDU 1846

裸的巴什博奕,这道题出现了一个问题就是,我想~scanf(“%d”,&T),结果一直是wrong,所以如果是单纯用T的题还是不要这样写了.

//巴什博奕
#include<bits/stdc++.h>
using namespace std;
int main(){
    int T,n,m;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        if((n)%(m+1)==0) printf("second\n");
        else printf("first\n");
    }
    return 0;
}

HDU 2149

【巴什博奕】

题目:

虽然不想,但是现实总归是现实,Lele始终没有逃过退学的命运,因为他没有拿到奖学金。现在等待他的,就是像FarmJohn一样的农田生涯。

要种田得有田才行,Lele听说街上正在举行一场别开生面的拍卖会,拍卖的物品正好就是一块20亩的田地。于是,Lele带上他的全部积蓄,冲往拍卖会。

后来发现,整个拍卖会只有Lele和他的死对头Yueyue。

通过打听,Lele知道这场拍卖的规则是这样的:刚开始底价为0,两个人轮流开始加价,不过每次加价的幅度要在1~N之间,当价格大于或等于田地的成本价 M 时,主办方就把这块田地卖给这次叫价的人。

Lele和Yueyue虽然考试不行,但是对拍卖却十分精通,而且他们两个人都十分想得到这块田地。所以他们每次都是选对自己最有利的方式进行加价。

由于Lele字典序比Yueyue靠前,所以每次都是由Lele先开始加价,请问,第一次加价的时候,
Lele要出多少才能保证自己买得到这块地呢?

Input:

本题目包含多组测试,请处理到文件结束(EOF)。每组测试占一行。
每组测试包含两个整数M和N(含义见题目描述,0<N,M<1100)

Output:

对于每组数据,在一行里按递增的顺序输出Lele第一次可以加的价。两个数据之间用空格隔开。
如果Lele在第一次无论如何出价都无法买到这块土地,就输出”none”。

Sample Input:

4 2
3 2
3 5

Sample Output:

1
none
3 4 5

题解

我们知道,在巴士博弈中,n=0为先手必输态,之后n=m+1为下一个先手必输态.
而当Lele在竞拍的时候,如果他所在的初始状态是如上所述的这样一个奇异局势(即先手必输局势),那他一定输(none).
当Lele在竞拍处于非奇异局势时,在选择最优的情况下,他一定可以赢得竞拍.即他只需要通过增价将对手置于奇异状态即可.
所以当我们想要找出Lele第一次出家的可能性时,只需要先找出Lele的第一个置对方为奇异局势的 价格 .然后在寻找下一个的时候只需要依次++,直到下一次加价会给对方一个 非奇异局势前 结束循环.
当然,存在一种可能性就是,初次加价可能会溢出n的价格范围.

//巴什博奕
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        if(n%(m+1)==0) printf("none\n");
        else{
            int next=0;
            while(1){
                next++;
                if((n-next)%(m+1)==0){
                    printf("%d",next);
                    break;
                }
            }
            while(next<m){
                next++;
                if((n-next)%(m+1)==0 || next>=n){
                    printf(" %d",next);
                }else{
                    break;
                }
            }
            printf("\n");
        }
    }
    return 0;
}

HDU 2188

【巴什博奕】

可以将题意转换为: 有n块石子,每次最多取m个,Grass先取.则转换成裸巴什博奕.

//巴什博奕
#include<bits/stdc++.h>
using namespace std;
int main(){
    int T,n,m;
    while(~scanf("%d",&T)){
        while(T--){
            scanf("%d%d",&n,&m);
            if((n)%(m+1)==0) printf("Rabbit\n");
            else printf("Grass\n");
        }
    }
    return 0;
}

博弈论

博弈论

博弈树

重点在于min和max状态间的关系,以及每个树节点的评分值.以及优化的Alpha-Beta剪枝.省略不写。

SG函数

基本概念

在公平的组合游戏中(游戏规则对于两个玩家不加以区分),可以把所有有可能出现的状态看作是图的节点,如果从一个状态可以通过一步转移到达另一个状态,则两点间有一条有向边,这样就得到了一个状态图.

巴什博奕

以巴什博奕为例,一共有n个物品,两人轮流取,一次最少取走1个最多去走m个,最后取光的人获胜。下图展示了n=6,m=3的时候的状态图,节点内的数字表示当前状态剩下的物品的个数.

假设游戏不会出现平局,即状态图是无环图的话,所有的状态可以分为两种,P态和N态。P态表示该状态对于前一个玩家来说是必胜态,而N态表示该状态对于下一个玩家来说是必胜态。例如对于n=6,m=3的巴什博奕来说,0个物品显然是P态,而还剩1、2或3个物品的状态都是N态。

一个状态被称为终止状态,如果当前状态下游戏不能再继续进行,譬如巴什博奕种物品都已经被取光了,在大部分游戏规则中,终止状态都是P态,所以如果不加特殊说明,一下都假设P态为终止状态.

从定义可知,任意一个P态,他要么是终止状态,要么他所有可以转移到的状态都是N态,而对于任意一个N态,他至少有一个后继状态是P态.

SG函数

SG函数是这样定义的:对于任意状态x,他的SG函数值g(x)=mex{g(y)|y是x的后续状态},其中mex是一个对于非负整数集合S的运算, mex(S)为S中没有出现的最小负整数 。对于一个终止状态,因为他没有后继状态,所以他的SG函数值是0.

还是以上面的巴什博奕为例:

n=6,m=3.用Si表示还剩i个物品的状态。S0是终止状态,所以g(S0)=0。S1的唯一后继状态是S0,所以g(S1)=1,S2可以转移到S1和S0,所以g(S2)是2.因为S3可以转移到S0,S1,S2,所以g(S3)=3.对于S4来说,它可以转移到S1,S2,S3(1,2,3),所以g(S4)=0.以此类推可以知道g(S5)=1,g(S6)=2.

如果知道一个状态SG函数值,则可以快速的判断当前状态时P态还是N态.对于一个函数,如果状态值是0则是P态,否则就是N态.

g(S4),P态,先手必败(后继都是N态);g(S5),N态(后继有P态),先手必胜.

KuangBin介绍博弈

(一)巴什博奕(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者胜。

(二)威佐夫博奕(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),若 b = a,则同时从两堆中取走 a 个物体,就变为了
奇异局势(0,0);如果a = ak ,b > bk,那么,取走b – bk个物体,即变为奇异局
势;如果 a = ak , b < bk ,则同时从两堆中拿走 ak – ab + ak个物体,变为奇异局
势( ab – ak , ab – ak+ b – ak);如果a > ak ,b= ak + k,则从第一堆中拿走多余
的数量a – ak 即可;如果a < ak ,b= ak + k,分两种情况,第一种,a=aj (j < k)
,从第二堆里面拿走 b – bj 即可;第二种,a=bj (j < k),从第二堆里面拿走 b – a
j 即可。

从如上性质可知,两个人如果都采用正确操作,那么面对非奇异局势,先拿者必胜
;反之,则后拿者取胜。

那么任给一个局势(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=[a(√5-1)/2],若a=[j(1+√5)/2],那么a = aj,bj = aj + j,若不等于,那么a = aj+1,bj+1 = aj+1 + j + 1,若都不是,那么就不是奇异局势。然后再按照上述法则进行,一定会遇到奇异局势。

威佐夫博弈的几点判断:

非奇异局势时,先手一方只需要将当前局势变成奇异局势即可必胜

奇异局势时,后手一方只需要将非奇异局势变成奇异局势必胜

(三)尼姆博奕(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,39-27=12,所以从39中拿走12个物体即可达
到奇异局势(14,21,27)。

例2。(55,81,121),55(+)81=102,121-102=19,所以从121中拿走19个物品
就形成了奇异局势(55,81,102)。

例3。(29,45,58),29(+)45=48,58-48=10,从58中拿走10个,变为(29,4
5,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)奇异局势
    甲胜。

拓展

斐波那契博弈

1、问题模型:

有一堆个数为n的石子,游戏双方轮流取石子,满足:

(1)先手不能在第一次把所有的石子取完;

(2)之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间(包含1和对手刚取的石子数的2倍)。 约定取走最后一个石子的人为赢家。

2、解决思路:

当n为Fibonacci数时,先手必败。即存在先手的必败态当且仅当石头个数为Fibonacci数。

证明:根据“Zeckendorf定理”(齐肯多夫定理):任何正整数可以表示为若干个不连续的Fibonacci数之和。如n=83 = 55+21+5+2,我们看看这个分解有什么指导意义:假如先手取2颗,那么后手无法取5颗或更多,而5是一个Fibonacci数,那么一定是先手取走这5颗石子中的最后一颗,同理,接下去先手取走接下来的后21颗中的最后一颗,再取走后55颗中的最后一颗,那么先手赢。

反证:如果n是Fibonacci数,如n=89:记先手一开始所取的石子数为y

(1)若y>=34颗(也就是89的向前两项),那么一定后手赢,因为89-34=55=34+21<2*34。

(2)y<34时剩下的石子数x介于55到89之间,它一定不是一个Fibonacci数,把x分解成Fibonacci数:x=55+f[i]+…+f[j],若,如果f[j]<=2y,那么对B就是面临x局面的先手,所以根据之前的分析,后手只要先取f[j]个即可,以后再按之前的分析就可保证必胜。

公平组合博弈(Impartial Combinatori Games)

1、定义:

(1)两人参与。

(2)游戏局面的状态集合是有限。

(3)对于同一个局面,两个游戏者的可操作集合完全相同

(4)游戏者轮流进行游戏。

(5)当无法进行操作时游戏结束,此时不能进行操作的一方算输。

(6)无论游戏如何进行,总可以在有限步数之内结束。

2、模型:给定一个有向无环图和一个起始顶点上的一枚棋子,两名选手交替的将这枚棋子沿有向边进行移动,无法移动者判负。事实上,这个游戏可以认为是所有公平组合游戏(Impartial Combinatori Games)的抽象模型。其实,任何一个ICG都可以通过把每个局势看成一个顶点,对每个局势和它的子局势连一条有向边来抽象成这个“有向图游戏”。

3、解决思路:

现在,假定我们给出两个游戏G1 和 G2。如果我们只知道单个游戏的P-状态和N-状态我们能够正确地玩好游戏和G1 + G2吗?答案是否定的。不难看出两个P-状态的和总是P-状态,P-状态和N-状态的和总是N-状态。但是两个N-状态的和既可能是P-状态也可能是N-状态。因此,只知道单个游戏的P-状态和N-状态是不够的。

为了正确地玩好游戏和我们需要推广P-状态和N-状态,它就是Sprague-Grudy函数(或者简称为g函数)

4、Sprague-Grudy定理:

令N = {0, 1, 2, 3, …} 为自然数的集合。Sprague-Grundy 函数给游戏中的每个状态分配了一个自然数。结点v的Grundy值等于没有在v的后继的Grundy值中出现的最小自然数.

形式上:给定一个有限子集 S ⊂ N,令mex S(最小排斥值)为没有出现在S中的最小自然数。定义mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

对于一个给定的有向无环图,定义关于图的每个顶点的Sprague-Garundy函数g如下:g(x)=mex{ g(y) | y是x的后继 }。

5、性质:

(1)所有的终结点所对应的顶点,其SG值为0,因为它的后继集合是空集——所有终结点是必败点(P点)。

(2)对于一个g(x)=0的顶点x,它的所有后继y都满足g(y)!=0——无论如何操作,从必败点(P点)都只能进入必胜点(N点)//对手走完又只能把N留给我们。

(3)对于一个g(x)!=0的顶点,必定存在一个后继点y满足g(y)=0——从任何必胜点(N点)操作,至少有一种方法可以进入必败点(P点)//就是那种我们要走的方法。

6、应用:

(1)可选步数为1-m的连续整数,直接取模即可,SG(x) = x % (m+1);

(2)可选步数为任意步,SG(x) = x;

(3)可选步数为一系列不连续的数,用mex(计算每个节点的值)