[CF1220C] Substring Game in the Lesson - 博弈论

2024-10-08 09:42:06

[CF1220C]

Description

给定一个字符串 \(S\) ，同时维护一个区间 \([l,r]\) 。轮流操作，每次可以扩展到一个新区间使得原区间是新区间的真子区间，并且字典序更小，不能操作的人输。初态区间为 \([k,k]\) ，你需要对 \(k=1,2,...,|S|\) 判断胜负性。

Solution

很容易发现游戏最多玩一轮，所以只需要判断每个字母之前有没有更小的字母就可以了。

#include <bits/stdc++.h>

using namespace std;

string str;

int c[27];

int main()

{

    ios::sync_with_stdio(false);

    cin>>str;

    int n=str.length();

    for(int i=0;i<n;i++)

    {

        c[str[i]-'a'+1]++;

        int flag=0;

        for(int j=0;j<str[i]-'a'+1;j++) flag+=c[j];

        if(flag) cout<<"Ann"<<endl;

        else cout<<"Mike"<<endl;

    }

}

最新文章

热门文章