思路:
容易发现,我们取走一张牌后:
如果下一步的人必败,则这一步的人必胜,因为可以走这个状态。反之,这个人必败。
代码:
#include <bits/stdc++.h> using namespace std; int n, a[21], b[21], f[2000005]; int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i] >> b[i]; for (int S = 0; S <= ((1 << n) - 1); S++)//状压dp for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) if (!(S & (1 << i - 1))) if (!(S & (1 << j - 1)))//两张牌都没选才能 dp if (a[i] == a[j] || b[i] == b[j]) if (!f[S]) //如果当前状态的上一个状态为先手必败,那么可以转移,因为上次必败,那么这次先手必胜。 f[S | (1 << i - 1) | (1 << j - 1)]++; if (!f[(1 << n) - 1])//判断是否先手必胜 cout << "Aoki"; else cout << "Takahashi"; }
标签:Pairs,21,int,状压,Remove,tie,dp From: https://www.cnblogs.com/litianyu1969/p/18206908