noi.ac 字符串游戏 - ltdJcoder - JOYK Joy of Geek, Geek News, Link all geek

noi.ac 字符串游戏 - ltdJcoder

2 years ago

source link: https://www.cnblogs.com/ltdjcoder/p/16051790.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

题目传送门

Zhangzj和Owaski在玩一个游戏。最开始有一个空的01串，Zhangzj和Owaski轮流进行操作，Zhangzj先走。每次进行操作的人可以在串上任意位置加一个新的字符，由于串是01串，新加的字符也只能是“0”或者“1”。

他们事先约定好一个字符串ss，如果在任意时刻，这个字符串包含ss作为它的一个子串，那么Zhangzj获胜。现在给定ss，假设Zhangzj和Owaski均按照最优策略进行操作，你的任务是判断Zhangzj能不能在有限时间内获胜。

A,B轮流往一个初始为空的 0101 串中插入 00/11, A先手，每次可以插在任意位置。给定一个 0101串ss，若某一时刻字符串包含 ss 作为它的一个子串, A赢得游戏。问A是否能在有限时间赢得游戏。

这种题首先要手玩样例，你大概能发现以下结论：
首先，如果B想，无论A如何操作， B总能在他操作后让字符串变成一个0101间隔的串，
同理，在A操作一次后，无论B如何操作， A都能让其变成 0101 间隔串
也就是说, 假如其中一方想, 就可让这个串始终是 0101间隔串,无论对方怎么操作

继续考虑, A如何获胜? 例如 01100110 , A可以通过往 010010 中插入一个 11 来得到
也就是说, 如果 ss 能通过 0101间隔串加入一个字符得到, 那么A可以先让原串先保持 0101 间隔, 等长度足够时再插入一个字符, A必胜

否则的话, ss不能通过 0101间隔串加 11 一个字符得到, 那么B可以让串始终 0101 间隔, 无法赢

然后就没有然后了, 考虑如果如果一个串中有超过一个相邻相同的位置, 那么就无法得到, 否则一定能

#include <iostream>
#include <cstdio>
using namespace std;

int read(){
    int num=0, flag=1; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) num=num*10+c-'0', c=getchar();
    return num;
}

int n, T;

void reads(){
    int las, cnt=0; char c = getchar();
    while(c!='1' && c!='0') c=getchar();
    las = c, c=getchar();
    while(c=='0' || c=='1') {
        if(c == las) cnt++;
        las = c;
        c=getchar();
    }
    printf(cnt>=2?"Owaski\n":"Zhangzj\n");
}

int main(){
    T = read();
    while(T--) reads();
    return 0;
}

Recommend

181