team2012-F3-sol-0018

从 Trac 迁移的文章

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

原文章内容如下：

{{{
题意：给13张麻将牌，和winning hand组成的规则，问再得到什么牌就变成了winning hand
解法：模拟题，在34种牌中枚举得到的牌，再检查是否可以组成四个melds和eyes，注意每种牌最多4张。
}}}
{{{
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

vector<int> ans;
int num[100];
bool ok;

void dfs(int cnt)
{
    if(ok)  return;
    if(cnt == 4)
    {
        //eyes
        for(int i=1;i<=34;i++)
            if(num[i] >= 2)
                ok = 1;
        return;
    }
    //pong
    for(int i=1;i<=34;i++)
        if(num[i] >= 3)
        {
            num[i] -= 3;
            dfs(cnt + 1);
            num[i] += 3;
        }
    //kong
    for(int i=1;i<=34;i++)
        if(num[i] >= 4)
        {
            num[i] -= 4;
            dfs(cnt + 1);
            num[i] += 4;
        }
    //chow
    for(int i=1;i<=25;i++)
    {
        if(i==8 || i==9 || i==17 || i==18)
            continue;
        if(num[i] && num[i+1] && num[i+2])
        {
            num[i]--;
            num[i+1]--;
            num[i+2]--;
            dfs(cnt+1);
            num[i]++;
            num[i+1]++;
            num[i+2]++;
        }
    }
}

void output(int x)
{
    if(x <= 9)
        cout<<x<<'m';
    else if(x <= 18)
        cout<<x-9<<'p';
    else if(x <= 27)
        cout<<x-18<<'s';
    else
        cout<<x-27<<'z';
}

int main()
{
    string s;
    while(cin>>s)
    {
        memset(num, 0, sizeof(num));
        for(int i=1;i<s.size();i+=2)
        {
            int t;
            switch(s[i])
            {
                case 'm': t = s[i-1]-'0'; break;
                case 'p': t = s[i-1]-'0'+9; break;
                case 's': t = s[i-1]-'0'+18; break;
                case 'z': t = s[i-1]-'0'+27; break;
            }
            num[t]++;
        }

        ans.clear();
        for(int i=1;i<=34;i++)
            if(num[i] <= 3)
            {
                num[i]++;
                ok = 0;
                dfs(0);
                if(ok)
                    ans.push_back(i);
                num[i]--;
            }
        if(ans.size() == 0)
            cout<<0<<endl;
        else
        {
            cout<<ans.size()<<' ';
            for(int i=0;i<ans.size();i++)
                output(ans[i]);
            cout<<endl;
        }
    }
    return 0;
}
}}}

题意：给13张麻将牌，和winning hand组成的规则，问再得到什么牌就变成了winning hand
解法：模拟题，在34种牌中枚举得到的牌，再检查是否可以组成四个melds和eyes，注意每种牌最多4张。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
vector<int> ans;
int num[100];
bool ok;
void dfs(int cnt)
{
    if(ok)  return;
    if(cnt == 4)
    {
        //eyes
        for(int i=1;i<=34;i++)
            if(num[i] >= 2)
                ok = 1;
        return;
    }
    //pong
    for(int i=1;i<=34;i++)
        if(num[i] >= 3)
        {
            num[i] -= 3;
            dfs(cnt + 1);
            num[i] += 3;
        }
    //kong
    for(int i=1;i<=34;i++)
        if(num[i] >= 4)
        {
            num[i] -= 4;
            dfs(cnt + 1);
            num[i] += 4;
        }
    //chow
    for(int i=1;i<=25;i++)
    {
        if(i==8 || i==9 || i==17 || i==18)
            continue;
        if(num[i] && num[i+1] && num[i+2])
        {
            num[i]--;
            num[i+1]--;
            num[i+2]--;
            dfs(cnt+1);
            num[i]++;
            num[i+1]++;
            num[i+2]++;
        }
    }
}
void output(int x)
{
    if(x <= 9)
        cout<<x<<'m';
    else if(x <= 18)
        cout<<x-9<<'p';
    else if(x <= 27)
        cout<<x-18<<'s';
    else
        cout<<x-27<<'z';
}
int main()
{
    string s;
    while(cin>>s)
    {
        memset(num, 0, sizeof(num));
        for(int i=1;i<s.size();i+=2)
        {
            int t;
            switch(s[i])
            {
                case 'm': t = s[i-1]-'0'; break;
                case 'p': t = s[i-1]-'0'+9; break;
                case 's': t = s[i-1]-'0'+18; break;
                case 'z': t = s[i-1]-'0'+27; break;
            }
            num[t]++;
        }
        ans.clear();
        for(int i=1;i<=34;i++)
            if(num[i] <= 3)
            {
                num[i]++;
                ok = 0;
                dfs(0);
                if(ok)
                    ans.push_back(i);
                num[i]--;
            }
        if(ans.size() == 0)
            cout<<0<<endl;
        else
        {
            cout<<ans.size()<<' ';
            for(int i=0;i<ans.size();i++)
                output(ans[i]);
            cout<<endl;
        }
    }
    return 0;
}