String Coloring （easy and hard）详解

这题其实很简单，只要想到了接下来就是水到渠成

题目传送门

Easy：

思路：我们需要把小的放到前面去，怎么定义这个小呢，就是在它之前存在了比它大的字符。我们可以把所有需要 转移位置的字符（前面有比它大的字符）用一个vector存储起来然后再进行转移（默认颜色为0，vector中的字符都为颜色1）。 关键点来了：这个vector中的字符必须是不减的。 因为 比它 大 的字符转移之后一定会在小的字符的转移路径上进行阻碍。比如说aabbedc ，我们把dc存储到vector中，d转移好了之后，一定会在c的转移路径上，所有这个样例是不能完成的。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pii pair<int,int>
const int maxn = 2e5 + 5;

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	string s;
	cin >> s;
	string ans(n,'0');  //默认为颜色0，vector中的字符设定为颜色1
	char c = 'A';
	vector<char>v;
	for (int i = 0; i < n; i++)
	{
		if (s[i] >= c) c = s[i];
		else
		{
			ans[i] = '1';
			v.push_back(s[i]);
		}
	}
	vector<char> temp = v;
	sort(temp.begin(), temp.end());
	if (v != temp) //如果排序之后不一样了，说明不是单调不减序列
	{
		cout << "NO\n";
	}
	else
	{
		cout << "YES\n";
		cout << ans << "\n";
	}
	return 0;
}

题目传送门

Hard:

这题思路和easy的差不多，这里要多注意一个放颜色的问题。看到字符串题目就可以想一想从26个字符下手！！！这里只需要在每个需要转移字符的前面寻找到比它大的字符的最大颜色值就可以了，我们可以用一个map来存储。比如说zywmerhahx这个样例，我们老样子把ywmerhahx存入vector中，从左到右开始，y前面没有比它大的，mp[y]=2,w前面y比它大,mp[w]=mp[y]+1=3,m前面，y和w都比m大，那么我们取最大的，mp[m]=mp[w]+1=4，至于怎么找最大的，只需要便利一下26个字母就行可

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pii pair<int,int>
#define pci pair<int,int>

map<char, int>mp;
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	string s;
	cin >> s;
	vector<int>ans(n,1);
	int c = 0;
	vector<pci>v;
	for (int i = 0; i < n; i++)
	{
		if (s[i] >= c) c = s[i];
		else
			v.push_back({ s[i],i });
	}
	for (int i = 0; i < v.size(); i++)
	{
		int maxx = 0;
		for (char j = v[i].first+1; j <= 'z'; j++)
		{
			if (mp[j])
				maxx = max(maxx, mp[j]);
		}
		if (maxx == 0) ans[v[i].second] = 2, mp[v[i].first] = 2;
		else ans[v[i].second] = maxx + 1, mp[v[i].first] = maxx + 1;
		
 	}
	int maxx = 0;
	for (char i = 'a'; i <= 'z'; i++)
		maxx = max(maxx, mp[i]);
	if (maxx == 0) maxx = 1;
	cout << maxx << "\n";
	for (int i = 0; i < ans.size(); i++)
	{
		cout << ans[i] << ' ';
	}
	
	
	return 0;
}

不知道我说清楚了没有呢😉