AtCoder Beginner Contest 209 E - Shiritori(博弈,图)

LINK

Takahashi先手(叫做小$T$),Aoki后手(叫做小$A$)

每个人轮流说一个单词,这个单词的前三个字母必须等于上一个单词的后三个字母

现在问当小$T$说出的第一个单词为$s_i$时,能否获得胜利??

可以$O(n^2)$暴力枚举两点间是否有边,但是复杂度太高

考虑每个单词只有前三个字母和后三个字母有用

把前三个字母浓缩成一个点,后三个字母浓缩成一个点

那么单词$s_i$(设长度为$l$)就表示能从 { s 1 , s 2 , s 3 } {s_1,s_2,s_3} {s1​,s2​,s3​}转移到 { s l − 2 , s l − 1 , s l } {s_{l-2},s_{l-1},s_l} {sl−2​,sl−1​,sl​}

这样整个图只有$n$条边

小$T$选定第一个单词为$s_i$,在我们构造的图中相当于是以 { s l − 2 , s l − 1 , s l } {s_{l-2},s_{l-1},s_l} {sl−2​,sl−1​,sl​}点为起始点的胜负状态

如果这个图是个DAG，问题就变得非常简单,拓扑排序一下就好了.

令状态$0$表示先手赢,状态$1$表示后手赢,状态$2$表示平局

若$i$的所有后继都是先手赢,那么$f[i]=1$,先手必败

若$i$存在后继是后手赢,那么$f[i]=0$,先手必胜

但是这个图可能有环,不过还是可以一样的拓扑排序…

但是当一个点度为零或确定状态时就入队

最后没状态的就是平局

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
const int M = 52*52*52;
int z(char c)
{
    if('A'<=c && c<='Z') return c-'A';
    else return c-'a'+26;
}
int trans(char a,char b,char c)
{
    return z(a) * 52 * 52 + z(b) * 52 + z(c);
}
int in[M];
int main()
{
	int n; cin >> n;
	vector<pair<int,int>> edge(n);
	vector<vector<int> > revGraph(M);
	for(int i=0;i<n;i++)
	{
		string s; cin >> s;
        edge[i] = make_pair(trans(s[0], s[1], s[2]), trans(s[s.size()-3], s[s.size()-2], s[s.size()-1]));
        in[edge[i].first]++;
        revGraph[edge[i].second].push_back(edge[i].first);		
	}
    vector<int> ans(M, -1);
    queue<int> que;
    for(int i = 0; i < M; i++) 
		if( in[i] == 0)
		{
        	ans[i] = 0;//赢 
        	que.push(i);
    	}
    while(!que.empty()) 
	{
        int t = que.front(); que.pop();
        for(int x : revGraph[t] )
		{ 
			if(ans[x] == -1) 
			{
	            in[x]--;
	            if(ans[t] == 0)
	                ans[x] = 1, que.push(x);
	            else if( in[x] == 0)
	                ans[x] = 0, que.push(x);
	        }
	    }
    }
    for(int i = 0; i < n; i++) 
	{
        if(ans[edge[i].second] == -1) cout << "Draw" << endl;
        if(ans[edge[i].second] == 0) cout << "Takahashi" << endl;
        if(ans[edge[i].second] == 1) cout << "Aoki" << endl;
    }	
}

最后

以上就是现实砖头最近收集整理的关于AtCoder Beginner Contest 209 E - Shiritori(博弈,图)的全部内容，更多相关AtCoder内容请搜索靠谱客的其他文章。