hihoCoder #1902 字符替换

解法

这题比赛时过的人很多，我却没思路，糊里糊涂写了个强联通分量，得了 80 分。

这题思路是这样的。

一个替换操作可以看做一个有向边，所以题目实际上给出了一个有向图 $G$，一个节点代表一个字母。

注意题目要求每个操作都必须执行一次。

关于自环

首先注意到自环是没有意义的，因此处理输入时把自环忽略掉。

这里需要特别说明自环的问题，题目描述中并没有说明 $X_i \ne Y_i$。不过似乎可以合理地假设输入中不存在 $X_i = Y_i$ 的操作。

有些 AC 的代码并没有判断自环，比如冰心水蜜桃的提交。当输入中有自环时，这个代码是有 BUG 的。

关于重边

实际上重边也是没有意义的，但是我们不必特别处理它。

用 $\mathsf{h}$ 表示 $G$ 中对应于字符 ‘h’ 的节点。

设字符 $x$ 在串 $S$ 中出现过且 $x$ 不是 ‘h’ 将 $x$ 出现的次数记做 $c_x$ 。则这 $c_x$ 个 $x$ 能转变为 ‘h’ 的充要条件是「图 $G$ 中存在一条从 $x$ 到 ‘h’ 的简单路径」。

证明：不失一般性，设 $x\to x_1 \to x_2 \to \mathsf{h}$ 是一条从 $x$ 到 ‘h’ 的简单路径，则我们可以按下述方法将 $x$ 变为 ‘h’。

首先将 $x$ 变为 $x_1$，这个操作用掉了 $(x\to x_1)$ 这条边；再将剩下的从 $x$ 发出的边全部用掉，这些边将不换改变当前的字符串，然后把所有从 $x$ 发出的边从图 $G$ 中删除。以此类推。

不难注意到若 ‘h’ 有出边，则上述论证是有问题的。

‘h’ 的出度为零的情形是平凡的。考虑 ‘h’ 的出度不为零的情形。此时若图 $G$ 中不存在「从 ‘h’ 到 ‘h’ 的回路」，则若初始字符串 $S$ 中有 ‘h’，则这些 ‘h’ 终将变成别的字符。因此在这种情况下我们可以将 ‘h’ 的所有出边先执行一遍，并把这些边从图 $G$ 中删除。

这样就完成了上述论证。

不过至此我们只是针对一个字符 $x$ 进行论证。实际上对多个字符，结论是一样的，证明留给读者。

现在来考虑图 $G$ 中存在从 ‘h’ 到 ‘h’ 的回路的情形。注意这样的回路一定不是自环。任取一个从 ‘h’ 到 ‘h’ 的回路 $C$，我们可以先把 'h' 变成回路 $C$ 上 'h' 的后继，得到一个新字符串 $S'$，并把图 $G$ 中其他的 ‘h’ 的出边删除。这样就把问题规约为上一段所描述的情形。

实现

我们需要判断的是，对于字符 $x\in S$ 且 $x\ne\mathsf{h}$，图 $G$ 中是否有一条从 $x$ 到 $\mathsf{h}$ 的简单路径，这可以通过 DFS 完成。另外当 $\mathsf{h}$ 的出度不为零时我们需要判断图 $G$ 中是否存在一条从 $\mathsf{h}$ 到 $\mathsf{h}$ 的回路。先进行DFS，确保字符串 $S$ 中所有字符都被访问过。遍历每一条以 $\mathsf{h}$ 为起点的边 $(\mathsf{h} \to x)$，判断图 $G$ 中是否存在从 $x$ 到 $\mathsf{h}$ 的简单路径。

也可以把边反向以后建图，这样只要对 $\mathsf{h}$ 调用一次 DFS 就可以了。

Implementation

#include <bits/stdc++.h>

using namespace std;

int main() {

    //freopen("main.in", "r", stdin);

    int n; cin >> n;

    string s; cin >> s;

    vector<int> cnt(26);

    for(auto ch: s) cnt[ch-'a']++;

    vector<vector<int>> g(26);

    vector<bool> to_h(26);

    bool flag = false;

    while (n--) {

        char x, y; cin >> x >> y;

        if (x != y) {

            g[y-'a'].push_back(x-'a');

            if(x == 'h') {

                to_h[y-'a'] = true;

                flag = true;

            }

        }

    }

    function<void(int)> dfs;

    vector<bool> vis(26);

    dfs = [&](int u) {

        vis[u] = true;

        for(auto v: g[u]) {

            if(!vis[v]) dfs(v);

        }

    };

    int h = 'h' - 'a';

    dfs(h);

    int ans = 0;

    for (int i = 0; i < 26; i++)

        if(vis[i]) ans += cnt[i];

    if (flag) {

        for (int i = 0; i < 26; i++)

            if (to_h[i] && vis[i]) {

                flag = false;

                break;

            }

        if (flag) ans -= cnt[h];

    }

    cout << ans << endl;

    return 0;

}

巴特西

hihoCoder #1902 字符替换

解法

关于自环

关于重边

实现

Implementation

最新文章

热门文章