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