解法

這題比賽時過的人很多，我卻沒思路，糊里糊涂寫了個強聯通分量，得了 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; }

轉載于:https://www.cnblogs.com/Patt/p/10170820.html

總結

以上是生活随笔為你收集整理的hihoCoder #1902 字符替换的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。