Timus 1654. Cipher Message 破解密码

Müller tried to catch Stierlitz red-handed many times, but always failed because Stierlitz could ever find some excuse. Once Stierlitz was looking through his email messages. At that moment, Müller entered secretly and watched a meaningless sequence of symbols appear on the screen. “A cipher message,” Müller thought. “UTF-8,” Stierlitz thought.

It is known that Stierlitz ciphers messages by the following method.

1. He deletes all spaces and punctuation marks.
2. He replaces all successive identical letters by one such letter.
3. He inserts two identical letters at an arbitrary place many times.

Try to restore a message as it was after the second step. For that, remove from the message all pairs of identical letters inserted at the third step.

Input

The only input line contains a message ciphered by Stierlitz. The message consists of lowercase English letters and its length is at most 200000.

Output

Output the restored message.

Sample

input output

wwstdaadierfflitzzz	stierlitz

这道题目其实十分有趣的。

如果按照原文叙述求思考，那么就很可能犯错的。

我们应该换一个角度来思考。

题目的意思就变成：

如果字符重复出现的次数是双次，那么就删除这个字符，如果出现的次数是单次，那么就保留这个字符。

这样诠释之后，题目豁然开朗，原来就是一个简单的操作字符串的问题。

这样写不会有bug。网上有些这道题目的AC程序是有bug的，应付不了所有特殊情况，不过这道题的测试用例似乎不是那么强，没有全面地测试所有特殊情况。

下面看我的程序，十分简洁明了的，速度也相当快0.04ms：

#include <string>
#include <iostream>
using namespace std;

void CipherMessage1654()
{
	string s;
	cin>>s;
	int c = 1;
	string rs;
	for (int i = 0; i < (int)s.size(); i++)
	{
		if (rs.empty() || rs.back() != s[i])
		{
			if (c % 2 == 0) rs.pop_back();			
			if (!rs.empty() && rs.back() == s[i]) c = 2;
			else
			{
				rs.push_back(s[i]);
				c = 1;
			}
		}
		else c++;
	}
	if (c % 2 == 0 && !rs.empty()) rs.pop_back();
	cout<<rs;
}

int main()
{
	CipherMessage1654();
	return 0;
}