題目描述:
A 與 B 正在玩一個關于由小寫拉丁字元構成的字元串 s 的遊戲,每一個人會輪流操作,先 A 後 B,對于每一次操作,操作者需要将 s中的兩個連續且相同的字元消除,消除後的字元串由另一個人操作,同樣的,對于每一次操作,如果不能找到兩個符合要求的字元,那麼操作者輸。
例如以下情況:
s = ''xaax''
首先是 A 操作,他隻能将 ''aa'′ 删除,剩下 ′′xx′′,被 B 消除後字元串為空,A 不能找到符合的字元串,故 A輸。
輸入:s(1<=s的長度<=100000)
輸出:第一行為字元串s輸出格式;若 A 可以獲勝則輸出 Yes,否則輸出No。
解題思路:
- 如果目前輸入的字元串與前一個相同,就删除前一個。
- 隻需要将目前的位置-2(因為每次 i 都要 i++ ),後面輸入進來就的會覆寫掉前面的。
- 每次删除回合數+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() 傳回棧頂元素