CF1383A String Transformation 1解题报告

解题报告

CF1383A String Transformation 1解题报告：

更好的阅读体验

题意

• 给定两个字符串$A,B$，每次在$A$内选取若干个相同字符$x$改为另一个字符$y$，且保证$x<y$，求把$A$改成$B$的最小操作数。
• $1\leqslant |A|=|B|\leqslant 10^5$，多组数据。

分析

比较好玩的一道题。

首先特判掉存在$A_i>B_i$的情况，这样明显不合法。

我们考虑每个字符都进行一次操作（从$A_i$改成$B_i$），然后考虑怎么减少操作。

我们把一次字符$x$变为字符$y$的操作看成一条$x$到$y$的有向边，因为所有的边都满足$x<y$，所以这个图一定是一个DAG。

我们发现如果存在$a\rightarrow b,a\rightarrow c,b\rightarrow c$，那么实际上$a\rightarrow c$是没有必要的（直接借助$a\rightarrow b\rightarrow c$就好了）。

那么我们保留任意一颗生成树都是合法的，具体用一个并查集实现就可以了。

代码

#include<stdio.h>
#include<iostream>
using namespace std;
const int maxk=27;
int T,n,ans,flg;
int f[maxk];
string a,b;
int find(int x){
    return f[x]==x? x:f[x]=find(f[x]);
}
void merge(int x,int y){
    x=find(x),y=find(y);
    if(x!=y)
        f[x]=y,ans++;
}
int main(){
    scanf("%d",&T);
    while(T--){
        ans=flg=0;
        for(int i=1;i<=26;i++)
            f[i]=i;
        scanf("%d",&n);
        cin>>a>>b;
        for(int i=0;i<n;i++){
            if(a[i]>b[i]){
                flg=1;
                break;
            }
            merge(a[i]-96,b[i]-96);
        }
        if(flg==0)
            printf("%d\n",ans);
        else puts("-1");
    }
    return 0;
}