nim博弈2： hiho1172

• • 描述

描述

Alice和Bob这一次准备玩一个关于硬币的游戏：

N枚硬币排成一列，有的正面朝上，有的背面朝上，从左到右依次编号为1..N。现在两人轮流翻硬币，每次只能将一枚正面朝上的硬币翻过来，并且可以随自己的意愿，在一枚硬币翻转后决定要不要将该硬币左边的任意一枚硬币也翻一次(正面翻到背面或背面翻到正面)。翻最后一枚正面向上的硬币的人获胜。同样的，这次游戏里面Alice仍然先手，两人均采取最优的策略，对于给定的初始局面，Alice会获胜还是Bob会获胜？

提示：Turning Turtles

输入

第1行：1个正整数N，表示硬币数量。1≤N≤10,000

第2行：1个字符串，第i个字符表示编号为i的硬币状态，’H’表示正面朝上，’T’表示背面朝上。

输出

第1行：1个字符串，若Alice能够获胜输出”Alice”，否则输出”Bob”

样例输入

8

HHTHTTHT

样例输出

Bob

需要转换一次的nim博弈，转换之后相对简单

#include<iostream>
#include<cstdio>
#include<cstring>
//#include<vector>
#include<algorithm>

#ifdef L_JUDGE
#pragma warning(disable:4996)
#endif

using namespace std;
const int MAXN=;

int N;
int num[MAXN];
int len;
char s[MAXN];


int main(){
    #ifdef L_JUDGE
        freopen("in.txt","r",stdin);
//      freopen("out.txt","w",stdout);
    #endif
    scanf("%d",&N);
    scanf("%s",s);
    len=;
    int slen=strlen(s);
    for(int i=;i<slen;i++){
        if(s[i]=='H'){
            num[len]=i+;
            len++;
        }
    }
    int res=;
    for(int i=;i<len;i++){
        res^=num[i] ;
    }
    if(res){
        printf("Alice\n");
    }else{
         printf("Bob\n");
    }

    #ifdef L_JUDGE
        fclose(stdin);
        fclose(stdout);
//      system("out.txt");
    #endif

    return ;
}