P9876 [EC Final 2021] Prof. Pang and Poker

· · 题解

题目链接：Luogu

题意

（竟然是卢本伟的翻译

题面意思其实就是三人打一种花色不计、只出单牌的斗地主。牌面数字或字母从小到大依次为 2,3,4,5,6,7,8,9,\texttt{T},\texttt{J},\texttt{Q},\texttt{K},\texttt{A}。现在 Prof.Pang（也就是题面中的卢本伟，后称 P）、Alice（即题面中的舒克，后称 A）、Bob（即题面中的贝塔，后称 B）三人打牌，A 和 P 希望 P 赢，B 希望 A 或 B 赢，现在给出每个人手上的牌，问绝顶聪明时（最优策略时） P 能否赢。

思路

分类讨论（只有这么大的分类讨论才可能评蓝吧）。

我们现将 \texttt{T},\texttt{J},\texttt{Q},\texttt{K},\texttt{A} 对应为 10,11,12,13,14，且设 n 为 A 手中的牌数，m 为 B 手中的牌数，A[i] 是 A 第 i 大的手牌，B[i] 是 B 第 i 大的手牌，B_{Smaller} 表示 B 比 P 小的牌数，A_{No} 表示 A 比 P 大的牌，A_{Max} 表示 A 比 P 小的牌中最大的那一张。

  1. 当 A 手里只剩一张牌时（即 n=1 时），那么 A 一出牌游戏就会结束，P 不可能胜利；

  2. 当 A 手里剩的牌都比 P 的大时（即 A_{No}=n 时），那么 A 不论怎么出 P 都不可能出掉手里的牌，P 不可能胜利；

  3. 当 B 手里的牌有至少 2 张比 P 的牌小时（即 B_{Smaller} \ge 2 时），那么他出牌时一定会有一次出牌使得 P 手上的牌能够出掉，P 一定胜利；

  4. 当 B 手里的牌全部比 P 手上的牌大时（即 B_{Smaller} = 0 时），那么 A 怎么出都会被 B 出的牌压住，使得 P 无法出掉手中的牌，P 不可能胜利；

  5. 当 B 只剩一张牌时（即 m=1 时）：

    1.如果 A 有比 B 大的牌，但比 P 小的牌（即 A_{Max}\ge B[1] 时），那么只要 A 出那张比 B 大的牌，但比 P 小的牌，就可以让 P 出完牌，P 一定胜利；

    2.如果 A 没有比 B 大的牌，但比 P 小的牌（即 A_{Max}< B[1] 时），那么 A 出大于等于 P 的牌 P 出不出去，出小于 P 的牌又会让 B 出完，P 不可能胜利；

  6. 如果 A 只有一张牌比 P 小（即 A_{No}=n-1 时），那么 A 出大于等于 P 的牌 P 出不出去，出小于 P 的牌又会被 B 压住，P 不可能胜利；

  7. 当 A 的最大牌大于 B 的最大牌，A 比 P 小的牌中最大的那一张牌大于等于 B 最小的那一张牌，同时 A 至少有 4 张牌时（即 A[n]>B[m] 且 A_{Max} \ge B[1] 且 n \ge 4 时），A 只要出一张 A[1]，这时 B 就要用大牌压住A 来不让 P 出完。之后 A 和 P 等到 B 出掉所有大牌，A 再出 A[n] 压住 B，这时 A 再出 A_{Max}，而 B 并没有更大的牌，P 就可以出完，P 一定能赢。

  8. 其余情况，P 都不可能赢。

Code:

#include<bits/stdc++.h>
#define M 114514
using namespace std;
int T,n,m,Shook[M],Beta[M],LBW;
string Pokers;
int Poker_to_Number(char ch)
{
    switch(ch)
    {
        case 'T':return 10;
        case 'J':return 11;
        case 'Q':return 12;
        case 'K':return 13;
        case 'A':return 14;
        default:return ch-'0';
    }
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)cin>>Pokers,Shook[i]=Poker_to_Number(Pokers[0]);
        sort(Shook+1,Shook+n+1); 
        for(int i=1;i<=m;i++)cin>>Pokers,Beta[i]=Poker_to_Number(Pokers[0]);
        sort(Beta+1,Beta+m+1);
        cin>>Pokers,LBW=Poker_to_Number(Pokers[0]);
        int Beta_Smaller=0,Shook_Max=0,Shook_No_Use=0;
        for(int i=1;i<=m;i++)Beta_Smaller+=(Beta[i]<LBW?1:0);
        for(int i=1;i<=n;i++)
        {
            if(Shook[i]>=LBW)Shook_No_Use++;
            else Shook_Max=max(Shook_Max,Shook[i]);
        }
        if(n==1)//case 1:当舒克手里只剩一张牌时，他一出游戏就结束，卢本伟不可能胜利。 
        {
            printf("Shou\n");continue;
        }
        if(Shook_No_Use==n)//case 2:当舒克手里剩的牌都比卢本伟的大时，他怎么出卢本伟都不可能出掉手里的牌。 
        {
            printf("Shou\n");continue;
        }
        if(Beta_Smaller>=2)//case 3:当贝塔手里的牌有至少2张比卢本伟的牌小时，那么他出牌时一定会有一次出牌使得卢本伟手上的牌能够出掉 
        {
            printf("Pang\n");continue;
        }
        if(Beta_Smaller==0)//case 4:当贝塔手里的牌全部比卢本伟手上的牌大时，那么舒克怎么出都会被贝塔出的牌压住，使得卢本伟无法出牌 
        {
            printf("Shou\n");continue;
        }
        if(m==1)
        {
            if(Shook_Max>=Beta[1])//case 5.1:当贝塔只剩一张牌时，如果舒克有比贝塔大的牌，但比卢本伟小的牌，那么卢本伟能出完 
            {
                printf("Pang\n");continue;
            }
            else//case 5.2:否则贝塔一定比卢本伟先出完 
            {
                printf("Shou\n");continue;
            }
        }
        if(n-Shook_No_Use==1)//case 6:如果舒克只有一张牌比卢本伟小，那么他会先出较大的牌来防止贝塔出完，使得卢本伟比舒克晚出完 
        {
            printf("Shou\n");continue;
        }
        //case 7:就是舒克用小牌先钓出贝塔的打牌，后等到贝塔手中牌均比卢本伟小时，舒克压住贝塔，再打一张大于贝塔手中牌且小于卢本伟手中的牌 
        if(Beta[m]>=Shook[n])
        {
            printf("Shou\n");continue;
        }
        if(Shook_Max>=Beta[1]&&n>3)
        {
            printf("Pang\n");continue;
        }
        else//case 8:其余情况 
        {
            printf("Shou\n");continue;
        }
    }
}