前言
这是考试的时候放的一道题，考的时候没做出来。
调了一个晚上，心态爆炸，故作此篇。顺便，鸣谢泥土笨笨大佬的题解，给我的代码提供了强有力的对拍参照。
正题
首先看到题目，虽然字符串长度不超过 \(10^5\)，但是还是嫌多；再一看，至多只有52个字符。
那么从这个数据范围入手，思考可以按照变换前后的字符串给所有字符建一张图，其中的每一条有向边 \(a \rightarrow b\) 表示变换前的字符 \(a\) 变成了字符 \(b\)。接下来思考这个图可能有哪几种形式：
首先讨论 1：显然无解！一个字符不可能同时分裂成两种不同的字符。所以，我们得到了第一种无解的判定。
其次讨论形成一条链（2）：显然的，假设这条链有 \(n\) 条边，可以在 \(n\) 次转化后完成。
然后是一个环（3）：这就无法用 \(n\) 次完成了，必须先将某个点换成另一种字符，转化成一条有 \(n+1\) 个节点的链来做，所以要 \(n+1\) 次完成。
最后是生出尾巴的环（4）：刹一看，好像要 \(n+1\) 次完成；其实不用。把入度为 \(2\) 的点叫做点 \(a\)，尾巴上指向 \(a\) 的点是 \(b\)，环上指向 \(a\) 的是 \(c\)，可以现将点 \(c\) 换成字符 \(a\)，转换成一条 \(n\) 的链，最后 \(c\) 和 \(a\) 一起变成 \(b\)。所以也是只用 \(n\) 次。
当然，实际处理中这三种总是会一起出现（2,3,4），那么只要意义处理就行。
除了上面提到的第一种无解，还有一种情况就是转换后的字符串包含了所有的字符（\(52\) 个），并且和转换前的字符串不同。这时候，若画出图来应该是一个 \(52\) 个点的环，由于没有一个点可以变成另一个不同于这 \(52\) 个点的字符，所以也是无解。
那么代码就好实现了。不过这里有几点需要注意：
-
从入度小的点开始遍历图，而不是按照字母顺序。
-
判断一个字符是否要同事变成两个字符时，别忘了把它自己算上。
接下来是代码时间（写法丑陋，仅作参考）：
#include <bits/stdc++.h>
using namespace std;
int nxt[55],id[128],ans,T;
bool vis[55],has[55],noind[55];
char s1[100005],s2[100005];
void init() {
ans=0;
memset(nxt,0,sizeof(nxt));
memset(vis,false,sizeof(vis));
memset(has,false,sizeof(has));
memset(noind,true,sizeof(noind));
memset(s1,0,sizeof(s1));
memset(s2,0,sizeof(s2));
return ;
}
void addans(int p) {
if(vis[p]) return ;
int v=p,type=0;
vis[p]=true;
while(nxt[v]) {
type++,v=nxt[v];
if(v==p) {
ans+=type+1;
return ;
}
if(vis[v]) {
ans+=type;
return ;
}
vis[v]=true;
}
ans+=type;
return ;
}
int main() {
scanf("%d",&T);
for(int i=0;i<26;i++) id[i+'A']=i+1,id[i+'a']=i+27;
// for(int i='A';i<='Z';i++) cout<<char(i)<<":"<<id[i]<<endl;
// for(int i='a';i<='z';i++) cout<<char(i)<<":"<<id[i]<<endl;
while(T--) {
init();
scanf("%s%s",s1+1,s2+1);
int len=strlen(s1+1);
bool no_ans=false,same=true;
set<char> chset;
for(int i=1;i<=len;i++) {
int id1=id[s1[i]],id2=id[s2[i]];
if(has[id1]&&(id2!=nxt[id1])) {
no_ans=true;
break;
}
else {
has[id1]=true,nxt[id1]=id2;
if(id1!=id2) noind[id2]=false,same=false;;
}
chset.insert(s2[i]);
}
if(same) {
printf("0\n");
continue;
}
for(int i=1;i<=52;i++)
if(nxt[i]==i) nxt[i]=0;
for(int i=1;i<=52;i++)
if(noind[i]) addans(i);
for(int i=1;i<=52;i++)
if(has[i]) addans(i);
if(no_ans) printf("-1\n");
else if(chset.size()==52) printf("-1\n");
else printf("%d\n",ans);
}
return 0;
}
完结撒花！！！