String Transformation 1

发表于 分类于 ，

    给出一个字符串a和b，每次可以选择a中一些字符相同的位置，假设这些位置的字符都是x，我可以将它们全部改为y，y必须比x字典序大。

    现在问最小多少次操作可以使得a字符串变为b。

String Transformation 1

Created by LXC on Mon Jul 3 00:11:56 2023

https://codeforces.com/problemset/problem/1383/A

ranting: 1700

tag: dsu, graphs, greedy, sortings, strings, trees, two pointers

problem

给出一个字符串a和b，每次可以选择a中一些字符相同的位置，假设这些位置的字符都是x，我可以将它们全部改为y，y必须比x字典序大。

现在问最小多少次操作可以使得a字符串变为b。

solution

对于A[i] > B[i]，没有答案

对于A[i] = B[i]，无需处理

只需关系A[i] < B[i]，我们将A[i]与B[i]分别看作图中的节点，然后将他们连接一条边。最后用图中节点个数减去图中的连通块个数就行。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    string A, B;
    cin >> A >> B;
    int st[200];
    memset(st, -1, sizeof(st));
    function<int(int)> ufind = [&](int x) {
        return st[x] == -1 ? x : st[x] = ufind(st[x]);
    };
    for (int i = 0; i < n; i++) {
        if (A[i] > B[i]) {
            cout << "-1\n";
            return;
        }
        if (A[i] < B[i]) {
            int fa = ufind(A[i]), fb = ufind(B[i]);
            if (fa != fb) {
                st[fa] = fb;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < 20; i++) {
        if (st[i + 'a'] != -1)
            ans++;
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}