D题: Poker Game: Decision

原题链接:https://ac.nowcoder.com/acm/contest/33193/D

题目大意

在德州扑克的大小比较规则情况下，发牌顺序与传统德扑不同。

初始发给Alice和Bob各两种手牌且双方均知道对方的手牌。牌桌上有 $6$ 张牌。双方轮流选取一张牌，直到各有 $5$ 张牌。Alice先手，牌组更大者获胜，求双方均采取最优策略的情况下，谁获胜。

德州扑克比较规则可参考:百度百科:德克萨斯扑克

题解

暴搜模拟然后基础博弈论转移即可，最麻烦的部分是大小比较。

关于牌型

不妨将同花和顺子(注意特判 $A2345$ )作为标记保存下来。
对于牌的点数可以保存入一个计数数组进行排序，方便知道第 $i$ 多的牌有多少张。

同牌型大小比较

1.皇家同花顺

只能是平局。

2.同花/高牌

排序后从大到小依次比较即可。

3.顺子/同花顺

首先特判最小的顺子 $A2345$ ，然后各自取最大的一张进行比较即可。

4.四张/葫芦/三张/两对/一对

不难发现这些牌型的比较都呈现 $41/32/311/221/2111$ 的先比较张数多的牌的规律。
不妨重新利用计数数组，以张数为第一关键字，点数为第二关键字进行排序，然后从大到小依次比较即可。

两个优化

1. 在搜索到必胜态时可以直接返回剪枝。
2. 考虑操作序列有 $6!$ 种，但是两个人得到牌的情况只有 $C_6^3$ 种，可以状压记忆化Alice选了哪些牌。

参考代码

#include
#define P pair<int,int>
using namespace std;

template<class T>inline void read(T&x){
	char c,last=' ';
	while(!isdigit(c=getchar()))last=c;
	x=c^48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+(c^48);
	if(last=='-')x=-x;
}

map<char,int>mp;
void init()//字符转点数/花色
{
	mp['A']=14;
	mp['K']=13;
	mp['Q']=12;
	mp['J']=11;
	mp['T']=10;
	mp['9']=9;
	mp['8']=8;
	mp['7']=7;
	mp['6']=6;
	mp['5']=5;
	mp['4']=4;
	mp['3']=3;
	mp['2']=2;
	mp['1']=1;
	
	mp['S']=1;
	mp['H']=2;
	mp['C']=3;
	mp['D']=4;
}

struct card{
	int num,suit;
};

bool cmp(const card&a,const card&b){return a.num>b.num;}//根据点数从大到小

struct cards{
	card c[5];
	void init(){
		sort(c,c+5,cmp);
	}
};

int type(cards a){//获得牌型
	a.init();
	vector<int>cnt(15);//计数数组
	int is_flush=1,is_straight=0;//标记:是否为同花/顺子
	for(int i=0;i<5;++i){
		if(i<4)is_flush&=a.c[i].suit==a.c[i+1].suit;
		++cnt[a.c[i].num];
	}
	sort(cnt.begin(),cnt.end(),greater<int>());
	if(a.c[0].num==14&&a.c[1].num==5&&a.c[2].num==4&&a.c[3].num==3&&a.c[4].num==2)is_straight=1;//特判A2345
	if(a.c[0].num==a.c[1].num+1&&a.c[1].num==a.c[2].num+1&&a.c[2].num==a.c[3].num+1&&a.c[3].num==a.c[4].num+1)is_straight=1;
	if(is_flush&&is_straight&&a.c[4].num==14)return 1;//皇家同花顺
	if(is_flush&&is_straight)return 2;//同花顺
	if(cnt[0]==4)return 3;//四张
	if(cnt[0]==3&&cnt[1]==2)return 4;//葫芦
	if(is_flush)return 5;//同花
	if(is_straight)return 6;//顺子
	if(cnt[0]==3)return 7;//三张
	if(cnt[0]==2&&cnt[1]==2)return 8;//两对
	if(cnt[0]==2)return 9;//一对
	return 10;//高牌
}

int cmp_royal(cards a,cards b){//皇家同花顺
	return 3;
}

int cmp_regular(cards a,cards b){//同花/高牌
	a.init(),b.init();
	for(int i=0;i<5;++i){
		if(a.c[i].num>b.c[i].num)return 1;
		if(b.c[i].num>a.c[i].num)return 2;
	}
	return 3;
}

int cmp_straight(cards a,cards b){//同花顺/顺子
	a.init(),b.init();
	int x=a.c[0].num==14&&a.c[4].num==2;//特判A2345是最小的顺子
	int y=b.c[0].num==14&&a.c[4].num==2;
	if(x&&y)return 3;
	if(x)return 2;
	if(y)return 1;
	x=a.c[0].num;
	y=b.c[0].num;
	if(x>y)return 1;
	if(y<x)return 2;
	return 3;
}

int cmp_groups(cards a,cards b){//葫芦/四张/三张/两对/一对
	vector<P>suma(15),sumb(15);//计数数组
	for(int i=2;i<=14;++i)suma[i].second=sumb[i].second=i;//以点数为第二关键字
	for(int i=0;i<5;++i)++suma[a.c[i].num].first,++sumb[b.c[i].num].first;//以牌数为第一关键字
	sort(suma.begin(),suma.end());//std::pair在比较时默认先比第一关键字,再比第二关键字
	sort(sumb.begin(),sumb.end());
	for(int i=14,p1=0,p2=0;i>=2;--i){//从大到小重新整牌
		while(suma[i].first)a.c[p1++].num=suma[i].second,--suma[i].first;
		while(sumb[i].first)b.c[p2++].num=sumb[i].second,--sumb[i].first;
	}
	for(int i=0;i<5;++i){//比较
		if(a.c[i].num>b.c[i].num)return 1;
		if(b.c[i].num>a.c[i].num)return 2;
	}
	return 3;
}

int cmp(cards a,cards b){//手牌比较
	int ta=type(a),tb=type(b);
//	cerr<
	if(ta<tb)return 1;
	if(tb<ta)return 2;
	if(ta==1)return cmp_royal(a,b);
	if(ta==5||ta==10)return cmp_regular(a,b);
	if(ta==2||ta==6)return cmp_straight(a,b);
	if(ta==3||ta==4||ta==7||ta==8||ta==9)return cmp_groups(a,b);
	return 3;//这句话不会被调用,只适用于通过编译防止报错
}

cards A,B;
card c[6];
int b[6];
int ans[100];//记忆化

void debug(){//调试:输出手牌
	for(int i=0;i<5;++i){
		cerr<<A.c[i].num<<' '<<A.c[i].suit<<"  ";
	}
	puts("");
	for(int i=0;i<5;++i){
		cerr<<B.c[i].num<<' '<<B.c[i].suit<<"  ";
	}
	puts("");
	puts("");
}

int dfs(int d,int p1,int p2,int bit){//bit为状压的Alice选取的牌
	if(d>6){
//		debug();
		if(ans[bit])return ans[bit];//已经算过了
		return ans[bit]=cmp(A,B);
	}
	if(d&1){
		int f=0;
		for(int i=0;i<6;++i){
			if(b[i])continue;
			A.c[p1]=c[i];
			b[i]=1;
			int res=dfs(d+1,p1+1,p2,bit|1<<i);
			b[i]=0;
			if(res==1)return 1;//剪枝,注意放在b[i]=0回溯之后
			f|=res==3;
		}
		return f?3:2;//能平则平
	}
	else{
		int f=0;
		for(int i=0;i<6;++i){
			if(b[i])continue;
			B.c[p2]=c[i];
			b[i]=1;
			int res=dfs(d+1,p1,p2+1,bit);
			b[i]=0;
			if(res==2)return 2;//剪枝
			f|=res==3;
		}
		return f?3:1;
	}
}

int main()
{
	init();
	int T;read(T);
	while(T--){
		memset(ans,0,sizeof(ans));//清空记忆化数组
		string s;
		for(int i=0;i<2;++i){
			cin>>s;
			A.c[i].num=mp[s[0]];
			A.c[i].suit=mp[s[1]];
		}
		for(int i=0;i<2;++i){
			cin>>s;
			B.c[i].num=mp[s[0]];
			B.c[i].suit=mp[s[1]];
		}
		for(int i=0;i<6;++i){
			cin>>s;
			c[i].num=mp[s[0]];
			c[i].suit=mp[s[1]];
		}
		int res=dfs(1,2,2,0);
		if(res==1)puts("Alice");
		if(res==2)puts("Bob");
		if(res==3)puts("Draw");
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208