Codeforces Round #824 (Div. 2) C - Phase Shift

（有点难以描述的）题意：给出一串字母，为每一个字母找一个映射，要求：1）所有的映射连起来形成一个且只有一个环；2）这个环内包含26个字母；3）映射后形成的新字符串字典序最小。

解：随便找两个26个字母的排列，再随便映射一下，可以发现：不管怎么样都是能形成环的，就是有几个的问题。题目要求只有一个，那就不要让新的字母映射到已经用过的字母上，可以用并查集实现。至于字典序尽量选小的就好。注意有字符串中26个不同字母的时候特判一下，因为到最后一个的时候不管怎么样前面的都用过一次了，这时候要把最后一个映射给没用过的。

可能还是看代码清楚一点：

#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;
}