ABC278F 题解

liangbowen · 2022-11-21 09:52:21 · 题解

前言

题目传送门！

更好的阅读体验？

博弈论，状压，记忆化搜索。

整合题解。

思路

看到很小的 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");
}

希望能帮助到大家！