前言

這是考試的時候放的一道題，考的時候沒做出來。

調(diào)了一個晚上，心態(tài)爆炸，故作此篇。順便，鳴謝泥土笨笨大佬的題解，給我的代碼提供了強有力的對拍參照。

正題

首先看到題目，雖然字符串長度不超過 \(10^5\)，但是還是嫌多；再一看，至多只有52個字符。

那么從這個數(shù)據(jù)范圍入手，思考可以按照變換前后的字符串給所有字符建一張圖，其中的每一條有向邊 \(a \rightarrow b\) 表示變換前的字符 \(a\) 變成了字符 \(b\)。接下來思考這個圖可能有哪幾種形式：

首先討論 1：顯然無解！一個字符不可能同時分裂成兩種不同的字符。所以，我們得到了第一種無解的判定。

其次討論形成一條鏈（2）：顯然的，假設這條鏈有 \(n\) 條邊，可以在 \(n\) 次轉化后完成。

然后是一個環(huán)（3）：這就無法用 \(n\) 次完成了，必須先將某個點換成另一種字符，轉化成一條有 \(n+1\) 個節(jié)點的鏈來做，所以要 \(n+1\) 次完成。

最后是生出尾巴的環(huán)（4）：剎一看，好像要 \(n+1\) 次完成；其實不用。把入度為 \(2\) 的點叫做點 \(a\)，尾巴上指向 \(a\) 的點是 \(b\)，環(huán)上指向 \(a\) 的是 \(c\)，可以現(xiàn)將點 \(c\) 換成字符 \(a\)，轉換成一條 \(n\) 的鏈，最后 \(c\) 和 \(a\) 一起變成 \(b\)。所以也是只用 \(n\) 次。

當然，實際處理中這三種總是會一起出現(xiàn)（2,3,4），那么只要意義處理就行。

除了上面提到的第一種無解，還有一種情況就是轉換后的字符串包含了所有的字符（\(52\) 個），并且和轉換前的字符串不同。這時候，若畫出圖來應該是一個 \(52\) 個點的環(huán)，由于沒有一個點可以變成另一個不同于這 \(52\) 個點的字符，所以也是無解。

那么代碼就好實現(xiàn)了。不過這里有幾點需要注意：

• 從入度小的點開始遍歷圖，而不是按照字母順序。

• 判斷一個字符是否要同事變成兩個字符時，別忘了把它自己算上。

接下來是代碼時間（寫法丑陋，僅作參考）：

#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;
}

完結撒花！！！