CF1383A String Transformation 1 题解

题意：

给定两个长度相等的字符串 $A,B$ ，最小化操作数使得 $A$ 变成 $B$ 。

一次操作定义为：在 $A$ 中选取若干个相同的字母 $x$ ，并将所有 $x$ 改成字母 $y(x<y)$

输入格式：

多组数据，$n=|A|=|B|$ ，然后两行 $A,B$ 。

输出格式：

每组数据输出一行，表示最小花费。

数据范围：

$1\le \sum |A|, \sum |B| \le 10^5$ 。

依次考虑每个 $a_i,b_i$ 。如果存在 $a_i > b_i$ 一定无解；同理若 $a_i=b_i$ 直接跳过 $i$ 。

否则若 $a_i < b_i$ ，如果 $a_i$ 不能到达 $b_i$ ，则连一条 $a_i$ 到 $b_i$ 的有向边并使答案加 $1$ 。

如果 $a_i$ 能到达 $b_i$ ，这意味着我们可以让 $a_i$ 沿着 $a_i \leadsto b_i$ 变换，并且这不会增加花费。

因为 $\forall (u,v) \in \langle a_i \leadsto b_i\rangle$ ，一定存在一个 $u \to v$ 的变换。由连边方式易知。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))

char a[N],b[N];
int n,f[33],sz[33];
void init(int n) { for(int i=1; i<=n; i++) f[i] = i, sz[i] = 1; }
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
bool merge(int u,int v)
{
    int x = find(u), y = find(v);
    if(x == y) return 0;
    if(sz[x] > sz[y]) swap(x,y);
    f[x] = y; sz[y] += sz[x]; return 1;
}
void solve()
{
    cin >> n; init(26);
    cin >> (a+1) >> (b+1);
    bool ok = 1; int res = 0;
    for(int i=1; i<=n; i++)
    {
        if(a[i] > b[i]){ ok = 0; break; }
        res += merge(a[i] - 'a' + 1, b[i] - 'a' + 1);
    }
    if(ok) cout << res << '\n'; else cout << "-1\n";
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int _Q; cin >> _Q; while(_Q--) solve();
    return 0;
}