题解 CF1383A 【String Transformation 1】

whiteqwq · 2021-01-23 13:23:22 · 题解

CF1383A String Transformation 1解题报告：

更好的阅读体验

题意

• 给定两个字符串A,B，每次在A内选取若干个相同字符x改为另一个字符y，且保证x<y，求把A改成B的最小操作数。

分析

比较好玩的一道题。

首先特判掉存在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;
}