打卡信奥刷题（3260）用C++实现信奥题 P8658 [蓝桥杯 2017 国 A] 填字母游戏

P8658 [蓝桥杯 2017 国 A] 填字母游戏

题目描述

小明经常玩 LOL 游戏上瘾，一次他想挑战 K 大师，不料 K 大师说：

“我们先来玩个空格填字母的游戏，要是你不能赢我，就再别玩 LOL 了”。

K 大师在纸上画了一行nnn个格子，要小明和他交替往其中填入字母。

并且：

1. 轮到某人填的时候，只能在某个空格中填入L或O。

2. 谁先让字母组成了LOL的字样，谁获胜。

3. 如果所有格子都填满了，仍无法组成LOL，则平局。

小明试验了几次都输了，他很惭愧，希望你能用计算机帮他解开这个谜。

输入格式

本题的输入格式为：

第一行，数字nnn（n<10n<10n<10），表示下面有nnn个初始局面。

接下来，nnn行，每行一个串（长度<20)<20)<20)，表示开始的局面。

比如：******，表示有666个空格。

L****，表示左边是一个字母LLL，它的右边是444个空格。

输出格式

要求输出nnn个数字，表示对每个局面，如果小明先填，当 K 大师总是用最强着法的时候，小明的最好结果。

1表示能赢。

-1表示必输。

0表示可以逼平。

输入输出样例 #1

输入 #1

4 *** L**L L**L***L L*****L

输出 #1

0 -1 1 1

说明/提示

时限 1 秒, 256M。蓝桥杯 2017 年第八届国赛

C++实现

#include<bits/stdc++.h>usingnamespacestd;map<string,int>m;string s;intcheck(){if(m.count(s))returnm[s];if(s.find("LOL")!=-1)return-1;if(s.find('*')==-1)return0;boolres=false;for(inti=0;s[i];i++){if(s[i]=='*'){s[i]='L';intans=check();s[i]='*';if(ans==-1)returnm[s]=1;elseif(ans==0)res=true;s[i]='O';ans=check();s[i]='*';if(ans==-1)returnm[s]=1;elseif(ans==0)res=true;}}if(res)returnm[s]=0;returnm[s]=-1;}intmain(){intn;cin>>n;for(inti=1;i<=n;i++){cin>>s;if(s.length()<3){cout<<"0"<<endl;continue;}cout<<check()<<endl;}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容