题目链接

博客中观看体验更佳

分析

题意非常简洁,即问你通过一系列的字符替换,最少花多少步能把一个 ss 串变成 tt 串。

拿到题之后,可以先从样例开始分析。

BBCABC\texttt{BBC} \to \texttt{ABC} 这个样例可以发现,不可能同时把某个字符替换成两个字符(BBAB\texttt{BB} \to \texttt{AB}),会起冲突。

那直接统计 sitis_i \ne t_i 的个数(给串去重之后,即不存在 s=AA,t=BBs = \texttt{AA}, t = \texttt{BB} 这种)就可以作为答案了吗?可以从最后一个样例发现不是这样的。

环的处理

因为最后一个样例中,CD\texttt{CD} 的部分是一样的。我们直接考虑 ABBA\texttt{AB} \to \texttt{BA} 的变换。如果直接执行 AB\texttt{A} \to \texttt{B} 的操作,会得到一个 BB\texttt{BB} 的串。这个时候就有了和前面一样的问题,不能将其转换成 BA\texttt{BA}。执行 BA\texttt{B} \to \texttt{A} 也是同理。

解决的办法就是先执行 ABxB\texttt{AB} \to x\texttt{B} 再处理 xBBAx\texttt{B} \to \texttt{BA}。(xx 是任意别的字符)

是否所有“相互依赖”的情况下,都可以通过这种方式解决呢?我们可以再思考一个大一点的样例 ABCDBCDA\texttt{ABCD} \to \texttt{BCDA},用图(创建 sitis_i \to t_i 的边,并且去掉重边和自环)的方式表示出来会更加清晰:

可以发现,这是一个环。无论我们先执行哪种 xyx \to y 的变换,都会需要再执行 yzy \to z 的变换。因为 yy 希望能变成别的。这个时候,先前 xx 会跟着一起被变成 zz

不过,如果能“化环为链”,就可以解决问题了。比如我们可以先执行 Ax\texttt{A} \to x,这个链就会变成:

这样,就有一个执行 xyx \to y 后,不用再执行 yzy \to z 的地方了。即 DA\texttt{D} \to \texttt{A} (执行完之后, CD\texttt{C} \to \texttt{D} 也符合这个条件,我们倒着的按照链的顺序就可以把整条串转换为目标)。

从这两个例子可以看出,在一般的情况下,一个操作能把环转化为链,或者把链的长度(边的数量)减少 1。

所以答案的数量就是(环的数量 + 链的长度)了吗?

两种特例

1

首先,化环为链的操作需要一个不在环中出现的字符,假设环包含了字符集中所有的字符,我们是不能处理的。

假设我们的字符集只有 AD\texttt{A} \sim \texttt{D} 这四个字符,那处理下面这个例子时候,就会发现问题。

不管先把 A\texttt{A} 变成什么字符,这个字符之后都会再经历最少一次的变换,导致 A\texttt{A} 不能被转换成目标字符 B\texttt{B}

当然,我们处理不了的情况不一定要求整张图中只有一个环,只要符合:

  1. 所有节点都在环里
  2. 字符集中的所有字符都被用到了

就不能处理了,比如下面这个例子,有两个环还是不行(字符集为 AC\texttt{A} \sim \texttt{C}):

2

考虑这样一个输入:ABCDEFBCDABE\texttt{ABCDEF} \to \texttt{BCDABE}

我们可以在一个操作内即化环为链,又把链的长度减少 1。观察到 A\texttt{A}E\texttt{E} 都希望能被转换成 B\texttt{B}。从字符转换的角度来说,AB&EB\texttt{A} \to \texttt{B} \And \texttt{E} \to \texttt{B}AE&EB\texttt{A} \to \texttt{E} \And \texttt{E} \to \texttt{B} 的最终结果和操作步数都是一样的。但是第二种方法在执行 AE\texttt{A} \to \texttt{E} 时,也把环中的一个字符转换成了环外的字符,将环化成了链。

能这么做的前提条件是,有多个环外字符希望变成环内的一个字符。更严谨的说就是环中某个节点的入度大于等于 2。

到此为止,所有的情况都基本分析好了,可以写出以下的总结(括号中的为实际判断方法):

  1. 一个字符希望转换成多个字符是无解的。(节点出度最多为 1)
  2. 所有节点(所有可能的字符)全部在环中是无解的 (每种字符的入度都为 1)。
  3. 答案 = 边的数量 + 绝对环的数量(环中每个节点的入度出度都为 1)

这里第二点的判断方法可以稍微解释一下:

没有选择使用出度是考虑到了环连着树的情况,参考上图。

代码实现

实现的时候找环的部分需要注意一下,其他部分都比较简单。

我们知道 tarjan 算法就可以判环,不过这道题可以用“简化版”的 tarjan,不用记录访的时间戳。我们把 dfs 的时候把所有访问过的节点从队尾压入一个双向队列。

如果我们开始 dfs 的时候是从一个环上的点进入的,之后一定会访问到一个和队头一样的节点。这个时候把所有在队头和队尾之间的节点都弹出,就得到了环中的所有节点。

如果我们发现某个节点之前访问过,但是并不在队头,就可以确定队列中的节点都不是“绝对环”,因为有树连着他(参考上图,如果从 F 节点开始搜就会出现这种情况)。

#include <bits/stdc++.h>
using namespace std;

const int CHSZ = 52;  // char set size
int out[CHSZ + 1];   // 出度只能有一个
int lpid[CHSZ + 1];  // 环的 id,不知道 -> -1,不是环 -> 0,是环 -> 1,2,3...
enum LP_STAT { UNKNOWN = -1, NOT_ABS_LP = 0 };
deque<int> vised_dq;   // 用于在找环的时候储存信息
bool vised[CHSZ + 1];  // 用于在找环的时候储存信息

set<int> in_nds[CHSZ + 1]; // in nodes,入度可以有多个
int in1_cnt = 0; // 入读为 1 的节点的数量

int abs_lp_cnt = 0;  // 绝对环数,即环不连树的环数
int diff_chs = 0;

void init() {
    memset(out, 0, sizeof(out));
    fill(lpid, lpid + CHSZ + 1, UNKNOWN);
    vised_dq.clear();
    memset(vised, 0, sizeof(vised));
    for (int i = 0; i <= CHSZ; i++) in_nds[i].clear();
    in1_cnt = 0;
    abs_lp_cnt = 0;
    diff_chs = 0;
}

inline int ch2id(char x) {
    // char to id
    if (x >= 'a' && x <= 'z') return x - 'a' + 1;
    if (x >= 'A' && x <= 'Z') return x - 'A' + 27;
    return -1;
}

bool check_loop_connect_to_tree() {
    for (int cur : vised_dq) 
        if (in_nds[cur].size() >= 2) 
            // 有树连这个环
            return true;
    return false;
}

void fill_lpid_in_vised_dq(int val) {
    for (int cur : vised_dq)
        lpid[cur] = val;
    vised_dq.clear();
}

void mark_loop(int cur) {
    if (vised[cur] && vised_dq.front() != cur) {
        // 从一个树进入的环,不是绝对环
        fill_lpid_in_vised_dq(NOT_ABS_LP);
        return;
    }
    vised[cur] = true;
    if (out[cur] == cur) {
        // 没有出度,找到一个链
        fill_lpid_in_vised_dq(NOT_ABS_LP);
        return;
    }

    if (vised_dq.size() && vised_dq.front() == cur) {
        // 找到环
        if (!check_loop_connect_to_tree()) {
            // 如果环不连树
            abs_lp_cnt++;
            fill_lpid_in_vised_dq(abs_lp_cnt);
        } else {
            fill_lpid_in_vised_dq(NOT_ABS_LP);
        }
        return;
    }
    vised_dq.push_back(cur);
    mark_loop(out[cur]);
}

void solve(const string& origs, const string& tars) {
    // orig str -> tar str
    init();
    for (int i = 0; i < origs.size(); i++) {
        int och = ch2id(origs[i]);
        int tch = ch2id(tars[i]);
        if (out[och] && out[och] != tch) {
            // 如果 o 串已经有要转换的字符,但是不是 t
            // 串的字符,那么会产生多对一
            cout << -1 << '\n';
            return;
        }
        if (!out[och]) {
            out[och] = tch;
            in_nds[tch].insert(och);
            if (och != tch) 
                diff_chs++;
        }
    }
    for (int i = 1; i <= CHSZ; i++) {
        if (in_nds[i].size() == 1) 
            in1_cnt++; // 统计入度为 1 的节点数量
    }
    for (int i = 1; i <= CHSZ; i++) {
        if (out[i] && lpid[i] == UNKNOWN) {
            // 标记环
            vised_dq.clear();
            memset(vised, 0, sizeof(vised));
            mark_loop(i);
        }
    }
    if (origs != tars && in1_cnt == CHSZ) {
        // 判断是否全部都在环中,用入度为 1 的数量来判断
        cout << -1 << '\n';
        return;
    }
    cout << diff_chs + abs_lp_cnt << '\n';
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        string origs, tars;
        cin >> origs >> tars;
        solve(origs, tars);
    }
}