題目鏈接：Problem - E - Codeforces

題目意思：有三個人玩游戲，Alice，Bob，還有Prof. Pang。Alice和Bob分別有n，m張撲克，Pang只有一張，出牌順序是Alice，Bob，Pang，Alice。類似斗地主一樣的規(guī)則，但是不同的是，每次只能出一張牌。Alice想要Pang出完手里的牌（送牌讓他走），Bob想要阻止。當(dāng)且僅當(dāng)Pang出完手里的唯一的牌，他會開心。

我們可以得知題目的規(guī)則類似斗地主，假設(shè)我們是Alice，那么我們就要想辦法送牌給Pang，讓Pang走完手中的牌，又或者通過一些手段，讓Bob出牌，送給Pang。

對于博弈論的題，我們可以先分析，哪些情況是必勝的（這里我定義Alice必定能讓Pang出完手里的牌是必勝的）。遇到這樣的題目，我們不能一上來就憑感覺狂寫一通，不能想到什么就寫什么，因為這樣很容易漏掉條件，我們最好按照某種特定的條件，不斷分類，讓自己所分類的條件，可以涵蓋所有的可能情況。

首先，如果你是Alice，你想要Pang走完自己的牌。我們可以先看兩個大前提的條件。

那么如果Alice的牌數(shù)n = 1，必輸。因為Alice先手，走完這張牌，游戲就結(jié)束了

如果Alice所有的牌，都 >= Pang的牌，必輸。因為你出的牌，Pang根本要不起，那么Bob就可以一直不接你的牌，直到你把自己的牌走完，游戲結(jié)束。

除此之外有一點很好發(fā)現(xiàn)的特點，那就是，帶入Bob，如果Bob手里小于Pang的牌很多，那么Bob就沒辦法走完全部的牌，如果平時玩過斗地主，這個特點非常容易發(fā)現(xiàn)。

那么，我們就可以對Bob手里小于Pang的牌的數(shù)量進行分類。我們假設(shè)，Bob手里小于Pang的牌的個數(shù)為x。那么：

若x>=2，Bob必輸。

因為，在除去之前的兩個Alice必敗條件，Alice至少有兩張牌，而且至少一張小于Pang的牌。那么Alice只需要開局打出小于Pang的那張牌。如果Bob不壓我們，Pang就會打出自己的牌，我們贏。所以Bob必須要壓我們，但如果他壓了我們，我們可以選擇不出牌，后面無論Bob出什么，我們都不要，讓Bob一直出牌，直到Bob打出了一張小于pang的牌，我們勝利。所以綜上，無論怎么樣，如果Bob手里小于pang的牌至少有兩張，那么我們必贏，bob必輸。

若x=0，Bob必勝。

如果Bob手里的牌，都是大于等于pang的，那么我們出牌，只要是小于pang的牌，Bob就選擇壓我們，一直出，就一直壓。到最后，要么Bob打完了手里所有的牌，要么Alice打完了所有能送pang贏的牌，所以，無論如何，都是Bob贏。

接下來，就剩最后一個大類了，也是最容易出錯的一類。

當(dāng)x=1的時候。

首先，我們先判斷一個特殊情況：

如果Bob只有一張牌，且Alice的那張小牌 >= Bob手中的牌，Bob必輸，否則Bob必勝。因為Alice只要出那張牌，Bob的牌出不了，也就是Bob不能跑完全部的牌，也就只能眼睜睜看著Alice的那張牌送到pang的手里，然后pang出牌，游戲結(jié)束。但如果Alice手里小于pang的那種牌，比Bob的手里的牌還小，那么Bob還是贏的，因為只要Alice出了那張牌，Bob會趕在pang能出牌之前，把自己手里唯一的牌打出去，游戲結(jié)束。

此后，我們再判斷Alice手中的牌

若Alice < pang 的牌的數(shù)量 = 1，Bob必勝

因為只要Alice出手了這唯一一張能讓pang贏的牌，那么Bob就可以壓制Alice的那張牌，滅了他唯一的希望，此后，Bob就可以隨意出，只要把小于pang的牌留到最后一手，然后走掉，結(jié)束游戲。那如果Alice選擇接手，但這時候Alice手里的牌都是大于等于pang的，那么Alice又回到了最開始我們說的必輸?shù)木置妗Ｋ赃@種情況下，Bob怎么樣都是贏的。

若Alice < pang 的牌的數(shù)量 >= 2：

如果Alice最大的牌 > Bob最大的牌，并且Alice存在一張牌 < pang 并且 >= Bob手中的小牌，同時Alice的牌還要多余3張，Bob必輸?，否則Bob必勝。因為Alice只要出一張最小的牌，Bob必須阻攔 ，之后Alice一直不接牌，讓Bob一直出牌，直到Bob剩下出完倒數(shù)第二張牌，也就是最后一個 > pang的牌，這時候Alice再出手，壓住Bob，然后再出一張Bob要不起，但是pang要得起的小牌，讓pang贏。之所以Alice的牌要 > 3張，是因為除去開局出的小牌，手里最大的牌，以及之后送給pang的牌，還要有多余的牌在手里，不然的話，打出送給pang的牌，自己手里沒牌，游戲就結(jié)束了（這點很容易錯）

最后附上AC代碼

#include<bits/stdc++.h> #define ll int #define LL long long #define L(i,j,k) for(ll i=j;i<=k;++i) #define R(i,j,k) for(ll i=j;i>=k;--i) using namespace std; const ll N=5e3+10,mod=1e9+7;ll n,m,k,p,t,x,y,z,c; LL ans; ll a[60],b[60]; char sa[60][5],sb[60][5],sc[5];ll cal(char ch){if(ch=='A')return 14;else if(ch=='K')return 13;else if(ch=='Q')return 12;else if(ch=='J')return 11;else if(ch=='T')return 10;else return (ch-'0'); }void solve(){scanf("%d%d",&n,&m);L(i,1,n)scanf("%s",sa[i]),a[i]=cal(sa[i][0]);L(i,1,m)scanf("%s",sb[i]),b[i]=cal(sb[i][0]);sort(a+1,a+n+1);sort(b+1,b+m+1);scanf("%s",sc);c=cal(sc[0]);int am,bm,amax,bmax;am=bm=amax=bmax=0;int a_maxmin=0;int ada=0;for(int i=1;i<=m;i++) //求出bob小于c的個數(shù){if(b[i]<c){bm++;}}for(int i=1;i<=n;i++) //alice大于等于c的個數(shù){if(a[i]>=c){ada++;}else{if(a[i]>a_maxmin) //最大的小于C的數(shù)字{a_maxmin=a[i];}}}int flag=1;if(n==1||ada==n){printf("Shou\n");return ;}if(bm>=2){printf("Pang\n");return;}else if(bm==0){printf("Shou\n");return ;}else{if(m==1) //B大為0 也就是沒有大于等于c的牌{if(a_maxmin>=b[1]) ///存在大于等于m且 小于C{printf("Pang\n");return ;}else{printf("Shou\n");return ;}}if((n-ada)==1) //a小為1{printf("Shou\n"); return ;}else ///A小大于等于2個{if(b[m]>=a[n]) //有牌權(quán){printf("Shou\n");return ;}else{if(a_maxmin>=b[1]&&n>3){printf("Pang\n");}else{printf("Shou\n");}}}} }int main(){ll cas=1;scanf("%d",&cas);while(cas--)solve(); }

總結(jié)

以上是生活随笔為你收集整理的2021EC-final博弈论E题Prof. Pang and Poker的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。