题解 | 填字母游戏

#include<bits/stdc++.h>
using namespace std;

const int N=1e5;

int T;
map<string,int> mp;

//mp==-1 代表Alice获胜
//mp==0  代表平局情况
//mp==1  代表Bob获胜 

int dfs(string state){ // f==false 代表Alice出手  f==true 代表Bob出手 
	
	if(mp.count(state)!=0) return mp[state];
	
	if(state.find("LOL")!=string::npos){
		return mp[state]=1;
	}
	
	if(state.find("*")==string::npos){
		return mp[state]=0;
	}
	
	bool tie=false;
	for(int i=0;i<state.size();i++){
		if(state[i]=='*'){
			
			state[i]='L';
			if(dfs(state)==1){
				state[i]='*';
				return mp[state]=-1;
			}
			
			if(dfs(state)==0){
				tie=true;
			}
			
			state[i]='O';
			if(dfs(state)==1){
				state[i]='*';
				return mp[state]=-1;
			}
			
			if(dfs(state)==0){
				tie=true;
			}
			
			state[i]='*';
			
		}
	}
	
	if(tie){
		return mp[state]=0;
	}else{
		return mp[state]=1;
	}
	
}

void solve(string s){
	
	int res=dfs(s);
	
	if(res==-1){
		cout<<"Alice"<<endl;
	}else if(res==0){
		cout<<"Tie"<<endl;
	}else{
		cout<<"Bob"<<endl;
	}
	
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>T;
	while(T--){
		string s;
		cin>>s;
		solve(s);
	}
	
    return 0;
}