[TIOJ] 1092. A.跳格子遊戲

題目連結:http://tioj.infor.org/problems/1092
本題是個對稱遊戲,所以應該只需要管該點是先手贏或後手贏,那顯然最後一點是先手贏,而連到最後一點的都輸,所以可以導出該點一定跟他下一點相反,而如果前面的點有必勝的點,那對方也一定走過去,所以只要看他連到的點有沒有必勝的,若有自己就必輸,若無則自己必贏,所以DFS一遍就可以解決了XD
#include <bits/stdc++.h>
using namespace std;
#define N 10000

vector<int> graph[N+10];
int n,e;
bitset<N+10> isset;
bitset<N+10> val;

inline void init();
bool dfs(int);

int main(){
	scanf("%d%d",&n,&e);
	while(n+e!=0){
		init();
		while(e--){
			int a,b;
			scanf("%d%d",&a,&b);
			graph[a].push_back(b);
		}
		isset[n]=1;
		val[n]=1;
		dfs(1);
		char name[7];
		scanf("%s",name);
		if((!val[1] && name[1]=='i') || (val[1] && name[1]=='o'))
			puts("Moumou");
		else
			puts("Mimi");
		scanf("%d%d",&n,&e);
	}
	return 0;
}

inline void init(){
	for(int i=0;i<n;i++)graph[i+1].clear();
	isset.reset();
	val.reset();
}

bool dfs(int w){
	if(!isset[w]){
		bool ans=1;
		for(auto i : graph[w]){
			ans&=dfs(i);
		}
		val[w]=ans;
		isset[w]=1;
	}
	return !val[w];
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology