ABC278F 题解

前言

题目传送门！

或许更好的阅读体验？

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

思路

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

希望能帮助到大家！