qoj6562 First Last 题解

妙妙题。

首先不同字母数最多为 \(3\)。我们把每一个字母看成一个点。对于每一个字符串，首个字母朝末尾字母连一条有向边。那么问题变为了给定一张有向图，从某个点出发，每次走一条边，且边不能重复，不能走的人输。问哪方有必胜策略。

先不考虑时间复杂度，那么这个可以直接爆搜。但是肯定会 T，考虑剪枝。

会发现一些神奇的事情：

• 若点 \(u\) 有 \(2\) 个自环，可以把这两个自环删掉。
• 若 \(u \to v\) 有边，\(v \to u\) 也有边，可以同时删去这两条边。

证明第一个：若先手走了自环，那后手一定也可以走一次自环就回到初始状态了。第二个证明同理。

于是边的情况就很少了，可以直接记忆化搜索求出答案。

//dzzfjldyqqwsxdhrdhcyxll
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e3 + 10;
int n,cnt,ans,a[5][5],b[5][5];
vector <int> now;
map <char,int> mp;
map <pair <vector <int>,int>,bool> dp;
string s[MAXN];
inline int dfs(vector <int> v,int u) {
	if(dp.count(make_pair(v,u))) return dp[make_pair(v,u)];
	bool flag = true;
	for(int i = 0;i < 9;i++) flag &= (v[i] == 0);
	if(flag == true) {
		return dp[make_pair(v,u)] = 0;
	}
	for(int j = 1;j <= 3;j++) {
		if(v[(u - 1) * 3 + j - 1] > 0) {
			v[(u - 1) * 3 + j - 1]--;
			flag |= !dfs(v,j);
			v[(u - 1) * 3 + j - 1]++;
		}
	}
	return dp[make_pair(v,u)] = flag;
}
signed main() {
	cin >> n;
	for(int i = 1;i <= n;i++) cin >> s[i];
	for(int i = 1;i <= n;i++) {
		#define s s[i]
		if(mp[s[0]] == 0) mp[s[0]] = ++cnt;
		if(mp[s[s.length() - 1]] == 0) mp[s[s.length() - 1]] = ++cnt;
		a[mp[s[0]]][mp[s[s.length() - 1]]]++;
		#undef s
	}
	for(int i = 1;i <= 3;i++)
		for(int j = 1;j <= 3;j++) b[i][j] = a[i][j];
 	
	for(int i = 1;i <= 3;i++) {
		for(int j = 1;j <= 3;j++) {
			for(int p = 1;p <= 3;p++) {
				for(int q = 1;q <= 3;q++) {
					a[p][q] = b[p][q];
				}
			}
			if(a[i][j] == 0) continue;
			a[i][j]--;
			for(int p = 1;p <= 3;p++) a[p][p] %= 2;
			for(int p = 1;p <= 3;p++) {
				for(int q = p + 1;q <= 3;q++) {
					int mn = min(a[p][q],a[q][p]);
					a[p][q] -= mn;
					a[q][p] -= mn;
				}
			}	
			now.clear();
			for(int p = 1;p <= 3;p++) {
				for(int q = 1;q <= 3;q++) {
					now.emplace_back(a[p][q]);
					if(a[p][q] != 0) {
					}
				}
			}
			bool flag = dfs(now,j) ^ 1;
			ans += flag * b[i][j];
		}
	}
	cout << ans;
	return 0;
}