team2012-E1-mysol-0018

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
/* 解题报告 //

打麻将，给出手中的 13 张牌，问再来哪张牌就可以胡
此题的胡指的是 13 + 1 张牌构成 3 + 3 + 3 + 2 的形式
其中 3 是顺子或刻子而 2 是对子

做法是先枚举来哪种花色，将每种花色的牌数 mod 3 后
判断是否有三个 0 和一个 2，没有的话就跳过这种花色
如果有的话，就可以确定对子是哪种花色的了

然后枚举来的是哪张牌，再枚举对子是哪张
加入新拿到的牌并扣除对子后，对现在手上剩下的 12 张牌进行检验

检验的方式是：依次检查各个花色，每个花色从点数最小的牌开始
1. 若能构成刻子，则直接贪心地取出刻子
2. 若这个点数的牌还有剩余，则去试图构成顺子
3. 若试图构成顺子失败，则这 12 张牌不能胡

然后就搞定了

// By 猛犸也钻地 @ 2012.07.22 */
}}}

{{{
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

const char* t="mpsz";
int cnt[10][4];
int tmp[10][4];

int gao(){
    memcpy(tmp,cnt,sizeof(tmp));
    int c,x;
    for(c=0;c<4;c++) for(x=1;x<=9;x++){
        if(cnt[x][c]>=3) cnt[x][c]-=3;
        while(cnt[x][c]){
            if(c==3 || x>7 || !cnt[x+1][c] || !cnt[x+2][c]) goto ret;
            cnt[x+0][c]--;
            cnt[x+1][c]--;
            cnt[x+2][c]--;
        }
    }
    ret:
    memcpy(cnt,tmp,sizeof(cnt));
    return c==4;
}

int main(){
    char s[50];
    while(gets(s)){
        vector<int> ans;
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<13;i++){
            int c=strchr(t,s[i*2+1])-t;
            int x=s[i*2]-'0';
            cnt[x][c]++,cnt[0][c]++;
        }
        for(int c=0;c<4;cnt[0][c++]--){
            int u=0,sum[3]={};
            cnt[0][c]++;
            for(int i=0;i<4;i++) sum[cnt[0][i]%3]++;
            if(sum[0]!=3 || sum[2]!=1) continue;
            while(cnt[0][u]%3!=2) u++;
            for(int x=1;x<=9;x++) if(cnt[x][c]<4){
                cnt[x][c]++;
                for(int e=1;e<=9;e++){
                    cnt[e][u]-=2;
                    int ok=gao();
                    cnt[e][u]+=2;
                    if(ok) ans.push_back(c*10+x),e=10;
                }
                cnt[x][c]--;
            }
        }
        printf("%d",ans.size());
        if(ans.size()) putchar(' ');
        for(size_t i=0;i<ans.size();i++)
            printf("%d%c",ans[i]%10,t[ans[i]/10]);
        puts("");
    }
}
}}}

/* 解题报告 //
打麻将，给出手中的 13 张牌，问再来哪张牌就可以胡
此题的胡指的是 13 + 1 张牌构成 3 + 3 + 3 + 2 的形式
其中 3 是顺子或刻子而 2 是对子
做法是先枚举来哪种花色，将每种花色的牌数 mod 3 后
判断是否有三个 0 和一个 2，没有的话就跳过这种花色
如果有的话，就可以确定对子是哪种花色的了
然后枚举来的是哪张牌，再枚举对子是哪张
加入新拿到的牌并扣除对子后，对现在手上剩下的 12 张牌进行检验
检验的方式是：依次检查各个花色，每个花色从点数最小的牌开始
1. 若能构成刻子，则直接贪心地取出刻子
2. 若这个点数的牌还有剩余，则去试图构成顺子
3. 若试图构成顺子失败，则这 12 张牌不能胡
然后就搞定了
// By 猛犸也钻地 @ 2012.07.22 */

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const char* t="mpsz";
int cnt[10][4];
int tmp[10][4];
int gao(){
    memcpy(tmp,cnt,sizeof(tmp));
    int c,x;
    for(c=0;c<4;c++) for(x=1;x<=9;x++){
        if(cnt[x][c]>=3) cnt[x][c]-=3;
        while(cnt[x][c]){
            if(c==3 || x>7 || !cnt[x+1][c] || !cnt[x+2][c]) goto ret;
            cnt[x+0][c]--;
            cnt[x+1][c]--;
            cnt[x+2][c]--;
        }
    }
    ret:
    memcpy(cnt,tmp,sizeof(cnt));
    return c==4;
}
int main(){
    char s[50];
    while(gets(s)){
        vector<int> ans;
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<13;i++){
            int c=strchr(t,s[i*2+1])-t;
            int x=s[i*2]-'0';
            cnt[x][c]++,cnt[0][c]++;
        }
        for(int c=0;c<4;cnt[0][c++]--){
            int u=0,sum[3]={};
            cnt[0][c]++;
            for(int i=0;i<4;i++) sum[cnt[0][i]%3]++;
            if(sum[0]!=3 || sum[2]!=1) continue;
            while(cnt[0][u]%3!=2) u++;
            for(int x=1;x<=9;x++) if(cnt[x][c]<4){
                cnt[x][c]++;
                for(int e=1;e<=9;e++){
                    cnt[e][u]-=2;
                    int ok=gao();
                    cnt[e][u]+=2;
                    if(ok) ans.push_back(c*10+x),e=10;
                }
                cnt[x][c]--;
            }
        }
        printf("%d",ans.size());
        if(ans.size()) putchar(' ');
        for(size_t i=0;i<ans.size();i++)
            printf("%d%c",ans[i]%10,t[ans[i]/10]);
        puts("");
    }
}