http://m3.codeforces.com/contest/1296/problem/E2

2021-04-18 19:28

阅读：543

标签：scanf return line 交换选择 test 进入多少 amp

题目是说给你一串有小写字母构成的序列。

现在你可以给每个字符上色，注意是同一个字母可以有多种颜色，但是刚才1说的是字符，也i就是每一个位置就只有一种颜色，现在，你有一个能力就是将不同颜色的字符可以进行交换，问你需要多少种颜色才可以将原序列变成有序列；

输出颜色种数而且还要输出方案；

思路：

我们可以发现一个字符必须和他前面的比他大的字符进行交换，我们把这些比他的字符统称集合s，那么就得我们这个字符颜色得和他们不一样，那么颜色肯定选择集合里最小的从未出现的，就是mex懂吧。例如集合里的颜色有2 ，4 ，5，那此时的颜色肯定是1。那么我们维护每个字母的并查集，也就是从头遍历字符串，当前遇到字符串为id，我们就进入该字符的所属并查集，然后开始找到他的父亲，那么这个新字符就为父亲的颜色（x）+1；然后我们接下来就对小于id的字符的颜色（x，也就是和左边那个x同一个颜色）进行归并父亲到当前的x+1，这里的意思大白话来讲就是，后面出现比id小的为了和id不同只能选不同颜色，但是id的颜色本身就是按这个从1，2，3，4，5慢慢一步一步选过来的规则，所以后面比id小的字符只能比id的颜色+1；

#include
#define MAXN 200005
using namespace std;
int n,vis[26][MAXN],pre[26][MAXN],ans[MAXN];
char s[MAXN];
inline int find(int id,int x)
{
	return x == pre[id][x] ? x : pre[id][x] = find(id,pre[id][x]);
}
int main()
{
	scanf("%d%s",&n,s+1);
	for(int i = 0;i

http://m3.codeforces.com/contest/1296/problem/E2

标签：scanf return line 交换选择 test 进入多少 amp

原文地址：https://www.cnblogs.com/hgangang/p/12275277.html

上一篇：js dom一些操作，记录一下自己写的没有意义，可以简略翻过第八章

下一篇：k8s之web界面（Dashboard）从安装到应用

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：http://m3.codeforces.com/contest/1296/problem/E2
文章链接：http://soscw.com/index.php/essay/76349.html

亲，登录后才可以留言！

http://m3.codeforces.com/contest/1296/problem/E2

评论

热门文章

推荐文章

最新文章

置顶文章