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 ;
}