301036: CF196A. Lexicographically Maximum Subsequence
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Lexicographically Maximum Subsequence
题意翻译
## 题目描述: 你现在有一个只包含小写英文字母的字符串,要求求它的最大字典序子序列。 我们把一个非空字符串s[p_{1}p_{2}...\ p_{k}]=s_{p1}s_{p2}...\ s_{pk}(1<=p_{1}<p_{2}<...<p_{k}<=|s|)叫做字符串s=s1s2…s|s|的一个子序列。 如果|x|>|y|而且x1=y1,x2=y2…X|y|=Y|y|或者存在一个数字r (r<|x|,r<|y|)满足x1=y1,x2=y2…X|y|=Y|y|并且x_{r+1}>y_{r+1},那么字符串x=x1x2…x|x|在字典序上比字符串y=y1y2…y|y|大。在行中的字符根据他们的ASCII码进行比较 ## 输入格式: 只有一行,包括一个非空的只含小写字母的字符串s,字符串长度不超过10^5 ## 输出格式: 输出只有一行,输出字符串s的 最大字典序子序列 ## 说明/提示: 让我们看一下样例并看一看待求的子序列长什么样子(用大写粗体字母标注) 样例1:a**B**a**BBA** 样例2:abb**C**b**CC**a**C**bb**CB**aa**BA**题目描述
You've got string $ s $ , consisting of only lowercase English letters. Find its lexicographically maximum subsequence. We'll call a non-empty string $ s[p_{1}p_{2}...\ p_{k}]=s_{p1}s_{p2}...\ s_{pk}(1<=p_{1}<p_{2}<...<p_{k}<=|s|) $ a subsequence of string $ s=s_{1}s_{2}...\ s_{|s|} $ . String $ x=x_{1}x_{2}...\ x_{|x|} $ is lexicographically larger than string $ y=y_{1}y_{2}...\ y_{|y|} $ , if either $ |x|>|y| $ and $ x_{1}=y_{1},x_{2}=y_{2},...\ ,x_{|y|}=y_{|y|} $ , or exists such number $ r $ $ (r<|x|,r<|y|) $ , that $ x_{1}=y_{1},x_{2}=y_{2},...\ ,x_{r}=y_{r} $ and $ x_{r+1}>y_{r+1} $ . Characters in lines are compared like their ASCII codes.输入输出格式
输入格式
The single line contains a non-empty string $ s $ , consisting only of lowercase English letters. The string's length doesn't exceed $ 10^{5} $ .
输出格式
Print the lexicographically maximum subsequence of string $ s $ .
输入输出样例
输入样例 #1
ababba
输出样例 #1
bbba
输入样例 #2
abbcbccacbbcbaaba
输出样例 #2
cccccbba