前言
完全不会() 看题解过的
题解指路: https://www.luogu.com.cn/problem/solution/P9013（luogu题解)
看的是 @泥土笨笨 的题解,非常清晰!
下文是我对这个题目的复盘总结（）感觉不如原题解那么专业
题目大意
给两个长度相等的字符串s和t，两个字符串都只由大写和小写字母组成。
每次操作可以将s中同一种字母统一变换为另一种字母。
问从s变换到t的最小操作次数，若不可能实现，输出-1。
思路
因为是一种字母统一变换到另一种。
很容易想到一种无解的情况，即一种字母变化成了两个或两个以上的字母。
对于s中某个字母si要变换成t中某字母ti，如果按照si->ti建一张图，重边和自环都不建边，那么这张图是有52个点的有向图。
由无解情况可知，一个有解的图，肯定保证一个点至多有一条出边。
也可以知道，s中字母种类必然大于等于t。
图中可能会有三种结果：
- 孤立点
- 纯环
- 链
- 有入度的环
对链和有入度的环来说，最小操作次数即为边数。
对纯环来说，必须有个辅助点来帮助转移，最小操作次数即边数+1，并且这个辅助点不能在t中出现。
如果t的字母种类小于52，那么辅助点一定存在。
如果t中已经出现了所有的字母，因为s中字母种类必然大于等于t，所以s也必然有所有的字母。所以s和t建图只形成一个纯环。
设t[j]为辅助点，s[i]->t[j]->e[s[i]]，但t[j]->e[t[j]]，同一个辅助点有两个映射，出现了一对多的情况，无解。
故除非s和t完全相等，否则无解。
这也是第二个无解的情况：t中出现所有的字母，但s与t不同。
所以排除掉这两个无解的情况，可以求解了。
对于纯环，链和有入度的环，必然存在入度为0的点。
由这些入度为0的点进入，可以把这三个情况的点全部标记一遍。
剩下的没有标记过的，就是存在于纯环上的点。
答案=边数+纯环的个数
代码
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
ll e[150],in[150];
bool vis[150];
string s,t;
void solve();
void init();
void dfs(ll x);
void dfs(ll x){
vis[x]=true;
if(e[x]!=0 && !vis[e[x]]){ //下一个点有出边 且 没有被访问过
dfs(e[x]); //下个点可以标记
}
//否则退出dfs
}
void init(){ //初始化
for(ll i=0;i<150;i++){
e[i]=0; //清空图
in[i]=0; //清空入度
vis[i]=false; //抹去所有点的访问记录
}
}
void solve(){
cin>>s>>t;
ll n=s.size();
s=' '+s;
t=' '+t;
set<char> st;
init();
//非法1:si对应多种ti
for(ll i=1;i<=n;i++){
if(e[s[i]]==0){
e[s[i]]=t[i];
} else if(e[s[i]]!=t[i]) {
cout<<-1<<'\n';
return ;
}
st.insert(t[i]);
}
//非法2:t集齐了52个字母,但s!=t
if(st.size()==52 && s!=t){
cout<<-1<<'\n';
return ;
}
//去掉自环和重边,重新建图;建图同时统计边数
ll ans=0;
init(); //多组测试样例,要对入度和出度初始化
for(ll i=1;i<=n;i++){
if(e[s[i]]==0 && s[i]!=t[i]){ //e[s[i]]==0 该点无连接 (2)s[i]!=t[i]去掉自环
e[s[i]]=t[i]; //建边
in[t[i]]++; //更新入度
ans++; //边数自增
}
}
//统计纯环数量
//思路很巧妙,运用了"孤点,链以及有入度的环必存在入度为0的点"这个特性
//将这些点的vis都设置为true,剩下的点都存在在纯环里
//找到纯环上的点,再遍历环,更新vis,即可得到纯环的个数
//预处理:将孤点,链以及有入度的环的所有点都标记为访问过
for(ll i='a';i<='z';i++){
if(in[i]==0){
dfs(i);
}
}
for(ll i='A';i<='Z';i++){
if(in[i]==0){
dfs(i);
}
}
//正式统计纯环数量
for(ll i='a';i<='z';i++){
if(!vis[i]){
dfs(i);
ans++;
}
}
for(ll i='A';i<='Z';i++){
if(!vis[i]){
dfs(i);
ans++;
}
}
cout<<ans<<'\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ll t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
收获
- 切身体会到了这道题的思维难度，感觉最难的点在第二个非法情况的判断（我太菜了）
- 利用入度为0的特性来统计纯环数量的思路很妙
- WA了一发，因为前面的init()忘记加了
- 直接开150的空间，然后让ascii码值直接做下标很妙
- 第一次见到这种遍历方法：
for(ll i='a';i<='z';i++)