ABC-354- E - Remove Pairs · znzryb
## 思路讲解
看这数据量，直接暴搜或者状态压缩好吧
看来一眼题解，说是状态压缩？这分数比那道并查集分还低
好吧，题解也是状压dp，那暴搜大抵凉凉。
说白了，思路就是一个**先手的人输赢**取决于**把一对合法牌去掉的情况下他是赢还是输**，要是是赢，那这种状态就输了，要是输，那么这种状态就赢了
```cpp
for(int i=1;i<=(1<<n)-1;++i){
if(popcnt(i)<=1) // 只有一个牌自然是不可以的
continue;
for(int j=0;j<n;++j){
if(!((i>>j)&1))
continue;
for(int k=j+1;k<n;++k){
if(((i>>k)&1) && (A[j]==A[k] || B[j]==B[k])){
dp[i]=1-dp[i-(1<<k)-(1<<j)];
if(dp[i])
break;
}
}
if(dp[i])
break;
}
}
```
## 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>
// https://atcoder.jp/contests/abc354/tasks/abc354_e
using namespace std;
typedef long long ll;
const ll N=20,MaxStatus=static_cast<ll> (1<<20);//(2**20)
ll n,T;
ll A[N],B[N];
inline ll popcnt(ll x){
ll cnt=0;
for(cnt;x;++cnt){
x&=x-1;
}
return cnt;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=0;i<n;++i)
cin>>A[i]>>B[i];
vector<int> dp(MaxStatus,0); // 先全部初始化为takahashi输的
for(int i=1;i<=(1<<n)-1;++i){
if(popcnt(i)<=1) // 只有一个牌自然是不可以的
continue;
for(int j=0;j<n;++j){
if(!((i>>j)&1))
continue;
for(int k=j+1;k<n;++k){
if(((i>>k)&1) && (A[j]==A[k] || B[j]==B[k])){
dp[i]=1-dp[i-(1<<k)-(1<<j)];
if(dp[i])
break;
}
}
if(dp[i])
break;
}
}
cout<<(dp[(1<<n)-1] ? "Takahashi":"Aoki")<<endl;
return 0;
}
// AC https://atcoder.jp/contests/abc354/submissions/61042226
// AC https://www.luogu.com.cn/record/195869767
```
## 心路历程（WA，TLE，MLE……）
一次提交过了，当然，归功于样例比较强。
前面稍微调了一下是因为要加一下
```cpp
if(dp[i])
break;
```
都true了就不要再跑了，跑着跑着有可能又变成false了