P8836 [传智杯 #3 决赛] 打牌 题解

· · 题解

前言

当时写传智杯这道题的时候就是奔着写题解来的，但是一直没开，今天中午（2022-11-11 12:50）恰巧看见加入主题库了，便赶来写一写。

题意简述

模拟三个人按 1,2,3,1,2,3,1... 顺序出牌，每次每人出牌遵守恰好打出在自己所有可以打（即比上家大）的牌型中最小的牌，若无合法牌型可出，则本轮不出牌。

若有人出牌后，其余两人都不出牌（即要不起），则从该人开始开始下一轮，该人打出本人最小的牌型。

合法的牌型由 N 张点数相同的牌构成。

牌的大小决定与牌型的长度（len）和其中的点数（N）决定：

对于牌型 A 和 B，若 len_A>len_B，则 A 大，反之则 B 大。

特殊的，若 len_A=len_B 时，比较构成 A 和 B 的数字 N_A 和 N_B，若 N_A > N_B 时，则 A 大；若 N_A = N_B 时，则一样大；若 N_A < N_B 时，则 B 大。

算法简述

本题我们采用模拟算法。通过模拟每个人的出牌，出牌后检查其牌是否打光判断胜负。

具体实现请查阅代码。

可行性证明

模拟题就不说这个了吧。。。

时间复杂度及空间复杂度

时间复杂度：最坏 O(3n)

空间复杂度：O(nm)

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,ls,js,mjs;
int a[10][60];//a[第几个人][哪种牌]->有几张
int b[10];//统计每个人打了几张牌 用来判断获胜 
struct p{int x,n;/*x=牌型 n=数量*/}s,mins;//上家打的什么牌 不要为0 1
int main(){
    s.x=0;s.n=1;
    cin>>n>>m;
    for(int i=1;i<=3;i++){
        for(int j=0;j<n;j++){
            cin>>ls;
            a[i][ls]++;
        }
    }
    while(1){//控制每轮 
        for(int i=1;i<=3;i++){//模拟每个人 
            //cout<<i<<":";
            mins.x=INT_MAX;mins.n=INT_MAX;
            for(int j=1;j<=m;j++){//模拟打哪种 
                if(a[i][j]>s.n){//比上家牌多  
                    if(j<=s.x){
                        if(s.n+1<mins.n||(s.n+1==mins.n&&j<mins.x)){
                            mins.n=s.n+1;mins.x=j;
                        }
                    }
                    else{
                        if(s.n<mins.n||(s.n==mins.n&&j<mins.x)){
                            mins.n=s.n;mins.x=j;
                        }
                    }
                }
                if(a[i][j]==s.n&&j>s.x){//跟上家牌一样 但是我比他大 
                    if(s.n<mins.n||(s.n==mins.n&&j<mins.x)){
                        mins.n=s.n;mins.x=j;
                    }
                }
            }
            if(mins.x==INT_MAX){
                mjs++;
                //cout<<endl;
                if(mjs==2){
                    s.x=0;s.n=1;
                    mjs=0;
                }
                continue;
            }
            else mjs=0;
            //for(int j=0;j<mins.n;j++)cout<<mins.x;
            //cout<<endl;
            a[i][mins.x]-=mins.n;
            b[i]+=mins.n;
            s.x=mins.x;s.n=mins.n;
            if(b[i]==n){
                cout<<i;
                return 0;
            }

        }
    }
    return 0;
}

备注

这个代码是一年半之前写的，写的不好多多见谅，更新的代码会放在这里 Link，有任何疑问也欢迎发私信。