思路讲解
看这数据量，直接暴搜或者状态压缩好吧
看来一眼题解，说是状态压缩？这分数比那道并查集分还低
好吧，题解也是状压dp，那暴搜大抵凉凉。
说白了，思路就是一个先手的人输赢取决于把一对合法牌去掉的情况下他是赢还是输，要是是赢，那这种状态就输了，要是输，那么这种状态就赢了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 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代码
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
| #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=20,MaxStatus=static_cast<ll> (1<<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);
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;
}
|
心路历程（WA，TLE，MLE……）
一次提交过了，当然，归功于样例比较强。
前面稍微调了一下是因为要加一下
都true了就不要再跑了，跑着跑着有可能又变成false了