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
