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() 返回栈顶元素