这个题巨坑,tag写博弈论,实际上是暴搜,并且剪枝优化点很多,有点没剪就TLE

/**
 * 博弈论,看必胜态和必输态
 * 让对方无法构成胜利态LOL、也就是说,双方都不能填到LO*、*OL、L*L形式
 * 除非无论怎么填都会变成这种形式,那么就会构成必败态
*/
#include <map>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

//-1为输, 1为赢, 2代表平局
map<string, int> mp;
char rep[2] = {'L', 'O'};

int n;

// u=1代表小明,u=0代表大师
// 如果有必胜态,那么必胜,如果无必胜态但有平局态,那么平局,如果只有必败态,那么必败
// res记录平局次数
int check(string s)
{
    if (mp.find(s) != mp.end()) return mp[s];
    if (s.length() < 3)
    {
        mp[s] = 2;
        return 2;
    }

    if (s.find("LO*") != -1 || s.find("*OL") != -1 || s.find("L*L") != -1)
    {
        mp[s] = 1;
        return 1;
    }

    if (s.find("*") == -1 && s.find("LOL") == -1)
    {
        mp[s] = 2;
        return 2;
    }

    int res = 0;
    for (int i = 0; s[i]; i ++ )
    {
        if (s[i] == '*')
        {
            for (int j = 0; j < 2; j ++ )
            {
                s[i] = rep[j];
                int flag = check(s);
                if (flag == 2) res = 1;
                if (flag == -1) return 1;
                s[i] = '*';
            }
        }
    }

    if (!res) {
        mp[s] = -1;
        return -1;
    }

    mp[s] = 2;
    return 2;
}

int main()
{
    cin >> n;

    while (n -- )
    {
        string str;
        cin >> str;

        int res = check(str);
        if (res == 2) puts("0");
        else cout << res << endl;
    }

    return 0;
}