Codeforces Round #659 (Div. 2) C、String Transformation 1（思维+set）

思路：

在相对应的位置，只要 $a$ 串上的字母大于 $b$ 串上的字母，那么无解，否则一定有解。
要找到最小的步数，其实最大步数也就20吧。
我们首先从小的开始选择字母，对于选定的字母，我们可以把它变成什么呢？选择的字母都有其要变成的值，我们让他们都变成要变成字母里的最小的一个，比如：aaa–>cdg，那么选择的字母是 $'a'$，把它变成 $'c'$ ，然后把其都变成 $'c'$。
具体实现使用 $set$ 来维护的，每个字母维护一个 $set$,从小到大枚举，然后每次取当前字母要变换到的最小字母，操作次数++，然后将这些字母变成最小字母，其对应的操作就是把其余的放入到最小字母的那个set里。
复杂度 $O(n*log20)$

参考代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int man = 2e5+10;
#define IOS ios::sync_with_stdio(0)
#define ull unsigned ll
#define uint unsigned
#define pai pair<int,int>
#define pal pair<ll,ll>
#define IT iterator
#define pb push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);++i)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);--i)
#define endl '\n'
#define ll long long
const ll mod = 1e9+7;
char s1[man],s2[man];

signed main() {
    #ifndef ONLINE_JUDGE
        //freopen("in.txt", "r", stdin);
        //freopen("out.txt","w",stdout);
    #endif
    int t;cin >> t;
    while(t--){
        int n;cin >> n;
        scanf("%s%s",s1+1,s2+1);
        bool f = 1;
        for(int i = 1;i <= n;++i){
            if(s1[i]>s2[i]){
                f = 0;
                break;
            }
        }
        if(!f){
            cout <<"-1\n";
            continue;
        }
        int ans = 0;
        set<int>s[25];
        for(int i = 1;i <= n;++i){
            if(s1[i]!=s2[i]){//只把不同的放入
                s[s1[i]-'a'].insert(s2[i]-'a');
            }
        }
        for(int i = 0;i < 20;++i){
            if(s[i].size()==0)continue;
            int minn = *s[i].begin();
            s[i].erase(minn);
            ans++;
            for(auto it:s[i]){
                s[minn].insert(it);
            }
        }
        printf("%d\n",ans);
    }   
    return 0;
}

本文地址：https://blog.csdn.net/weixin_43571920/article/details/107575713