字符串构造,思维 - Codeforces Problem 1506 G - Maximize the Remaining String
本题做法相对暴力,但是还是应该学习其STL的用法、构造思路。
count_unique(string s)
函数为离散化函数,用于统计字符串s中不重复字符的数量。
filter(string s, char c)
函数返回字符串s的,从第一个c字符往后的,不包括字符c的子序列。
程序首先读入字符串s,然后用count_unique(s)
统计s的不重复字符的数量,记录为k。这个k同时也是我们的答案字符串的长度。
接下来,我们设法构造出答案字符串t,使得其为s的一个字典序最大的、无重复字符的子序列。
为此,首先获得字符串s的所有不重复字符,我们可以用一个集合来实现去重。
只要k大于0(表示我们还应该继续加入新的字符),我们就遍历集合的各个字符c,判断c是否能够加入最终的答案串t。如果可以加入,并且字典序更大,那么就将其选为备选字符maxC。然后将本轮选出的字符maxC加入到答案串t后,并且使s = filter(s, maxC)。这一步是因为,既然已经在答案串中加入了maxC字符,那么答案串一定不能再包括第一个maxC以前的字符以及maxC本身了。同时还应该使k-=1。
最终代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int t;
int count_unique(string s){
sort(s.begin(), s.end());
return unique(s.begin(), s.end()) - s.begin();
}
string filter(string s, char c){
string t = "";
bool first = false;
for(char a : s){
if(a != c && first){
t += a;
}else if(a == c){
first = true;
}
}
return t;
}
int main(){
cin >> t;
while(t--){
string s;
cin >> s;
int k = count_unique(s);
set<char> st(s.begin(), s.end());
string t = "";
while(k){
char maxC = -1;
for(char c : st){
if(count_unique(filter(s, c)) == k-1){
maxC = max(maxC, c);
}
}
t += maxC;
st.erase(maxC);
s = filter(s, maxC);
--k;
}
cout << t << endl;
}
return 0;
}