ABC399.E题解

题目

E - Replace

算法标签: 动态规划, 组合数学, 图论

思路

首先考虑是否有解, 然后再考虑最小操作步数, 观察什么情况下无解, 如果对于$i,j$有$S_i=S_j$, 并且$T_i\ne T_j$一定无解(因为两个相等字符无法变为不同的字符), 假设有两个字符串$A=a,b,c,d,e,f,g,...,z$, 字符串$B=b,c,d,e,f,g,...,z,a$对于这两个字符串就无法通过操作使得两个字符串相等, 因为无论变换哪个字符, 都会使得串中出现两个相同的字符, 那么一定无解的

对于$A=a,b,c,d$和$B=b,c,d,a$是可以的, 因为可以引入一个外部字符, 首先将$A$变为$z,a,b,d$, 然后变后面的字符, 最后换回来, 类似于环状

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 26;

int n;
string s, t;
int p[N];

int find(int u) {
   
	if (p[u] != u) p[u] = find(p[u]);
	return p[u];
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n;
	cin >> s >> t;

	if (s == t) {
   
		cout << 0 << "\n";
		return 0;
	}

	vector<int> des(N, -1);
	for (int i = 0; i < n; ++i) {
   
		int sc = s[i] - 'a';
		int tc = t[i] - 'a';
		// 相同字母映射到不同字符说明矛盾
		if (des[sc] != -1 && des[sc] != tc) {
   
			cout << -1 << "\n";
			return 0;
		}
		des[sc] = tc;
	}

	int tag = 0;
	vector<int> tmp = des;
	sort(tmp.begin(), tmp.end());
	for (int i = 0; i < N; ++i) {
   
		// 存在字母未被映射
		if (tmp[i] != i) tag = 1;
	}

	if (tag == 0) {
   
		cout << -1 << "\n";
		return 0;
	}

	int ans = 0;
	vector<int> deg(N);
	for (int i = 0; i < N; ++i) p[i] = i;

	for (int i = 0; i < N; ++i) {
   
		// 字母i需要被映射
		if (des[i] != -1) {
   
			// 如果映射的目标不是自己需要操作
			if (des[i] != i) ans++;
			// 记录入度
			deg[des[i]]++;
			int fa1 = find(i), fa2 = find(des[i]);
			p[fa1] = fa2;
		}
	}

	// 将每个字母按照并查集根节点分组, 组成森林
	vector<vector<int>> trs(N);
	for (int i = 0; i < N; ++i) {
   
		trs[find(i)].push_back(i);
	}

	// 遍历森林的每个树
	for (auto tr: trs) {
   
		int has_cycle = 1;
		for (int ver : tr) {
   
			if (deg[ver] != 1) has_cycle = 0;
		}

		if (has_cycle && g.size() > 1) ans++;
	}

	cout << ans << "\n";
	return 0;
}