【2022牛客多校-8】D - Poker Game: Decision_2022 年牛客多校第八场

题意

Alice 和 Bob 玩修改版德州扑克，一人先拥有两张牌，有 6 张公共牌，所有牌都是明牌，Alice先手交替选择牌，直至人手五张牌，两人均使用最优策略。
先比较牌型，若一样则按牌型指定的规则排列牌后，比较牌的字典序。

思路

牌的数量很小，可以直接对抗搜索。
双方交替选牌，枚举 Alice 的操作，用 Bob 能做出的最好应对更新 Alice 当前操作的影响。Bob 同理，递归进行。
按题意模拟二人摸完牌后的胜负，注意牌应按照自大到小的顺序排列，且当 A2345 作为顺子出现时，A 应被视为 1。

代码

#include <stdio.h>
#include <algorithm>
using namespace std;
struct Card{
    int r,c;
}a[11],b[11],c[11],o;
char ch;
Card getCard()
{
	for (ch=getchar();(ch<'2'||ch>'9')&&ch!='T'&&ch!='J'&&ch!='Q'&&ch!='K'&&ch!='A';ch=getchar());
	if (ch>='2'&&ch<='9') o.r=ch-'0';
	else if (ch=='T') o.r=10;
	else if (ch=='J') o.r=11;
	else if (ch=='Q') o.r=12;
	else if (ch=='K') o.r=13;
	else o.r=14;
	for (ch=getchar();ch!='S'&&ch!='H'&&ch!='C'&&ch!='D';ch=getchar());
	if (ch=='S') o.c=1;
	if (ch=='H') o.c=2;
	if (ch=='C') o.c=3;
	if (ch=='D') o.c=4;
	return o;
}
int cmp(Card a,Card b)
{
    if (a.r!=b.r) return a.r>b.r;
    return a.c>b.c;
}
int type(Card t[])
{
    sort(t+1,t+1+5,cmp);
	int col=1;
	for (int i=1;i<=5;++i)
		if (t[i].c!=t[1].c) col=0;
	if (col)
	{
		if (t[5].r==10&&t[4].r==11&&t[3].r==12&&t[2].r==13&&t[1].r==14) return 10;
        if (t[5].r+1==t[4].r&&t[4].r+1==t[3].r&&t[3].r+1==t[2].r&&(t[2].r+1==t[1].r||(t[5].r==2&&t[1].r==14)))
		{
			if (t[1].r==14)
			{
				swap(t[1],t[2]);
				swap(t[2],t[3]);
				swap(t[3],t[4]);
				swap(t[4],t[5]);
				t[5].r=1;
			}
			return 9;
		}
        return 6;
	}
	
	if ((t[1].r==t[2].r||t[4].r==t[5].r)&&t[2].r==t[3].r&&t[3].r==t[4].r)
    {
    	if (t[4].r==t[5].r) swap(t[1],t[5]);
    	return 8;
	}
	
	if (t[1].r==t[2].r&&t[3].r==t[4].r&&t[5].r==t[4].r)
		swap(t[1],t[4]),swap(t[2],t[5]);
	if (t[4].r==t[5].r&&t[2].r==t[3].r&&t[3].r==t[1].r) return 7;
	
    if (t[5].r+1==t[4].r&&t[4].r+1==t[3].r&&t[3].r+1==t[2].r&&(t[2].r+1==t[1].r||(t[5].r==2&&t[1].r==14)))
		{
			if (t[1].r==14)
			{
				swap(t[1],t[2]);
				swap(t[2],t[3]);
				swap(t[3],t[4]);
				swap(t[4],t[5]);
				t[5].r=1;
			}
			return 5;
		}
    
	if (t[3].r==t[4].r&&t[2].r==t[4].r) swap(t[1],t[4]);
    if (t[3].r==t[4].r&&t[5].r==t[4].r) swap(t[1],t[4]),swap(t[2],t[5]);
	if (t[2].r==t[3].r&&t[3].r==t[1].r) return 4;
    
    if (t[1].r==t[2].r&&t[4].r==t[5].r) swap(t[3],t[5]);
    if (t[2].r==t[3].r&&t[4].r==t[5].r) swap(t[1],t[3]),swap(t[3],t[5]);
    if (t[1].r==t[2].r&&t[3].r==t[4].r) return 3;
    
    if (t[2].r==t[3].r) swap(t[1],t[3]);
    if (t[3].r==t[4].r) swap(t[1],t[3]),swap(t[2],t[4]);
    if (t[4].r==t[5].r) swap(t[2],t[4]),swap(t[3],t[5]),swap(t[3],t[1]);
    if (t[1].r==t[2].r) return 2;
    
    return 1;
}
int v[11],xn,yn;
Card x[11],y[11];
int Alice(int);
int Bob(int);
int tx,ty;
int qwq()
{
	for (int i=1;i<=5;++i) x[i]=a[i];
    for (int i=1;i<=5;++i) y[i]=b[i];
	tx=type(x);
	ty=type(y);
//	for (int i=1;i<=5;++i) printf("(%d,%d)",x[i].r,x[i].c);
//	printf("\n");
//	for (int i=1;i<=5;++i) printf("(%d,%d)",y[i].r,y[i].c);
//	printf("\n--------------------\n");
	if (tx>ty) return 1;
	if (tx<ty) return -1;
	for (int i=1;i<=5;++i)
	{
		if (x[i].r>y[i].r) return 1;
		if (x[i].r<y[i].r) return -1;
	}
	return 0;	
}
int Bob(int t)
{
	int flag=1;
	for (int i=1;i<=6;++i)
	{	
		if (v[i]) continue;
		v[i]=1;
		b[t+2]=c[i];
		flag=min(flag,Alice(t-1));
		v[i]=0;
		if (flag<0) return -1;
	}
	return flag;
}
int Alice(int t)
{
	if (t==0) return qwq();
	int flag=-1;
	for (int i=1;i<=6;++i)
	{	
		if (v[i]) continue;
		v[i]=1;
		a[t+2]=c[i];
		flag=max(flag,Bob(t));
		v[i]=0;
		if (flag>0) return 1;
	}
	return flag;
}
int check()
{
    for (int i=1;i<=2;++i) a[i]=getCard();
    for (int i=1;i<=2;++i) b[i]=getCard();
    for (int i=1;i<=6;++i)
	{
		v[i]=0;
		c[i]=getCard();
	}
    return Alice(3);
}
int main()
{
    int T;
    for (scanf("%d",&T);T--;)
    {
        int result=check();
        if (result==0) printf("Draw\n");
        else if (result>0) printf("Alice\n");
        else printf("Bob\n");
    }
    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