Codeforces 1506G - Maximize the Remaining String

Codeforces 1506G - Maximize the Remaining String

八月 04, 2021

题目概述

给定一个字符串$s$,求将$s$中的重复字符删除，使得剩下的字符串字典序最大。

分析与解

我们想逐位确定。最初的思路是从’z’到’a’进行贪心。但发现前后顺序并不能有唯一确定的规则。实际上我们还是可以逐位确定的，只是相当于要求，每一次填入一个有限制条件的最大字符。所谓的限制条件，就是当这个字符填入后，它后面的字符能够保证将原本答案剩下的不同的字符填上。具体来说，就是假设填完字符$c$后答案串还得填$k$种字符，那么原串$c$的首位置之后的后缀必须有这$k$种字符。

由于总共只有26种字符，所以模拟判定即可。学习一下标程STL的应用。因为数据量并不是很大，所以用string也没问题。此外，reverse方法是可以应用到string和vector的。

关于实现，或者说另一个常见的思路，是用单调栈。

我们维护每个字符在当前的剩余串中的出现次数，维护一个字典序从（栈底）大到小的单调栈，每次新压入一个字符之前，弹出所有在后面还能出现，且字典序比当前字母小的字母，更新次数。最后把字母从栈底到栈顶输出即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
int distin(string a) {
	sort(a.begin(),a.end());
	return unique(a.begin(),a.end()) - a.begin();
}
string filt(const string &s,char c) {
	string t;
	bool fir=false;
	for(char now : s) {
		if(now!=c && fir)
			t+=now;  //验证限制，只有在这个后面的才能加入
		else if(now==c)
			fir=true;
	}
	return t;
}
string inp;
set<char> hav;
int main() {
	char now;
	int kase,k;
	scanf("%d",&kase);
	while(kase--) {
		cin>>inp;
		string ans;
		k=distin(inp);
		hav.clear();
		for(auto t : inp)hav.insert(t);
		while(k) {
			now=-1;
			for(auto x : hav)
				if(distin(filt(inp,x)) == k-1)
					now=max(now,x);
			ans+=now;
			hav.erase(now);
			inp=filt(inp,now);
			k--;

		}
		cout<<ans<<endl;
	}
	return 0;
}