T - Game with string（栈）

问题描述：

Two people are playing a game with a string ss, consisting of lowercase latin letters.

On a player's turn, he should choose two consecutive equal letters in the string and delete them.

For example, if the string is equal to "xaax" than there is only one possible turn: delete "aa", so the string will become "xx". A player not able to make a turn loses.

Your task is to determine which player will win if both play optimally.

 输入：

The only line contains the string ss, consisting of lowercase latin letters (1≤|s|≤1000001≤|s|≤100000), where |s||s|means the length of a string ss.

输出：

If the first player wins, print "Yes". If the second player wins, print "No".

样例：

Input

abacaba

Output

No

Input

iiq

Output

Yes

Input

abba

Output

No

题目大意：

输入一个字符串，如果有两个字符相邻就可以消去 剩下的部分自动相连接 例如bvvacd ->bacd（这是一次操作）

接下来就换第二个人来操作 直到没有相邻的字符串为止 （如果轮到谁操作了 但是他已经没得操作了那么他就输了）

因此我们在第一个人操作之后就计数 完成一次操作后sum++，结束所有操作后如果sum为偶数那么第一个人就输了 （输出No）

如果sum为奇数第一个人就赢了 （输出Yes）

具体实现：

输入字符串后，遍历字符串，利用栈的特点 如果栈顶元素等于你下一个要遍历的元素 那么就清除栈顶元素（即如果相邻则消除，并且实相当于实现了两个块儿的自动连接）如果不相等就入栈。

话不多说 上代码~

#include<iostream>
using namespace std;
#include<stack>
int main()
{stack<int>a;string s;int i,j,sum=0;cin>>s;a.push(s[0]);//先输入s[0],避免循环时第一个就为空 for(i=1;s[i]!='\0';i++)//魔鬼细节，s[i]!='\0'就不用写i小于字符串的长度了{if(!a.empty()&&a.top()==s[i]){a.pop();//如果栈顶元素与查找的元素相同，则删除栈顶元素 sum++;continue;}else a.push(s[i]);//不相同就进栈 }if(sum%2==0)cout<<"No";else cout<<"Yes";return 0;
}