[USACO23JAN] Find and Replace S

Gusare / 2024-11-10 / 原文

前言

完全不会() 看题解过的
题解指路: 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. 孤立点
  2. 纯环
  3. 有入度的环

对链和有入度的环来说,最小操作次数即为边数。
对纯环来说,必须有个辅助点来帮助转移,最小操作次数即边数+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++)