NC17191. 爆搜题
描述
德克萨斯扑克是一种风靡全球的游戏，下面将介绍它的规则。
它由52张标准牌组成（除去鬼牌），有4种花色（黑桃，红心，方片和梅花），13种不同类型的牌A、K、Q、J、2、3、4、5、6、7、8、9、10。
游戏由两名玩家进行。一开始每一名玩家抽两张牌并将面朝下，称为底牌。底牌将不会公示出来直到比较阶段。接着主持人将会在剩下的牌中再抽出三张当做公共牌，也就是说，这三张牌是两名玩家都有所有权的。
之后主持人会在剩下来的牌中，再抽出两张牌，一共组成5张双方玩家都可以使用的牌。主持人在确定公共牌之后，扑克游戏进行比较环节。每个玩家展示自己的底牌，并且从7张牌（自己的底牌＋5张公共牌）中选出5张来成为自己的手牌（注意：公共牌双方都可以使用，也就是说可以允许某张公共牌同时成为两名玩家的手牌），根据组出来的手牌的强度来决定胜负。
下面是10种可能的手牌类型，从强到弱排序如下:
对于组成顺子而言，J、Q、K可以分别被看做11、12、13。A既可以被看做14，也可以看做1，也就是说A、K、Q、J、10是一个合法的顺子，5、4、3、2、A也是一个合法的顺子，但是3、2、A、K、Q不是一个合法的顺子。
玩家各自从自己手牌中挑出最强的手牌类型组，如果两名玩家挑出来都是同类型的手牌类型，那么将对该类型的手牌类型进行比较。特别地，比较方法如下:
特别注意：牌的花色不影响牌面大小的比较。
对于牌面的大小，顺序从大到小依次是A，K，Q，J，10，9，…，2。当A在顺子中被视为1的时候，A的大小位置被视为比2更小。
下面来举出一些例子来方便进行理解。
在世纪之交的x000年，M国最高的人W来到了Mr. F的王国，并进行了一次高水平的采访。这次采访的剪辑录像后来被收入了Mr. F的经典视频资料集中。
采访之余，W提出想和Mr. F进行一场公平的对决，于是选定了德州扑克这一游戏。Mr. F无所不知，在底牌和前三张公共牌已经抽出的时候，他已经知道了W的两张底牌是什么，而剩下的两张牌将随机从牌组中抽出。(也就是说，Mr. F已经知道了双方的底牌和三张公共牌的类型和花色)
Mr. F希望知道剩下两张牌随机抽出的情况下，他和W赌上了国家荣誉全力以赴比赛的情况下，Mr. F获胜的概率有多大。Mr. F认为平局意味着W能达到他的水平，这是他不能容忍的，所以他认为平局不算获胜。
输入描述
本题有多组测试数据，测试数据以一个#结束。
对于一张牌，用两个字符构成: 第一个字符为S、H、D、C的一种，分别表示黑桃、红心、方片、梅花。第二个字符为A、K、Q、J、T，和2到9的一种, 其中T代表10。
对于每一组测试数据，由三行组成:
第一行有两个字符串，表示Mr. F的两张底牌。
第二行有两个字符串，表示W的两张底牌。
第三行有三个字符串，表示已抽出的三张牌。
输出描述
每组数据输出一个实数，表示Mr. F获胜的概率，四舍五入到小数点后3位。
示例1
输入:
SA SK DA CA SQ SJ ST SA HA D2 C3 H4 S5 DA HA D9 H6 C9 H3 H4 H5 #
输出:
1.000 0.344 0.630
C++11(clang++ 3.9) 解法, 执行用时: 166ms, 内存消耗: 380K, 提交时间: 2018-07-13 20:33:17
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <numeric>
#define rank _rk
using namespace std;
const char *suit = "SHDC";
const char *rank = "A23456789TJQK"; // 0 to 12
const double eps = 1e-8;
bool c1[4][13], c2[4][13], c3[4][13], c[4][13];
pair<int, int> Read(void) {
char s[3];
scanf("%s", s);
if (s[0] == '#') exit(0);
int b = strchr(suit, s[0]) - suit;
int a = strchr(rank, s[1]) - rank;
return {b, a};
}
void Set(bool c[4][13]) {
pair<int, int> a = Read();
c[a.first][a.second] = 1;
}
int Hash(const int *a) {
int h = 0;
vector< pair<int, int> > b;
for (int i = 13; i > 0; --i) {
for (int j = 0; j < a[i % 13]; ++j) {
b.push_back({a[i % 13], i});
}
}
sort(b.begin(), b.end());
reverse(b.begin(), b.end());
for (auto p : b) {
int j = p.second;
h = h * 13 + j - 1;
}
return h;
}
pair<int, int> Score_(void) {
int a[13] = {};
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 13; ++j) {
a[j] += c[i][j];
}
}
if (accumulate(a, a + 13, 0) != 5) throw;
// tong hua shun
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 10; ++j) {
bool good = true;
for (int k = 0; k < 5; ++k) if (!c[i][(j + k) % 13]) good = false;
if (good) return {10, j};
}
}
// si tiao
if (count(a, a + 13, 4) == 1) {
return {9, Hash(a)};
}
// man tang hong
if (count(a, a + 13, 3) == 1 && count(a, a + 13, 2) == 1) {
return {8, Hash(a)};
}
// tong hua
for (int i = 0; i < 4; ++i) {
if (count(c[i], c[i] + 13, true) == 5) {
return {7, Hash(a)};
}
}
// shun zi
for (int j = 0; j < 10; ++j) {
bool good = true;
for (int k = 0; k < 5; ++k) if (!a[(j + k) % 13]) good = false;
if (good) return {6, j};
}
// san tiao
if (count(a, a + 13, 3) == 1) {
return {5, Hash(a)};
}
// shaung dui
if (count(a, a + 13, 2) == 2) {
return {4, Hash(a)};
}
// dui zi
if (count(a, a + 13, 2) == 1) {
return {3, Hash(a)};
}
// gao pai
return {2, Hash(a)};
}
pair<int, int> Score(const vector< pair<int, int> > &card) {
pair<int, int> ans = {0, 0};
for (int s = 0; s < 1 << 7; ++s) {
if (__builtin_popcount(s) == 5) {
memset(c, 0, sizeof c);
for (int i = 0; i < 7; ++i) {
if (s >> i & 1) {
c[card[i].first][card[i].second] = true;
}
}
ans = max(ans, Score_());
}
}
return ans;
}
bool Solve(int a1, int b1, int a2, int b2) {
vector< pair<int, int> > card;
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 13; ++j) {
if (c1[i][j] || c3[i][j] ||
(i == a1 && j == b1) || (i == a2 && j == b2)) {
card.push_back({i, j});
}
}
}
if (card.size() != 7) throw;
pair<int, int> p1 = Score(card);
card.clear();
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 13; ++j) {
if (c2[i][j] || c3[i][j] ||
(i == a1 && j == b1) || (i == a2 && j == b2)) {
card.push_back({i, j});
}
}
}
if (card.size() != 7) throw;
pair<int, int> p2 = Score(card);
return p1 > p2;
}
int main(void) {
while (true) {
memset(c1, 0, sizeof c1);
memset(c2, 0, sizeof c2);
memset(c3, 0, sizeof c3);
Set(c1); Set(c1);
Set(c2); Set(c2);
Set(c3); Set(c3); Set(c3);
int win = 0, tot = 0;
for (int i = 0; i < 52; ++i) {
for (int j = i + 1; j < 52; ++j) {
int a1 = i % 4, b1 = i / 4;
int a2 = j % 4, b2 = j / 4;
if (c1[a1][b1] || c1[a2][b2] || c2[a1][b1] || c2[a2][b2] ||
c3[a1][b1] || c3[a2][b2]) continue;
win += Solve(a1, b1, a2, b2);
tot += 1;
}
}
char s1[10], s2[10];
sprintf(s1, "%.3lf", (double)win / tot + eps);
sprintf(s2, "%.3lf", (double)win / tot - eps);
// if (strcmp(s1, s2)) while(1);
puts(s1);
}
return 0;
}