P7866 小昕昕题解

昒昕 · 2021-11-07 18:43:33 · 题解

更新了数据，卡掉了暴力做法，在此表示歉意。

做法 1

贪心+桶排，时间复杂度 \mathcal{O}(n)

对于一个牌点，一对“小昕昕”是优先把 牌最少的花色 配 牌最多的花色。

也就是对于某一牌点，优先拿 1 张牌的花色与 2 张牌的花色配对，如果没有 1 张牌的花色，才可以把 2 张牌的花色拆开。

所以就想到了桶排。

#include <cstdio>

int poke[6][21];
int ans;

int change_color(char p) {
    switch (p) {
        case 'S': return 1;
        case 'H': return 2;
        case 'C': return 3;
        case 'D': return 4;
    }
}
int change_num(char p) {
    switch (p) {
        case 'A': return 1;
        case 'T': return 10;
        case 'J': return 11;
        case 'Q': return 12;
        case 'K': return 13;
        default: return int(p-'0');
    }
}
int main() {
//  freopen("xinxin.in","r",stdin);
//  freopen("xinxin.out","w",stdout);
    int n;
    char c,num;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        scanf(" %c%c",&c,&num); //空格是为了吃前面的回车
        poke[change_color(c)][change_num(num)]++; //相应的牌个数加1
    }
    for (int i=1;i<=13;i++) //13个牌点
        for (int j=1;j<=4;j++) //4个花色
            for (int k=1;k<=4;k++)
                if (poke[j][i]==2&&poke[k][i]==1&&j!=k) { //正好是1-2的配对
                    poke[j][i]=0;
                    poke[k][i]=0;
                    ans++;
                }

    for (int i=1;i<=13;i++)
        for (int j=1;j<=4;j++)
            for (int k=1;k<=4;k++)
                if (poke[j][i]==2&&poke[k][i]!=0&&j!=k) { //如果这两个花色都是两张，那么只能拆其中一个花色，给另一个花色配
                    poke[j][i]=0;
                    poke[k][i]--;
                    ans++;
                }
    printf("%d\n",ans);
    return 0;
}

做法 2

桶排+找规律，时间复杂度 \mathcal{O}(n \log n)

想一想，一共有 2 副无大小王的扑克牌，说明每个花色至多有 2 张牌。

由于不同牌点间相互不影响，所以单从一个牌点考虑，并且无视花色。

如果该牌点如果共有 1 或 2 张牌，肯定无法组成“小昕昕”。
如果有 3 或 4 张牌，0 对或 1 对“小昕昕”都有可能，所以需要依靠花色判断。
如果有 5 张牌，只有 2-1-1-1 或 2-2-1-0 的情况，最多能配 1 对。
如果有 6 张牌，有 2-2-2 和 2-2-1-1 的情况，都是 2 对。
如果有 7 或 8 张牌，则分别是 2-2-2-1 和 2-2-2-2 的情况，2 对。

再来考虑 3 张牌，有 1-1-1-0 和 2-1-0-0 的情况，花色分别是 3 种和 2 种，如果花色有两种，就是 1 对小昕昕。

#include <bits/stdc++.h>
using namespace std;

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

int n,ans;
set <char> color[14];
int cnt[14]; //存储每个牌点的数量，无视花色

int main() {
//  freopen("xinxin.in","r",stdin);
//  freopen("xinxin.out","w",stdout);
    char a,b;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        scanf(" %c%c",&a,&b);
        int t=change_num(b);
        cnt[t]++; //该牌点的数量增加
        color[t].insert(a); //保存花色，以判断3张或4张牌的情况
    }
    for (int i=1;i<=13;i++) {
        if (cnt[i]==5) ans++; //5张1对
        else if (cnt[i]>=6) ans+=2; //6,7,8张2对
        else if (cnt[i]>=3&&cnt[i]<=4&&(int)color[i].size()!=cnt[i]) ans++;
        //如果是3,4张，则看总花色数
        //如果3张牌共有3个不同的花色 或 4张牌共有不同的4个花色，肯定不能组成“小昕昕”
    }
    printf("%d\n",ans);
   return 0;
}

P7866 小昕昕 题解

做法 1

做法 2

P7866 小昕昕题解