codeforces-1104B. Game with string-題解

題目描述:

A 與 B 正在玩一個關于由小寫拉丁字元構成的字元串 s 的遊戲，每一個人會輪流操作，先 A 後 B，對于每一次操作，操作者需要将 s中的兩個連續且相同的字元消除，消除後的字元串由另一個人操作，同樣的，對于每一次操作，如果不能找到兩個符合要求的字元，那麼操作者輸。

例如以下情況：

s = ''xaax''

首先是 A 操作，他隻能将 ''aa'′ 删除，剩下 ′′xx′′，被 B 消除後字元串為空，A 不能找到符合的字元串，故 A輸。

輸入：s（1<=s的長度<=100000）

輸出：第一行為字元串s輸出格式；若 A 可以獲勝則輸出 Yes，否則輸出No。

解題思路：

1. 如果目前輸入的字元串與前一個相同，就删除前一個。
2. 隻需要将目前的位置-2（因為每次 i 都要 i++ ），後面輸入進來就的會覆寫掉前面的。
3. 每次删除回合數+1，最後看奇偶性來判斷輸赢！！！

小編的代碼如下：

#include<cstdio>
#include<iostream>
using namespace std;
char a[100005];
int main()
{
    int x=0;
	int i=1;
    while(cin>>a[i]&&(a[i]>'a'||a[i]<'z'))
    {
        if(a[i]==a[i-1])//如果一樣
        {
            i=i-2;
			x++;//删除并加一次回合
        }
        i++;
    }
        if(x%2==1)
		    cout<<"Yes"<<endl;//為奇數則是A赢了
        else 
		    cout<<"NO"<<endl;//為偶則是B
    return 0;
}
           

不過小編想知道有沒有别的做法，故上網搜尋發現如下：

#include<cstdio>
#include<stack>
#include<cstring>
using namespace std;
const int N=1e5+50;
char s[N];
int len,Ans;
stack<char>qwq;
int main()
{
    scanf("%s",s);
    len=strlen(s);
    for(int i=0;i<len;i++){
        if(qwq.empty()||s[i]!=qwq.top())
            qwq.push(s[i]);
        else 
            Ans++,qwq.pop();
    }
    puts(Ans&1?"Yes":"No");
    return 0;
}
           

順便補充：

stack 類

STL中的很有用的容器之一，其中元素遵循先進先出原則

包含以下幾個成員函數：

empty() 堆棧為空則傳回真

pop() 移除棧頂元素（不會傳回棧頂元素的值）

push() 在棧頂增加元素

size() 傳回棧中元素數目

top() 傳回棧頂元素