前言
博弈论,状压,记忆化搜索。
思路
看到很小的 \(n\),容易联想到状压、搜索。本题就是状压加搜索。
设状态 \(x\) 的每一位表示:如果第 \(i\) 位是 \(0\),则当前数没有被选过。否则已经选过了。
每次 dfs 的时候,记录当前状态,以及上一次选的字符串。
如果有一种情况能使对手必败,那么我们就必胜。如果所有情况都是对手胜,那么我们必败。
注意要记忆话,否则会被卡到 \(O(n!)\) 然后 TLE 几个点。
代码
省去了大段的缺省源。
const int N = 17;
int n;
string a[N];
bool vis[1 << N][N], ans[1 << N][N]; //vis 是看 ans 有没有出现过
bool dfs(int x, int lst) //x 是状压
{
if (vis[x][lst]) return ans[x][lst]; //记忆化搜索
for (int i = 1; i <= n; i++)
if ( !(x & (1 << (i - 1))) ) //意思:x的第i位是0
if (lst == 0 || a[lst][a[lst].length() - 1] == a[i][0]) //如果可以接上去
if ( !dfs(x | (1 << (i - 1)), i) ) //尝试接
{vis[x][lst] = true; return ans[x][lst] = true;} //对手必败,说明我方必胜
vis[x][lst] = true; return ans[x][lst] = false; //怎样都是对手胜,那么我们必败
}
void solve()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) cin >> a[i];
if (dfs(0, 0)) puts("First");
else puts("Second");
}
希望能帮助到大家!
标签:puts,题解,状压,dfs,ABC278F,选过 From: https://www.cnblogs.com/liangbowen/p/16910421.html