比赛传送门
作者： fn

---

一点吐槽：这场好难。。。

基本题

F题 Longest Common Subsequence / “最长公共子序列”

题目大意
用 $x_{i+1}=(a{x}_i^2+b{x}_i+c)$ mod $p$ 构造一个长为 $2n$ 的序列，序列前 $n$ 个数字记为 $a$ ，后 $n$ 个数字记为 $b$ 。求 $a$ 和 $b$ 的最长公共子序列。

考察内容
思维，哈希

分析
此题和LCS的常见做法不同。

如果前后两段中出现了相同数字，那么后面的数字一定全一样。
预处理 $a$ 中每个数字的最早的出现位置。
遍历 $b$ ，对每个数字，如果能在 $a$ 中找到出现的最早位置，则更新答案。

复杂度 $O(n)$ 。

#include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=1e6+5;
ll a[N],b[N];

int main(){ // AC
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
		unordered_map<int,int> mp;
		
		ll n,m,p,x,a0,b0,c0;
		cin >> n >> m >> p >> x >> a0 >> b0 >> c0;
		for ( int i = 1; i <= n; i++ ){
			a[i] = (a0*x%p *x%p + b0*x%p + c0)%p;
			x = a[i];

			if(mp[a[i]]<=0){
				mp[a[i]]=i;
			}
		}
		
		ll ans=0;
		for ( int i = 1; i <= m; i++ ){
			b[i] = (a0*x%p *x%p + b0*x%p + c0)%p;
			x = b[i];
			int t1=mp[b[i]];
			if(t1>0){
				ans=max(ans, min(n-t1+1,m-i+1));
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}
/*
1
3 4 1024 0 0 0 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

---

进阶题

D题 Poker Game: Decision / 扑克游戏：决定

题目大意

两名玩家明牌玩德州扑克，一共52张牌。起始各两张牌，从6张公共牌中轮流取牌，牌面大的获胜。
双方都按照最优策略走，判断先手必胜、后手必胜还是必定平局。

$T(1\le T\le 10^5)$ 组数据。保证没有两张牌相同。

考察内容
dfs，模拟，博弈论

分析
不确定的牌数 $n=6$ ，考虑dfs。

每一步搜索时，如果存在让后面一个人必败的情况，则当前的人必胜。
否则，如果存在让平局的情况，则必定平局。
否则当前的人必败。

复杂度 $O(6!T)$ ，数据量大约在 $7\ast 10^7$ 左右，可以通过。

#include
using namespace std;
int a[10],b[10],p[10],q[10],suma[20],sumb[20],vis[10];
string sx[10],sy[10],sz[10];
int flush(int d[10])// 同花 
{
	if(d[1]==d[2]&&d[2]==d[3]&&d[3]==d[4]&&d[4]==d[5])	return 1;
	return 0; 
}
int straight(int d[10])// 顺子 
{
	if(d[1]==10&&d[2]==11&&d[3]==12&&d[4]==13&&d[5]==14)		return 2;//10 J Q K A
	if(d[2]-d[1]==1&&d[3]-d[2]==1&&d[4]-d[3]==1&&d[5]-d[4]==1)	return 1;
	if(d[1]==2&&d[2]==3&&d[3]==4&&d[4]==5&&d[5]==14)			return 1;//A 2 3 4 5
	return 0;
}
int four(int d[10])// 4张
{
	if(d[1]==d[2]&&d[2]==d[3]&&d[3]==d[4])	return 1;
	if(d[2]==d[3]&&d[3]==d[4]&&d[4]==d[5])	return 1;
	return 0;
}
int three(int d[10])// 3张
{
	if(d[1]==d[2]&&d[2]==d[3])	return 1;
	if(d[2]==d[3]&&d[3]==d[4])	return 1;
	if(d[3]==d[4]&&d[4]==d[5])	return 1;
	return 0;
}
int two(int d[10])// 2张
{
	if(d[1]==d[2])	return 1;
	if(d[2]==d[3])	return 1;
	if(d[3]==d[4])	return 1;
	if(d[4]==d[5])	return 1;
	return 0;
}
/*
牌型		rk()
皇家同花顺	10 
同花顺		9
4个			8
3带2		7
同花		6
普通顺子	5
3个			4 
两对		3
对子		2
散牌		1
*/
int rk(int c[10],int d[10])// c数值 d花色，判断牌面类型 
{
	if(flush(d)&&straight(c)==2)	return 10;
	if(flush(d)&&straight(c)==1)	return 9;
	if(four(c))		return 8;
	if((c[1]==c[2]&&c[3]==c[4]&&c[4]==c[5])||(c[1]==c[2]&&c[2]==c[3]&&c[4]==c[5]))	return 7;
	if(flush(d))	return 6;
	if(straight(c))	return 5;
	if(three(c))	return 4;
	if((c[1]==c[2]&&c[3]==c[4])||(c[1]==c[2]&&c[4]==c[5])||(c[2]==c[3]&&c[4]==c[5]))	return 3;
	if(two(c))		return 2;
	return 1;
}
bool cmpa(int x,int y){
	if(suma[x]!=suma[y])	return suma[x]>suma[y];
	return x>y;
}
bool cmpb(int x,int y){
	if(sumb[x]!=sumb[y])	return sumb[x]>sumb[y];
	return x>y;
}
int judge(){ // 比较牌面大小 
	sort(a+1,a+6);// 数值 
	sort(b+1,b+6);
	sort(p+1,p+6);// 花色 
	sort(q+1,q+6);
	int v1=rk(a,p);
	int v2=rk(b,q);
	if(v1>v2)	return 1;// win
	if(v1<v2)	return -1;// lose
	
	// v1==v2，说明牌面类型相同，此时继续判断大小 
	int aa[10],bb[10];
	memcpy(aa,a,sizeof(aa)); // 把a数组复制过来 
	memcpy(bb,b,sizeof(bb));
	memset(suma,0,sizeof(suma));
	memset(sumb,0,sizeof(sumb));
	if(straight(aa)&&aa[1]==2&&aa[2]==3&&aa[3]==4&&aa[4]==5&&aa[5]==14)	aa[5]=1;
	if(straight(bb)&&bb[1]==2&&bb[2]==3&&bb[3]==4&&bb[4]==5&&bb[5]==14)	bb[5]=1;
	for(int i=1;i<=5;i++){
		suma[aa[i]]++; // 统计个数 
		sumb[bb[i]]++; 
	}	
	sort(aa+1,aa+6,cmpa); // 按照个数最多的优先 否则按大小 
	sort(bb+1,bb+6,cmpb);
	for(int i=1;i<=5;i++){
		if(aa[i]>bb[i])	return 1;// win
		if(aa[i]<bb[i])	return -1;// lose
	}
	return 0;// draw
}
int dfs(int now){
	if(now>6){ // 递归边界 
		for(int i=1;i<=5;i++){ // 变成数字 
			if(sx[i][0]>='2'&&sx[i][0]<='9')	a[i]=sx[i][0]-'0';
			if(sx[i][0]=='A')	a[i]=14;
			if(sx[i][0]=='K')	a[i]=13;
			if(sx[i][0]=='Q')	a[i]=12;
			if(sx[i][0]=='J')	a[i]=11;
			if(sx[i][0]=='T')	a[i]=10;
			if(sy[i][0]>='2'&&sy[i][0]<='9')	b[i]=sy[i][0]-'0';
			if(sy[i][0]=='A')	b[i]=14;
			if(sy[i][0]=='K')	b[i]=13;
			if(sy[i][0]=='Q')	b[i]=12;
			if(sy[i][0]=='J')	b[i]=11;
			if(sy[i][0]=='T')	b[i]=10;
			if(sx[i][1]=='S')	p[i]=1;
			if(sx[i][1]=='H')	p[i]=2;
			if(sx[i][1]=='C')	p[i]=3;
			if(sx[i][1]=='D')	p[i]=4;
			if(sy[i][1]=='S')	q[i]=1;
			if(sy[i][1]=='H')	q[i]=2;
			if(sy[i][1]=='C')	q[i]=3;
			if(sy[i][1]=='D')	q[i]=4;
		}
		return judge(); // 比较牌面大小
	}
	
	int bj=0; // 记录是否可以平局 
	for(int i=1;i<=6;i++){
		if(vis[i]==0){
			vis[i]=1;
			if(now%2)	sx[now/2+3]=sz[i]; // 轮到先手，放到x里面 
			else		sy[now/2+2]=sz[i]; // 轮到后手，放到y里面
			int nxt=dfs(now+1); // 下一步的结果 
			vis[i]=0;
			if(nxt==-1)	return 1;// 当前是先手，存在让后面一个人必败的情况，则当前必胜 
			if(nxt==0)	bj=1; // 可以平局
		}
	}
	if(bj)	return 0;
	return -1;
}
void solve(){
	cin>>sx[1]>>sx[2]>>sy[1]>>sy[2];
	for(int i=1;i<=6;i++)	cin>>sz[i];
	
	memset(vis,0,sizeof(vis));
	int h=dfs(1);
	if(h==1)	cout<<"Alice"<<endl;	// 先手赢 
	if(h==-1)	cout<<"Bob"<<endl;		// 后手赢 
	if(h==0)	cout<<"Draw"<<endl;		// 平局 
}

int main(){
	int t;
	cin>>t;
	while(t){
		t--;
		solve();
	}
	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

---