算法竞赛进阶指南-30.占卜DIY

题目链接

算法竞赛进阶指南-30.占卜DIY

达达学会了使用扑克 DIY 占卜。

方法如下：

一副去掉大小王的扑克共 5252 张，打乱后均分为 1313 堆，编号 1∼131 \sim 13，每堆 44 张，其中第 1313 堆称作“生命牌”，也就是说你有 44 条命。

这里边，$ 4 $ 张 $ K $ 被称作死神。

初始状态下，所有的牌背面朝上扣下。

流程如下：

1.抽取生命牌中的最上面一张(第一张)。

2.把这张牌翻开，正面朝上，放到牌上的数字所对应编号的堆的最上边。(例如抽到 $ 2 $，正面朝上放到第 $ 2 $ 堆牌最上面，又比如抽到 $ J $，放到第 $ 11 $ 堆牌最上边，注意是正面朝上放)

3.从刚放了牌的那一堆最底下(最后一张)抽取一张牌，重复第 $ 2 $ 步。（例如你上次抽了 $ 2 $，放到了第二堆顶部，现在抽第二堆最后一张发现是 $ 8 $，又放到第 $ 8 $ 堆顶部…）

4.在抽牌过程中如果抽到 $ K $，则称死了一条命，就扔掉 $ K $ 再从第 $ 1 $ 步开始。

5.当发现四条命都死了以后，统计现在每堆牌上边正面朝上的牌的数目，只要同一数字的牌出现 $ 4 $ 张正面朝上的牌(比如 $ 4 $ 个 $ A $)，则称“开了一对”，当然 $ 4 $ 个 $ K $ 是不算的。

6.统计一共开了多少对，开了 $ 0 $ 对称作”极凶”，$ 1 \sim 2 $ 对为“大凶”，$ 3 $ 对为“凶”，$ 4 \sim 5 $ 对为“小凶”，$ 6 $ 对为“中庸”，$ 7 \sim 8 $ 对“小吉”，$ 9 $ 对为“吉”，$ 10 \sim 11 $ 为“大吉”，$ 12 $ 为“满堂开花，极吉”。

输入格式

一共输入 $ 13 $ 行数据，每行四个数字或字母，表示每堆牌的具体牌型(不区分花色只区分数字)，每堆输入的顺序为从上到下。

为了便于读入，用 $ 0 $ 代表 $ 10 $。

同行数字用空格隔开。

输出格式

输出一个整数，代表统计得到的开出的总对数。

输入样例：

8 5 A A
K 5 3 2
9 6 0 6
3 4 3 4
3 4 4 5
5 6 7 6
8 7 7 7
9 9 8 8
9 0 0 0
K J J J
Q A Q K
J Q 2 2
A K Q 2

输出样例：

9

Method : 模拟

理解了题意就很好做的一道模拟题。

这里使用的是数组 + 额外的两个idx模拟的抽取卡牌的过程，也可以使用双端队列来模拟抽取卡牌的过程。

吐槽: memset是真的难用，有时候会莫名其妙初始化不了

#include <vector>
#include <iostream>
#include <cstring>

using namespace std;

const int N = 13 + 7;
const int M = 4 + 7;

char poke[N][M];
vector<int> idx_top(N, 1); // 从上往下抽到第i张牌
vector<int> idx_bot(N, 4); // 从下往上抽到第i张牌
int cnt[N];      // 第i堆正面朝上的纸牌数
int life = 4;

int trans(char c) {
    switch(c) {
        case '0' :
            return 10;
        case 'J' :
            return 11;
        case 'Q' :
            return 12;
        case 'K' :
            return 13;
        case 'A' :
            return 1;
        default :
            return c - '0';
    }
}

int pick_top(int cur) {
    int pick = trans(poke[cur][idx_top[cur]]);
    idx_top[cur] ++;
    cnt[pick] ++;
    
    if (pick == 13) life --;
    return pick;
}

int pick_bot(int cur) {
    int pick = trans(poke[cur][idx_bot[cur]]);
    idx_bot[cur] --;
    cnt[pick] ++;
    
    if (pick == 13) life --;
    return pick;
}


int main() {
    memset(poke, '0', sizeof poke);
    memset(cnt, 0, sizeof cnt);
    
    for (int i = 1; i <= 13; i ++) {
        for (int j = 1; j <= 4; j ++) {
            // scanf("%c", &poke[i][j]);
            cin >> poke[i][j];
        }
    }
    
    int cur = 13;
    while (life != 0) {
        if (cur == 13) cur = pick_top(cur);
        else cur = (pick_bot(cur));
    }

    
    int res = 0;
    for (int i = 1; i <= 12; i ++) {
        if (cnt[i] == 4) {
            res ++;
        }
    }
    cout << res << endl;
    
    return 0;
}

复杂度分析

  • 时间复杂度：O(n∗m){O(n * m)}， 其中nn为13，m{m}为4。

  • 空间复杂度：O(n∗m){O(n * m)}， 其中nn为13，m{m}为4。