题解：P10293 [CCC 2024 J4] Troublesome Keys

· · 题解

题目分析

定义两个字符串，其中字符串 a 为按下按键的字符串，字符串 b 为电脑上显示的错误的字符串。然后梳理下这两个特殊的按键的特点：

那么，我们可以通过字母在两个字符串中出现次数的不同来找到突破口。

定义两个数组，其中 sa[0] \sim sa[25] 和 sb[0] \sim sb[25] 分别表示 26 个小写字母分别在 a 串和 b 串中出现的次数。由于可能会按下过安静的按键，因此两个字符串的串长可能不同，用 lena 和 lenb 表示两串串长，那么一定满足 lena \ge lenb。所以在计数的时候稍微注意一下就可以了，程序如下：

for(int i=0;i<lena;i++){
    sa[a[i]-'a']++;
    if(i<lenb) sb[b[i]-'a']++;
}

在刚才的分析中，我们会发现：如果某个字母在 a 串中没有出现，但是在 b 串中出现了，那一定是愚蠢的按键在按下时显示的错误字母。但是，在 a 串中出现，在 b 串中没有出现的字母，可能是愚蠢的按键也可能是安静的按键（仅当 lena >lenb 时），那么我们除了要记录这两个字母，还需要再确定一下具体谁是谁。

再次对两个字符串进行枚举，当遇到 a[i] 和 b[i] 不同时，判断一下此时的 b[i] 是不是前面我们已经获取到的错误字母：如果是，由于题目中说两个特殊按键不会连续按下，就是说不会有先按安静键再按愚蠢键的这种情况，那么 a[i] 就是愚蠢的按键键入时的字母了；如果不是，那么 a[i] 就是安静的按键了！

代码

#include<bits/stdc++.h>
using namespace std;

string a,b;
int lena,lenb;
int sa[30],sb[30];
char yc1='$',yc2,aj='-';

int main()
{
    cin>>a>>b;
    lena=a.length();
    lenb=b.length();
    for(int i=0;i<lena;i++)
    {
        sa[a[i]-'a']++;
        if(i<lenb) sb[b[i]-'a']++;
    }

    for(int i=0;i<=25;i++)
    {
        if(sa[i]==0&&sb[i]!=0) yc2=(char)('a'+i); //a中未出现 b中出现了 一定是错误的那个 
        if(sa[i]!=0&&sb[i]==0) //不能确定是愚蠢的还是安静的
        {  
            if(yc1=='$') yc1=(char)('a'+i); 
            else aj=(char)('a'+i);
        }
    }

    if(lena!=lenb){ //按下过安静键 
        for(int i=0;i<lena;i++)
        {
            if(a[i]!=b[i])
            {
                if(b[i]==yc2&&a[i]==aj||b[i]!=yc2&&a[i]==yc1) //记录反了的情况
                    swap(yc1,aj);
                break;
            }
        } 
    } 

    cout<<yc1<<" "<<yc2<<endl;
    cout<<aj;
    return 0;
}