题解：AT_abc380_f [ABC380F] Exchange Game
coding_goat
2024-11-18 08:01:21
如果有一种操作使得之后的情况都可以转换为我胜，那么这就是我的必胜点，反之就是我的必败点。
注意是**可以**从桌上拿起一张牌，不是必须。
然后就是要记忆化搜索，注意要记录此时是谁操作，因为有可能出现两个人手牌一样但是操作方不一样。
```cpp
#include<bits/stdc++.h>
#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define inn(i,n,a) For(i,1,n) a[i]=read();
#define ll long long
#define i128 __int128
using namespace std;
inline int read() {
int xx= 0;int f= 1;
char c = getchar();
while(c<'0'||c>'9') {
if(c=='-') f= -1;
c= getchar();
}
while(c>='0'&&c<='9') {
xx= (xx<<1)+(xx<<3)+(c^48);
c= getchar();
}
return xx*f;
}
#define maxn 15
short f[2][(1<<12)+114][(1<<12)+514];
int a[maxn];
int n,m,l;
int out[maxn],top;
void put(int x) {
m0(out);
top=0;
while(x) out[++top]=x&1,x>>=1;
For(i,1,13) cout<<out[i];
puts("");
}
bool dfs(int dep,int s1,int s2) {
// cout<<dep<<'\n';put(s1); put(s2); puts("---");
bool res=0;
if(f[dep][s1][s2]!=-1) return f[dep][s1][s2];
if(dep&1) {
res=0;
For(i,0,n+m+l-1) {
if(!((s1>>i)&1)) continue;
if((s2>>i)&1) continue;
For(j,0,n+m+l-1) {
if(((s1|s2)>>j)&1) continue;
if(a[i+1]>a[j+1])
if(!dfs((dep^1),(s1^(1<<i))|(1<<j),s2)) res=1;
}
if(!dfs((dep^1),(s1^(1<<i)),s2)) res=1;
}
} else {
res=0;
For(i,0,n+m+l-1) {
if(!((s2>>i)&1)) continue;
if((s1>>i)&1) continue;
For(j,0,n+m+l-1) {
if(((s1|s2)>>j)&1) continue;
if(a[i+1]>a[j+1])
if(!dfs((dep^1),s1,(s2^(1<<i))|(1<<j))) res=1;
}
if(!dfs((dep^1),s1,(s2^(1<<i)))) res=1;
}
}
f[dep][s1][s2]=res;
return res;
}
signed main() {
mem(f,-1);
in3(n,m,l);
For(i,1,n+m+l) in1(a[i]);
cout<<(dfs(1,(1<<(n))-1,(1<<(m+n))-(1<<n))?"Takahashi":"Aoki");
}