题解：状态压缩之后，暴力dfs，如果有一个选择，能让对手必败，那么就是必胜态，能转移到的状态都是对手的必胜态，或者无法转移，就是必败态。
总算是过了，TLE是因为状态没判重。
#include<cstdio> #include<cmath> #include<vector> #include<map> #include<set> #include<algorithm> #include<iostream> #include<cstring> using namespace std; typedef long long ll; //#define local const int maxn = 10023; char str[maxn]; int n,m; struct Node { char h,r; }; Node P[2][10]; bool G[2][10][10]; bool vis[1<<18]; bool dfs(int p,int u,int sta) { for(int v = 0,sz = p?m:n; v < sz; v++) if(G[p][u][v]&&!((sta>>(v+p*9))&1)) { int newsta = sta|(1<<(v+p*9)); if(vis[newsta]) continue; vis[newsta] = 1; if(!dfs(p^1,v,newsta)) return true; vis[newsta] = 0; } return false; } int main() { #ifdef local freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); #endif // local int T; scanf("%d",&T); for(int k = 1; k <= T; k++){ scanf("%d",&n); getchar(); for(int i = 0; i < n; i++){ gets(str); P[0][i].h = *str; P[0][i].r = str[strlen(str)-1]; } scanf("%d",&m); getchar(); for(int i = 0; i < m; i++){ gets(str); P[1][i].h = *str; P[1][i].r = str[strlen(str)-1]; } memset(G,0,sizeof(G)); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(P[0][i].r == P[1][j].h) { G[1][i][j] = 1; } if(P[1][j].r == P[0][i].h) { G[0][j][i] = 1; } } } memset(vis,0,sizeof(vis)); bool p1Win = false; for(int i = 0; i < n; i++){ if(!dfs(1,i,1<<i)) { p1Win = true; break; }; } printf("Game %d: player%d ",k,p1Win?1:2); } return 0; }