某岛

… : "…アッカリ~ン . .. . " .. .
June 11, 2012

UESTC 1751. Harue’s Child Mahjong Club

Brief description:

。。麻将,不带碰不带吃不带杠,只带自摸。。
问都采取最优策略(开挂)时谁先获得胜利。。

Analysis:

由于什么都不带基本上就可以单机了,而且都开挂的话获胜条件只和所有可以摸到的麻将有关,也不用考虑弃牌。。
维护一个 Player 类。。。主要有 「摸!」和「和?」 两个功能。。

struct Player{
    int N[10], S[10], B[10];
    int EH, SH, WH, NH, rH, wH, gH;
    int pair;

    ...

    bool hu(){
        return pair >= 7 || all_crap() || std_hand();
    }

    void mo(){
        --wall; char a, b; scanf(" %c%c", &a, &b);

        switch (b){
            case 'N':if (++N[a-'0'] == 2) ++pair;break;
            case 'S':if (++S[a-'0'] == 2) ++pair;break;
            case 'B':if (++B[a-'0'] == 2) ++pair;break;
            default:
                switch (a){
                    case 'E':if (++EH == 2) ++pair;break;
                    case 'S':if (++SH == 2) ++pair;break;
                    case 'W':if (++WH == 2) ++pair;break;
                    case 'N':if (++NH == 2) ++pair;break;
                    case 'r':if (++rH == 2) ++pair;break;
                    case 'w':if (++wH == 2) ++pair;break;
                    default:if (++gH == 2) ++pair;
                }
        }
    }

} p[4];

对于判断胡牌的情况,先对两种特殊情况进行简单判断,然后考虑标准牌型。。
特殊处理「字牌」。(因为没有「吃」所以处理起来更容易一些。。)。
。然后对3种图案分开来处理,考虑到只考虑「吃」的话是很容易贪心构造的。
。。于是对满足「碰」的情况再枚举是否「碰」。(不会超过 4 组,否则上一轮已经得解了 。。)。
。。然后再最外围枚举由那类图案来提供「对」。。。

...
    bool std_hand(){

        F[0] = fh(), G[0] = gh();
        F[1] = f(N), F[2] = f(S), F[3] = f(B);
        G[1] = g(N), G[2] = g(S), G[3] = g(B);

        if (G[0] + F[1] + F[2] + F[3] >= 4) return true;
        if (F[0] + G[1] + F[2] + F[3] >= 4) return true;
        if (F[0] + F[1] + G[2] + F[3] >= 4) return true;
        if (F[0] + F[1] + F[2] + G[3] >= 4) return true;

        return false;
    }
...

总的复杂度似乎超级低。。。

#define LOCAL

/** ` Micro Mezzo Macro Flation -- Overheated Economy ., **/

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>

using namespace std;

#define REP(i, n) for (int i=0;i<int(n);++i)
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)
#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)
#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)
#define REP_C(i, n) for (int n____=int(n),i=0;i<n____;++i)
#define FOR_C(i, a, b) for (int b____=int(b),i=a;i<b____;++i)
#define DWN_C(i, b, a) for (int a____=int(a),i=b-1;i>=a____;--i)
#define REP_N(i, n) for (i=0;i<int(n);++i)
#define FOR_N(i, a, b) for (i=int(a);i<int(b);++i)
#define DWN_N(i, b, a) for (i=int(b-1);i>=int(a);--i)
#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)
#define FOR_1_C(i, a, b) for (int b____=int(b),i=a;i<=b____;++i)
#define DWN_1_C(i, b, a) for (int a____=int(a),i=b;i>=a____;--i)
#define REP_1_N(i, n) for (i=1;i<=int(n);++i)
#define FOR_1_N(i, a, b) for (i=int(a);i<=int(b);++i)
#define DWN_1_N(i, b, a) for (i=int(b);i>=int(a);--i)
#define REP_C_N(i, n) for (n____=int(n),i=0;i<n____;++i)
#define FOR_C_N(i, a, b) for (b____=int(b),i=a;i<b____;++i)
#define DWN_C_N(i, b, a) for (a____=int(a),i=b-1;i>=a____;--i)
#define REP_1_C_N(i, n) for (n____=int(n),i=1;i<=n____;++i)
#define FOR_1_C_N(i, a, b) for (b____=int(b),i=a;i<=b____;++i)
#define DWN_1_C_N(i, b, a) for (a____=int(a),i=b;i>=a____;--i)

#define ECH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)
#define DO(n) while(n--)
#define DO_C(n) int n_____ = n; while(n_____--)

#define ALL(A) A.begin(), A.end()
#define LLA(A) A.rbegin(), A.rend()
#define CPY(A, B) memcpy(A, B, sizeof(A))
#define INS(A, P, B) A.insert(A.begin() + P, B)
#define ERS(A, P) A.erase(A.begin() + P)
#define BSC(A, X) find(ALL(A), X) // != A.end()
#define CTN(T, x) (T.find(x) != T.end())
#define SZ(A) int(A.size())
#define PB push_back
#define MP(A, B) make_pair(A, B)

#define Rush int T____; RD(T____); DO(T____)
#pragma comment(linker, "/STACK:36777216")
//#pragma GCC optimize ("O2")
#define Ruby system("ruby main.rb")
#define Haskell system("runghc main.hs")
#define Pascal system("fpc main.pas")

typedef long long LL;
typedef double DB;

typedef vector<int> VI;

template<class T> inline void RD(T &);
template<class T> inline void OT(const T &);

inline int RD(){ int x; RD(x); return x;}
template<class T> inline T& _RD(T &x){ RD(x); return x;}
inline void RC(char &c){scanf(" %c", &c);}
inline void RS(char *s){scanf("%s", s);}

template<class T0, class T1> inline void RD(T0 &x0, T1 &x1){RD(x0), RD(x1);}

template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T0, class T1> inline void RST(T0 &A0, T1 &A1){RST(A0), RST(A1);}
template<class T0, class T1, class T2> inline void RST(T0 &A0, T1 &A1, T2 &A2){RST(A0), RST(A1), RST(A2);}


template<class T> inline void CLR(T &A){A.clear();}
template<class T0, class T1> inline void CLR(T0 &A0, T1 &A1){CLR(A0), CLR(A1);}
/** Add - On **/

const int MOD = 1000000007;
const int INF = 10009;
const DB EPS = 1e-2;
const DB OO = 1e15;
const DB PI = 3.14159265358979323846264; //M_PI;

// <<= ` 0. Daily Use .,

template<class T> inline void checkMin(T &a,const T b){if (b<a) a=b;}
template<class T> inline void checkMax(T &a,const T b){if (b>a) a=b;}
template <class T, class C> inline void checkMin(T& a, const T b, C c){if (c(b,a)) a = b;}
template <class T, class C> inline void checkMax(T& a, const T b, C c){if (c(a,b)) a = b;}
template<class T> inline T min(T a, T b, T c){return min(min(a, b), c);}
template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}
template<class T> inline T min(T a, T b, T c, T d){return min(min(a, b), min(c, d));}
template<class T> inline T max(T a, T b, T c, T d){return max(min(a, b), max(c, d));}
template<class T> inline T sqr(T a){return a*a;}
template<class T> inline T cub(T a){return a*a*a;}
int Ceil(int x, int y){return (x - 1) / y + 1;}

// <<= ` 1. Bitwise Operation .,
inline bool _1(int x, int i){return x & 1<<i;}
inline bool _1(LL x, int i){return x & 1LL<<i;}
inline LL _1(int i){return 1LL<<i;}
//inline int _1(int i){return 1<<i;}
inline LL _U(int i){return _1(i) - 1;};
//inline int _U(int i){return _1(i) - 1;};

inline int count_bits(int x){
    x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1);
    x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2);
    x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4);
    x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8);
    x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16);
    return x;
}

// <<= ' 0. I/O Accelerator interface .,

template<class T> inline void RD(T &x){
    //cin >> x;
    scanf("%d", &x);
    //char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c -
    //char c; c = getchar(); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';
}

template<class T> inline void OT(const T &p){
    printf("%.0lf\n", p);
}

/* .................................................................................................................................. */

const char name[4][129] = {"Takakamo Shizuno", "Atarashi Ako", "Matsumi Kuro", "Haramura Nodoka"};

int AA[10], wall;
int F[4], G[4];

struct Player{
    int N[10], S[10], B[10];
    int EH, SH, WH, NH, rH, wH, gH;
    int pair;

    void init(){
        RST(N, S, B), EH = SH = WH = NH = rH = wH = gH = 0, pair = 0;
    }

    bool all_crap(){
        if (!EH || !SH || !WH || !NH || !rH || !wH || !gH || !N[1] || !N[9] || !S[1] || !S[9] || !B[1] || !B[9]) return false;
        return EH>=2||SH>=2||WH>=2||NH>=2||rH>=2||wH>=2||gH>=2||N[1]>=2||N[9]>=2||S[1]>=2||S[9]>=2||B[1]>=2||B[9]>=2;
    }

    int fh(){
        return (EH>=3)+(SH>=3)+(WH>=3)+(NH>=3)+(rH>=3)+(wH>=3)+(gH>=3);
    }

    int gh(){
        if (EH==2||SH==2||WH==2||NH==2||rH==2||wH==2||gH==2) return fh();
        if (EH<2&&SH<2&&WH<2&&NH<2&&rH<2&&wH<2&&gH<2) return -INF;
        return fh() - 1;
    }


    int _f(int A[]){

        CPY(AA, A); int res = 0; REP_1(i, 7){
            if (AA[i]){
                int d = min(AA[i], AA[i+1], AA[i+2]);
                AA[i] -= d, AA[i+1] -= d, AA[i+2] -= d;
                res += d;
            }
        }

        return res;
    }

    int f(int A[]){
        int res = 0; VI L; REP_1(i, 9) if (A[i] >= 3) L.PB(i);
        REP(s, _1(SZ(L))){
            REP(i, SZ(L)) if (_1(s, i)) A[L[i]] -= 3;
            checkMax(res, _f(A) + count_bits(s));
            REP(i, SZ(L)) if (_1(s, i)) A[L[i]] += 3;
        }
        return res;
    }

    int g(int A[]){
        int res = -INF; REP_1(i, 9) if (A[i] >= 2) A[i] -= 2, checkMax(res, f(A)), A[i] += 2;
        return res;
    }

    bool std_hand(){

        F[0] = fh(), G[0] = gh();
        F[1] = f(N), F[2] = f(S), F[3] = f(B);
        G[1] = g(N), G[2] = g(S), G[3] = g(B);

        if (G[0] + F[1] + F[2] + F[3] >= 4) return true;
        if (F[0] + G[1] + F[2] + F[3] >= 4) return true;
        if (F[0] + F[1] + G[2] + F[3] >= 4) return true;
        if (F[0] + F[1] + F[2] + G[3] >= 4) return true;

        return false;
    }

    bool hu(){
        return pair >= 7 || all_crap() || std_hand();
    }

    void mo(){
        --wall; char a, b; scanf(" %c%c", &a, &b);

        switch (b){
            case 'N':if (++N[a-'0'] == 2) ++pair;break;
            case 'S':if (++S[a-'0'] == 2) ++pair;break;
            case 'B':if (++B[a-'0'] == 2) ++pair;break;
            default:
                switch (a){
                    case 'E':if (++EH == 2) ++pair;break;
                    case 'S':if (++SH == 2) ++pair;break;
                    case 'W':if (++WH == 2) ++pair;break;
                    case 'N':if (++NH == 2) ++pair;break;
                    case 'r':if (++rH == 2) ++pair;break;
                    case 'w':if (++wH == 2) ++pair;break;
                    default:if (++gH == 2) ++pair;
                }
        }
    }

} p[4];

void Run(){

    DO_C(3) REP(i, 4) p[i].mo(), p[i].mo(), p[i].mo(), p[i].mo();

    REP(i, 4) p[i].mo();

    REP_1(turn, 21){
        REP(i, 4){
            p[i].mo(); if (p[i].hu()){
                printf("%s wins at turn %d.", name[i], turn);
                return;
            }
        }
    }

    printf("a Draw Hand occurs.");
}


int main(){


#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //  freopen("out.txt", "w", stdout);
#endif


    REP_1_C(Case, RD()){
        REP(i, 4) p[i].init();
        printf("For round %d, ", Case);
        wall = 136; Run(); puts("");
        DO(wall){char a, b; scanf(" %c%c", &a, &b);}

    }
}

External link:

http://acm.uestc.edu.cn/problem.php?pid=1715
http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=28653
http://en.wikipedia.org/wiki/Mahjong