USACO23JAN Find and Replace S(洛谷 P9013)题解
分析
题意非常简洁,即问你通过一系列的字符替换,最少花多少步能把一个 串变成 串。
拿到题之后,可以先从样例开始分析。
从 这个样例可以发现,不可能同时把某个字符替换成两个字符(),会起冲突。
那直接统计 的个数(给串去重之后,即不存在 这种)就可以作为答案了吗?可以从最后一个样例发现不是这样的。
环的处理
因为最后一个样例中, 的部分是一样的。我们直接考虑 的变换。如果直接执行 的操作,会得到一个 的串。这个时候就有了和前面一样的问题,不能将其转换成 。执行 也是同理。
解决的办法就是先执行 再处理 。( 是任意别的字符)
是否所有“相互依赖”的情况下,都可以通过这种方式解决呢?我们可以再思考一个大一点的样例 ,用图(创建 的边,并且去掉重边和自环)的方式表示出来会更加清晰:
graph LR A --> B B --> C C --> D D --> A
可以发现,这是一个环。无论我们先执行哪种 的变换,都会需要再执行 的变换。因为 希望能变成别的。这个时候,先前 会跟着一起被变成 。
不过,如果能“化环为链”,就可以解决问题了。比如我们可以先执行 ,这个链就会变成:
graph LR x --> B B --> C C --> D D --> A
这样,就有一个执行 后,不用再执行 的地方了。即 (执行完之后, 也符合这个条件,我们倒着的按照链的顺序就可以把整条串转换为目标)。
从这两个例子可以看出,在一般的情况下,一个操作能把环转化为链,或者把链的长度(边的数量)减少 1。
所以答案的数量就是(环的数量 + 链的长度)了吗?
两种特例
1
首先,化环为链的操作需要一个不在环中出现的字符,假设环包含了字符集中所有的字符,我们是不能处理的。
假设我们的字符集只有 这四个字符,那处理下面这个例子时候,就会发现问题。
graph LR A --> B B --> C C --> D D --> A
不管先把 变成什么字符,这个字符之后都会再经历最少一次的变换,导致 不能被转换成目标字符 。
当然,我们处理不了的情况不一定要求整张图中只有一个环,只要符合:
- 所有节点都在环里
- 字符集中的所有字符都被用到了
就不能处理了,比如下面这个例子,有两个环还是不行(字符集为 ):
graph LR A --> B B --> A C --> D D --> C
2
考虑这样一个输入:
graph LR A --> B B --> C C --> D D --> A E --> B F --> E
我们可以在一个操作内即化环为链,又把链的长度减少 1。观察到 和 都希望能被转换成 。从字符转换的角度来说, 和 的最终结果和操作步数都是一样的。但是第二种方法在执行 时,也把环中的一个字符转换成了环外的字符,将环化成了链。
能这么做的前提条件是,有多个环外字符希望变成环内的一个字符。更严谨的说就是环中某个节点的入度大于等于 2。
到此为止,所有的情况都基本分析好了,可以写出以下的总结(括号中的为实际判断方法):
- 一个字符希望转换成多个字符是无解的。(节点出度最多为 1)
- 所有节点(所有可能的字符)全部在环中是无解的 (每种字符的入度都为 1)。
- 答案 = 边的数量 + 绝对环的数量(环中每个节点的入度出度都为 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);
}
}