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

92 阅读 0 评论 61 点赞

我是靠谱客的博主现实砖头，最近开发中收集的这篇文章主要介绍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_{l-2},s_{l-1},s_l}$

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

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

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

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

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

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

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

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

最后没状态的就是平局

#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;
    }	
}