Znzryb's Blog
0%

ABC-380- F - Exchange Game

Posted on Edited on

思路讲解

好像和上面这道有点关系

还是需要用到三进制状态压缩dp

0表示这张牌在A手里，1表示这张牌在B手里，2表示这张牌在C手里

然后问题就回到了怎么样状态转移了

答案是不用管怎么转移，暴搜（记忆化搜索）就完了

注意理解题意

AC代码

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>

using namespace std;
typedef long long ll;
const ll N=15,MaxSatus=600000;	// 3**12=531441
ll A[N];	// A为牌的权值
ll n,m,l;
ll digit[MaxSatus][N];
ll three[N];
int dp[MaxSatus][4];	// dp就是记忆化搜索里的缓存
ll initialStatus;
bool vis[MaxSatus][4];	// 表示走过
// 0 表示这张牌在桌子上，1表示这张牌在Takahashi手里
// 2表示在Aoki手里
// dp里存0就是指Takahashi输,反之则为他赢

void init(){
	three[0]=1;
	for(int i=1;i<=n+m+l;++i)
		three[i]=three[i-1]*3;
	for(int i=1;i<=three[n+m+l]-1;++i){
		ll temp=i;
		for(int j=0;j<=n+m+l;++j){
			digit[i][j]=temp%3;
			temp/=3;
		}
	}
	// 生成初始状态码（initialStatus）
	for(int i=0;i<n+m+l;++i){
		initialStatus*=3;
		if(i>=l && i<l+m)
			initialStatus+=2;
		else if(i>=m+l && i<m+n+l)
			initialStatus+=1;
	}
}
// who=1代表takahashi，who=2代表Aoki
// 然后就是要记忆化搜索，注意要记录此时是谁操作，因为有可能出现两个人手牌一样但是操作方不一样。
int dfs(int x,int who){
	if(vis[x][who])
		return dp[x][who];
	int res=0;	// res为这个状态是赢还是输
	for(int i=0;i<n+m+l;++i){
		// 模拟takahashi/Aoki换牌过程
		if(digit[x][i]!=who){
			continue;
		}
		// 模拟直接把i牌丢掉
		res=max(1-dfs(x-three[i]*who, 3-who),res);
		for(int j=0;j<n+m+l;++j){
			if(digit[x][j]!=0)
				continue;
			
			if(A[i]>A[j]){
				// 为什么要!dfs(x-three[i]*who, 3-who)？
				// 可以这么理解，返回的是你对手接下来是赢还是输，你对手输了，你自然就赢了
				// 如果对手赢了，你自然就输了
				// 当然，你输了,你的对手自然就赢了
				
				// 模拟拿这i牌换j牌
				res=max(1-dfs(x-three[i]*who+three[j]*who, 3-who),res);
			}
			if(res)
				break;
		}
		if(res)
			break;
	}
	dp[x][who]=res;
	vis[x][who]=true;
	return res;
}

//void out(){
//	for(int i=0;i<three[n+m+l];++i){
//		if(dp[i]){
//			for(int j=0;j<n+m+l;++j)
//				cout<<digit[i][j];
//			cout<<endl;
//		}
//	}
//}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>l;
	init();	// 初始化
	// 0-based
	for(int i=0;i<n+m+l;++i)
		cin>>A[i];
	bool ans=dfs(initialStatus,1);
	if(ans)
		cout<<"Takahashi"<<endl;
	else
		cout<<"Aoki"<<endl;
//	out();
}
// 暴搜
/*
AC https://atcoder.jp/contests/abc380/submissions/61130785
Takahashi and Aoki 
4 4 4
98 98765 987654 987654321
987 9876 9876543 98765432
123 12345 1234567 123456789

4 3 3
1233 1223 6767 5657
5657 5657 1
1212 2221 5656

1 0 0
0

*/

心路历程（WA，TLE，MLE……）

注意，题目是说可以直接把自己的一张牌打出来，不用管桌子上的牌，只是拿牌只能拿桌子上大的牌