Logo CSP.ac

CSP.ac

1 s / 256 MB

#124. 【冬令营】Day3T1-XX粒子

统计

【问题描述】

小苇最近在实验室里发现了一类全新粒子,这类粒子有着无比神奇的特性以至于人们长久以来一直没有发现他们。为了方便向你表述这类粒子的性质,小苇给这类粒子起了个

名字——XX粒子。因为小苇到目前为止也才发现26种XX粒子,不妨将他们命名为a~z。

XX粒子特别有意思,当他们被排列到一条直线上时,如果两个相同种类的XX粒子间没有XX粒子的话他们就会互相湮灭,比如“abbc”中两个b会湮灭变成“ac”,而“abccb

d”会产生连锁反应最后变成“ad”。我们又认为两组湮灭不可能同时发生。比如“ccc”湮灭后最后还是会剩下一个“c”。

现在小苇告诉了你一开始他控制的XX粒子形成的排列,他想知道等湮灭都结束了以后剩余的排列是什么样子的?

【输入格式】

第一行一个字符串,表示初始状态XX粒子的排列

【输出格式】

输出一行一个字符串,表示所有可以进行的湮灭都结束了以后剩余粒子的排列,如果最后一个粒子也没剩下,就输出空串。

【样例输入】

abddbeeb

【样例输出】

ab

【样例解释】

“abddbeeb”->“abbb” 然后有两种湮灭的可能,但是最后都是“ab”

【数据规模和约定】

对于30%的数据, n<=24

对于50%的数据, n<=1024

对于100%的数据, n<=200024