头部背景图片
Decaku 's Blog |
Decaku 's Blog |

codeforces 1296E String Coloring

题意:给你一个字符串,让你对每个下标染一个颜色,然后如果两个下标相邻且
被染成了不同的颜色就可以交换这两个下标对应的字母,交换操作可以执行任意次
要求最后能够得到一个字典序单调不降的字符串,询问最少染色数。


$考虑染完色后,字符串的一个子序列,这个子序列都被染成了相同的颜色,那就 \\
要求这个子序列字典序也是单调非降的,因为同种颜色是无法交换的,问题就等价于 \\
把字符串分解成最少的单调非降的子序列的个数,这是一个经典题,结论是等价于 \\
求原字符串的最长下降子序列长度。根据Dilworth定理,对于一个偏序集,最少链划分 \\
等于最长反链的长度。字符集大小只有26,转移的时候暴力即可,否则可以用树状数组 \\
维护,输出第i个字母染色颜色等价于以i结尾的最长下降序列长度。 \\
$

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
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define pii pair<ll,ll>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(ll i=a;i<=(ll)b;++i)
#define per(i,a,b) for(ll i=a;i>=(ll)b;--i)
#define ll long long
#define lowbit(x) ((x)&(-x))

const int maxn=2e5+5;
int n,dp[26],ed[maxn];
int main()
{
cin>>n;
string s;cin>>s;
int cnt=1;
dp[s[0]-'a']=1;ed[0]=1;
rep(i,1,n-1)
{
int c=s[i]-'a';
int mx=0;
rep(j,c+1,25) mx=max(dp[j],mx);
ed[i]=mx+1; dp[c]=max(dp[c],mx+1);
cnt=max(cnt,dp[c]);
}
cout<<cnt<<"\n";
rep(i,0,n-1) cout<<ed[i]<<" ";
cout<<"\n";
}
avatar Decaku 菜菜菜