(有点难以描述的)题意:给出一串字母,为每一个字母找一个映射,要求:1)所有的映射连起来形成一个且只有一个环;2)这个环内包含26个字母;3)映射后形成的新字符串字典序最小。
解:随便找两个26个字母的排列,再随便映射一下,可以发现:不管怎么样都是能形成环的,就是有几个的问题。题目要求只有一个,那就不要让新的字母映射到已经用过的字母上,可以用并查集实现。至于字典序尽量选小的就好。注意有字符串中26个不同字母的时候特判一下,因为到最后一个的时候不管怎么样前面的都用过一次了,这时候要把最后一个映射给没用过的。
可能还是看代码清楚一点:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; #define ll long long #define maxx 200005 #define inf 1000000009; #define mod 998244353 char s[maxx]; int fa[30]; int find(int x){ return fa[x]==x?x:fa[x]= find(fa[x]); } signed main(){ int T; cin>>T; while(T--){ int n; scanf("%d",&n); scanf("%s",s); char cnt[30]={0}; string ans; for(int i=0;i<n;i++){ if(!cnt[s[i]-'a']){ ans+=s[i]; cnt[s[i]-'a']++; } } for(int i=0;i<26;i++) fa[i]=i; int res[30]={0},cnt2[30]={0}; for(int i=0;i<ans.length();i++){ for(int j=0;j<26;j++){ if(find(ans[i]-'a')!=find(j)&&!cnt2[j]){ res[ans[i]-'a']=j; cnt2[j]++; fa[ans[i]-'a']=j; break; } } } if(ans.length()==26){ for(int i=0;i<26;i++){ if(!cnt2[i]){ res[ans[ans.length()-1]-'a']=i; break; } } } for(int i=0;i<n;i++) s[i]=res[s[i]-'a']+'a'; printf("%s\n",s); } return 0; }View Code
标签:26,映射,int,Shift,字母,Codeforces,fa,Phase,define From: https://www.cnblogs.com/capterlliar/p/16756374.html