题解：AT_abc370_c [ABC370C] Word Ladder

zeroflows · 2024-09-08 08:58:43 · 题解

题目传送门

简要题意

给两个序列 S 和 T，输出的第一个数是它能改变的总个数，后面跟着的第 i 个是改变 i 个数之后，字典序最小的结果。

思路

当 S 与 T 相等的话，那就无法改变了，直接输出 0。

对于总数只要 T_i \ne S_i 那它就可以改，所以只要 T_i \ne S_i 答案就加一。

• 要让字典序最小，那我们从前面开始枚举，只要 T_i < S_i 就替换，然后输出。
• 否则如果 T_i > S_i 记录位置。等枚举完后，从后往前把记录的位置也换了。

代码

#include<bits/stdc++.h>
using namespace std;
char s[1000],t[1000],ss[1000];
int n,qw,h[100000000];
main()
{
    ios::sync_with_stdio(false);
    cin.tie(),cout.tie();
    cin>>s>>t;
    if(s==t)
    {
        cout<<0;
        return 0;
    }
    n=qw=strlen(s);
    for(int i=0;i<n;i++)
    ss[i]=s[i];
    int qq=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]==t[i])
            continue;
        qq++;
    }
    cout<<qq<<endl;
    qq=0; 
    for(int i=0;i<n;i++)
    {
        if(s[i]==t[i])
            continue;
        if(s[i]<t[i])
        {
            h[++qq]=i;
            continue;
        }
        s[i]=t[i];
        cout<<s<<endl;
    }
    for(int i=qq;i>=1;i--)
    {
        int j=h[i];
        s[j]=t[j];
        cout<<s<<endl;
    }
}