自动搬运

查看原文

来自洛谷，原作者为

	Nightsky_Stars .

搬运于2025-08-24 22:41:09，当前版本为作者最后更新于2023-12-21 20:15:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

递归 + 记忆化搜索，记忆化用 map 。

我们既然是和小明一伙的，所以肯定很希望小明输，所以能胜就胜，不能就平，否则才败。

每次就判断一下小明是否胜利及是否有未填的空位，再循环遍历一下，如果该位置为空位，就尝试将 L 和 O 填入空位，看看能不能赢。

CODE:

#include<bits/stdc++.h>
using namespace std;
map<string,int> m;
string s;
int check(){
	if(m.count(s)) return m[s];
	if(s.find("LOL")!=-1) return -1;
	if(s.find('*')==-1) return 0;
	bool res=false;
	for(int i=0;s[i];i++){
		if(s[i]=='*'){
            s[i]='L';
            int ans=check();
            s[i]='*';
            if(ans==-1) return m[s]=1;
            else if(ans==0) res=true;
            s[i]='O';
            ans=check();
            s[i]='*';
            if(ans==-1) return m[s]=1;
            else if(ans==0) res=true;
   		}
	}
	if(res) return m[s]=0;
    return m[s]=-1;
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s;
		if(s.length()<3){
			cout<<"0"<<endl;
			continue;
		}
		cout<<check()<<endl;
	}
	return 0;
}