ABC-380- F - Exchange Game · znzryb
## 思路讲解
[](https://www.notion.so/1654539447bd80d2948ee6440a8cd5a2)
好像和上面这道有点关系
[](https://www.notion.so/1664539447bd802eb625f7651f0bf3ff)
还是需要用到三进制状态压缩dp
0表示这张牌在A手里，1表示这张牌在B手里，2表示这张牌在C手里
然后问题就回到了怎么样状态转移了
答案是不用管怎么转移，暴搜（记忆化搜索）就完了
注意理解题意
## AC代码
```cpp
#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……）
注意，题目是说可以直接把自己的一张牌打出来，不用管桌子上的牌，只是拿牌只能拿桌子上大的牌