noi.ac 字符串游戏

2022年1月14日 8点热度 0条评论 来源: ltdJcoder

题目传送门

题面

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

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

题意

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

题解

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

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

否则的话, \(s\)不能通过 \(01\)间隔串加 \(1\) 一个字符得到, 那么B可以让串始终 \(01\) 间隔, 无法赢

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

实现

#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;
}
    原文作者:ltdJcoder
    原文地址: https://www.cnblogs.com/ltdjcoder/p/16051790.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。