博弈論（取石子游戲）dp+分析

博弈論(取石子游戲)dp+分析題目描述給定一個有NN個節(jié)點的有向無環(huán)圖，圖中某些節(jié)點上有棋子，兩名玩家交替移動棋子。玩家每一步可將任意一顆棋子沿一條有向邊移動到另一個點，無法移動者輸?shù)粲螒?。對于給定的圖和棋子初始位置，雙方都會采取最優(yōu)的行動，詢問先手必勝還是先手必敗。輸入格式第一行，三個整數(shù)N,M,KN,M,K，NN表示圖中節(jié)點總數(shù)，MM表示圖中邊的條數(shù)，KK表示棋子的個數(shù)。接下來M行，每行兩個整數(shù)X,YX,Y表示有一條邊從點XX出發(fā)指向點YY。接下來一行，KK個空格間隔的整數(shù)，表示初始時，棋子所在的節(jié)點編號。節(jié)點編號從11到NN。輸出格式若先手勝，輸出win，否則輸出lose。數(shù)據(jù)范圍WNW2000,1WNW2000,WMW6000,1WMW6000,1WKWN1WKWN輸入樣例：684144154513561246輸出樣例：win這題咋沒人寫題解嘞qwqqwqSG函數(shù)首先定義mexmex函數(shù)，這是施加于一個集合的函數(shù)，返回最小的不屬于這個集合的非負(fù)整數(shù)例：mex({1,2})=0,mex({0,1})=2,mex({0,1,2,4})=3mex({1,2})=0,mex({0,1})=2,mex({0,1,2,4})=3在一張有向無環(huán)圖中，對于每個點uu，設(shè)其所有能到的點的SGSG函數(shù)值集合為集合AA，那么uu的SGSG函數(shù)值為mex(A)mex(A)，記做SG(u)=mex(A)SG(u)=mex(A)例圖：例圖解釋：SG(5)=mex({0})=0SG(5)=mex({0})=0SG(3)=mex({SG(5)})=mex({0})=1SG(3)=mex({SG(5)})=mex({0})=1SG(4)=mex({SG(5),SG(3)})=mex({0,1})=2SG(4)=mex({SG(5),SG(3)})=mex({0,1})=2SG(2)=mex({SG(3)}=mex({1})=0SG(2)=mex({SG(3)}=mex({1})=0SG(1)=mex({SG(2),SG(4)})=mex({0,2})=1SG(1)=mex({SG(2),SG(4)})=mex({0,2})=1那么SGSG函數(shù)的定義說完了，這題和SGSG函數(shù)又有什么關(guān)系呢？下面先說本題做法，再證明該方法正確性。做法：求出每個棋子所在的點的SGSG函數(shù)值，將所有值異或起來。若異或值不為00，則輸出win，否則輸出lose證明：首先，由于這是一張有向無環(huán)圖，所以游戲最后一定會結(jié)束，也就是說每個棋子最后都會移動到一個點上，且該點沒有任何能到達的點。那么根據(jù)定義，結(jié)束狀態(tài)的所有點的SGSG函數(shù)值異或起來為00,做法對于結(jié)束狀態(tài)可行。所以接下來，只要證明出任何一種每個棋子所在點的SGSG函數(shù)值異或起來非00的情況，一定能通過一次移動棋子，到達一個每個棋子所在點的SGSG函數(shù)值異或起來為00的情況任何一種每個棋子所在點的SGSG函數(shù)值異或起來為00的情況，一定不能通過一次移動棋子，到達一個每個棋子所在點的SGSG函數(shù)值異或起來為00的情況那么做法就是對的證明1:設(shè)每個棋子所在點的SGSG函數(shù)值分別為a1,a2,…,ana1,a2,…,an設(shè)x=a1XORa2XOR…XORanx=a1XORa2XOR…XORan,設(shè)xx的最高位為第kk位，那么在a1,a2,…,ana1,a2,…,an中，—定有一個值的第kk位為11設(shè)該值為aiai，那么由于xx的第kk位和aiai的第kk位都是11,且第kk位是xx的最高位，所以aiXORxaiXORx一定小于aiai又因為aiai是其中一個棋子所在點的SGSG函數(shù)值，那么根據(jù)SGSG函數(shù)值的定義，該點能到達的所有點中，一定存在一個點的SGSG函數(shù)值為aiXORxaiXORx那么我們就可以將該點上的棋子，移到一個SGSG函數(shù)值為aiXORxaiXORx的點上去移完之后，原來每個棋子所在點的SGSG函數(shù)異或值就變?yōu)榱薬1XORa2XOR???XORa-1XOR(aiXORx)XORai+1…XORana1XORa2XOR…XORai-1XOR(aiXORx)XORai+1…XORan二(a1XORa2XOR…XORan)XORx=xXORx=0=(a1XORa2XOR…XORan)XORx=xXORx=01證畢證明2：反證法，設(shè)將點uu上的棋子移動到點vv上后，每個棋子所在點的SGSG函數(shù)值仍然為00那就說明SG(u)=SG(v)SG(u)=SG(v),不符合SGSG函數(shù)的定義，不成立證畢所以做法是正確的。那么如何求出每個點的SGSG函數(shù)值呢？記憶化搜索就好啦?每層記憶化搜索中，如果該點的SGSG函數(shù)值已經(jīng)被計算出，那就直接返回該值。否則用一個setset記錄每個點能到的所有點的SGSG函數(shù)值集合，然后從00開始遍歷，找到第一個setset里面沒有的數(shù)，將該值記錄在該點上并返回。時間復(fù)雜度最壞情況下，每個點都會被遍歷一次，時間復(fù)雜度為O(n)O(n)。對于每個點，我們會將其所能到達的所有點扔到一個set中。而每個點能到達的點的數(shù)量，取決于從該點出發(fā)的邊的數(shù)量。所以總共我們會往set中插入mm次。但是對于每個set，我們至多只會往其中插入n-1個數(shù)。所以對于set的總復(fù)雜度為O(mlogn)O(mlocn)o那么本題的總時間復(fù)雜度即為O(n+mlogn)O(n+mlogn)。C++C++代碼include<iostream>include<algorithm>^include<cstring>include<cstdio>include<set>jsingnamespacestd;;onstintN=2005;;onstintM=6005;ntn,m,k;nth[N],e[M],ne[M],idx; //鄰接表存圖ntsg[N]; //存所有被計算過的點的SG函數(shù)值ntres;nlinevoidadd(intu,intv) //加邊函數(shù)。從點u向點v連一條有向邊e[++idx]=v;ne[idx]=h[u];h[u]=idx;ntSG(intu)if(~sg[u])returnsg[u]; 〃如果當(dāng)前sg[u]不是-1,那么說明該點的SG函數(shù)值已經(jīng)被計算過了，直接返回set<int>S; //否則要建一個集合S,存該點能到的所有點的SG函數(shù)值for(inti=h[u];i;i=ne[i])//遍歷點u能到達的所有點S.insert(SG(e[i]));for(inti=0;;i++)if(!S.count(i)){sg[u]=i;//計算該點的SGS.insert(SG(e[i]));for(inti=0;;i++)if(!S.count(i)){sg[u]=i;//從0開始枚舉所有非負(fù)整數(shù)//如果該值沒有在S中出現(xiàn)過//那么將該值記錄在sg[u]中并返回returni;ntmain()讀入題目中N,M,Kfor(inti=0;i<m;i++)//讀入M條邊并建圖{intu,v;add(u,v);}memset(sg,-1,sizeofsg);//先將sg數(shù)組中的所有值初始化成-1,表示沒有記錄過while(k--) //讀入K個棋子所在的點{intu;resA=SG(u);}如果res不為0,那么輸出win否則輸出losereturn0;簡單情況:所有堆的石子個數(shù)＞1＞1設(shè)b=堆數(shù)+石子總數(shù)-1b=堆數(shù)+石子總數(shù)-1先手必勝＜=＞bb是奇數(shù)對于任何一個奇數(shù)，一定存在一個偶數(shù)后繼對于任何一個偶數(shù),所有后繼必然是奇數(shù)又當(dāng)b=1b=1時，有b=1(堆數(shù))+1(石子總數(shù))-1=1b=1(堆數(shù))+1(石子總數(shù))-1=1則最終狀態(tài)一定是奇數(shù)證明思路：奇數(shù)出發(fā)(自己)-＞能到偶數(shù)(對手)-＞必回奇數(shù)(自己)-＞???-＞剩1(自己)-＞自己贏奇數(shù):堆數(shù)＞1＞1=＞合并兩堆(堆數(shù)-1)b-＞偶數(shù)堆數(shù)=1,＞3=1,＞3=＞取1石子(石子數(shù)-1)b-＞偶數(shù)即任何一個奇數(shù)狀態(tài)都可以轉(zhuǎn)移到某一個偶數(shù)狀態(tài)偶數(shù):堆數(shù)＞1＞1=＞合并兩堆(堆數(shù)-1)b-＞奇數(shù)取一子1該堆＞2＞2b-＞奇數(shù)2該堆=2=2b-＞奇數(shù)該堆剩12.1總共堆數(shù)=1=1則奇對手贏2.2總共堆數(shù)＞1＞1則奇對手一定在之后把這剩1的堆給合并假設(shè)剩兩堆22數(shù)的堆+奇數(shù)個數(shù)的堆(b=2+b=2+奇-1+2=1+2=偶)拿完后1+1+奇奇對手合并兩堆-＞最后只剩11堆偶數(shù)給偶對手(b=1+b=1+偶-1-1)一般情況:有堆的石子個數(shù)=1=1石子個數(shù)=1=1的堆個數(shù)=aabb其他個數(shù)(＞1)(＞1)的堆個數(shù)+其他堆石子總數(shù)-1-1f(a,b)=「H||||||||||f(a-1,b)，從a中取1個f(a,b-1)，從b中取1個f(a,b-1),合并b中2個f(a-2,b+3),合并a中2個(b堆石子數(shù)+2,堆數(shù)+1)f(a-1,b+1),合并a中1個b中1個(b堆石子數(shù)+1,a個數(shù)-1)f(a,b)=(f(a-1,b),從a中取1個f(a,b-1),從b中取1個f(a,b-1),合并b中2個f(a-2,b+3),合并a中2個(b堆石子數(shù)+2,堆數(shù)+1)f(a-1,b+1),合并a中1個b中1個(b堆石子數(shù)+1,a個數(shù)-1)#include<cstdio>#include<cstring>#include<iostream>usingnamespacestd;constintN=55,M=50050;intf[N][M];intdp(inta,intb){int&v=f[a][b];if(v!=-1)returnv;//簡單情況if(!a)returnv=b%2;//一般情況//上一次取完后b中只有1堆且只有1個石子b=1+1-1=1這堆并入a中if(b==1)returndp(a+1,0);//有a從a中取1個if(a&&!dp(a-1,b))returnv=1;//有b從b中取1個or合并b中2個if(b&&!dp(a,b-1))returnv=1;//合并a中2個if(a>=2&&!dp(a-2,b+(b?3:2)))returnv=1;//合并a中1個b中1個if(a&&b&&!dp(a-1,b+1))returnv=1;returnv=0;}intmain(){memset(f,-1,sizeoff);intT;cin>>T;while(T--){intn;cin>>n;inta=0,b=0;for(inti=0;i<n;i++){intx;cin>>x;if(x==1)a++;//b==0時加1堆+加x石子=0+1+x-1=x//b!=0時加1堆+加x石子=原來的+x+1elseb+=b?x+1:x;}}return0;在研究過Nim游戲及各種變種之后，Orez又發(fā)現(xiàn)了一種全新的取石子游戲，這個游戲是這樣的:有n堆石子，將這n堆石子擺成一排。游戲由兩個人進行，兩人輪流操作，每次操作者都可以從最左或最右的一堆中取出若干顆石子，可以將那一堆全部取掉，但不能不取，不能操作的人就輸了。Orez問：對于任意給出的一個初始局面，是否存在先手必勝策略。輸入格式第一行為一個整數(shù)T,表示有T組測試數(shù)據(jù)。對于每組測試數(shù)據(jù)，第一行為一個整數(shù)n,表示有n堆石子，第二行為n個整數(shù)ai,依次表示每堆石子的數(shù)目。輸出格式對于每組測試數(shù)據(jù)僅輸出一個整數(shù)0或1,占一行。其中1表示有先手必勝策略，0表示沒有。數(shù)據(jù)范圍1WTW10,1WnW1000,1WaiW109輸入樣例：14194輸出樣例：0假設(shè)當(dāng)前i?ji?j堆固定o[ij]oleft[i][j]left[i][j]表示我在左邊放多少個石子先手必敗left[i][j]left[i][j]必然存在且唯一唯一：反證：假設(shè)有兩個取值L1<L2L1<L2使得先手必敗當(dāng)左邊先放L2L2并先手拿完后剩L1L1個給對手的局面時自己就不是必敗了同理可以求一個right[i][j]right[i][j]表示我在右邊放多少個石子先手必敗最后答案：left[2][n]==a[1]left[2][n]==a[1]left[i][j]left[i][j]遞推[ij-1]第]堆（石子個數(shù)x）則我們希望求的是假設(shè)i~j已經(jīng)固定了，我們在左邊放多少個可以使得？[ij-1]第]堆是必敗的定義：左邊放LL時,L[ij-1]必敗右邊放RR時,[ij-1]R必敗情況1:R=xR=x[ij-1]xleft[i][j]=0left[i][j]=0情況2：x<L且x<Rx<L且x<Rx[ij-1]xleft[i][j]=xleft[i][j]=x不管先手怎么取必然在取完后某一此后某一邊剩0個石子，另一邊剩yy個石子0<yWx0<yWx0[ij-1]y此時由于x<L,x<Rx<L,x<R0<yWx0<yWxWy<L,y<Ry<L,y<R此時留給對手只有在左邊是LL或者右邊是RR的時候才是必敗,則此時對手必然不是必敗,則自己是必敗情況3:3.1L>RL>R則有R<xWLR<xWLx-1[ij-1]x此時右邊取xx左邊取x-1x-1left[i][j]=x-1left[i][j]=x-1時必敗先手取右邊首先先手一定不能把右邊取RR假設(shè)先手把右邊取RR后手把左邊取完則先手必敗如果先手把右邊取到x<Rx<R時，后手立即把左邊取到和右邊相同-轉(zhuǎn)化為情況2-先手必敗如果先手把右邊取到x>Rx>R時，后手立即把左邊取到比右邊少11的x-1x-1由于右邊>R>R則右邊xx最小取到11左邊xx最小取到00則必然會將右邊取到RR（情況1）或者RR以下（情況2）-必敗先手取左邊如果先手把左邊取到x>Rx>R時,后手就把右邊邊取到x+1x+1（情況3.1）如果先手把左邊取到x<Rx<R時,后手就把右邊邊取到xx（情況2）則只要左邊>R>R右邊>R+1>R+1后手保證左邊比右邊少一個（情況3）,一旦左邊或者右邊有一個<R<R，后手就保證左右兩邊一樣多（情況2）3.2R>LR>L則有LWx<RLWx<Rleft[i][j]=x+1left[i][j]=x+1先手必敗x+1[ij-1]x如果先手把左邊取到>L+1>L+1時,后手就把右邊邊取到>L>L后手永遠(yuǎn)保證左邊比右邊多11如果先手把左邊取到LL時，后手就把右邊取完，先手必敗如果先手把左邊或右邊取到<L<L,后手就保證左右兩邊一樣多，先手必敗后手保證左邊比右邊多一個（情況3.2）,一旦左邊或者右邊有一個<L<L,后手就保證左右兩邊一樣多（情況2）情況4x>L且x>Rx>L且x>Rleft[i][j]=xleft[i][j]=x意味著只要x>L且x>Rx>L且x>R左邊和右邊取一樣多就行4.1L>RL>R0時先手取完后〉L>L后手保證左右兩邊相同一旦先手把某一邊個數(shù)取到（R,L]（R,L]后手保證左邊比右邊少一個（情況3.1）一旦先手把某一邊個數(shù)取到[R,L）[R,L）后手保證右邊比左邊多一個一旦先手把某一邊個數(shù)取到（,R）（,R）后手保證右邊和左邊一樣多4.2R>LR>L時對稱先手取完后>R>R后手保證左右兩邊相同一旦先手把某一邊個數(shù)取到（L,R]（L,R]后手保證右邊比左邊少一個（情況3.2）一旦先手把某一邊個數(shù)取到[L,R）[L,R）后手保證左邊比右邊多一個一旦先手把某一邊個數(shù)取到（,L）（,L）后手保證右邊和左邊一樣多#include<iostream>#include<cstring>usingnamespacestd;constintN=1010;intn;inta[N];intl[N][N],r[N][N];int