寒冬信使（牛客练习赛90+阶梯博弈）

Piink

已于 2022-04-04 17:40:41 修改

阅读量134

点赞数

于 2021-11-06 19:54:37 首次发布

本文链接：https://blog.csdn.net/Piink/article/details/121184079

版权

博弈论算法二进制操作字符串处理游戏策略

关键词由CSDN通过智能技术生成

什么是阶梯博弈？
https://blog.csdn.net/qq_30241305/article/details/51956518

把曾经白色的部分全部染黑

nn 个格子排成一排，每个格子是黑色或者白色的。

有双方在格子上进行博弈，根据先后手轮流进行操作，每次操作方可以选择一个白色格子并且翻转这个格子和它前面一个格子的颜色（如果选择的是第一个格子则只翻转这个格子的颜色）。

无法操作者败，求是否先手必胜。
输入描述:
第一行给出一个正整数 TT (1\leq T\leq 10)(1≤T≤10) 表示数组组数。

接下来 TT 行给出一个长度为 nn (1\leq n\leq 10^5)(1≤n≤10
5
) 的 0101 串。

00 表示该格子颜色为黑色，11 表示该格子颜色为白色。

输出描述:

答案输出 TT 行分别表示每组数据的答案。
若先手必胜则输出 TT ，否则输出 XX 。

示例1
输入
4
01
1101
0101110110
0110111000

输出

X
T
X
T

代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char a[100010];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",a);
        int l=strlen(a);
        int ans=0;
        for(int i=0; i<l; i+=2)
        {
            ans=ans^(a[i]-48);
        }
         if(ans==1)
            printf("T\n");
         else
            printf("X\n");
    }
    return 0;
}