自动搬运

查看原文

来自洛谷，原作者为

	superballll **

搬运于2025-08-24 22:56:38，当前版本为作者最后更新于2024-04-02 00:58:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目分析

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

• 愚蠢的按键：按下的字母不会出现，但是会出现一个没有按下过的字母。即按下的字母在字符串 $a$ 中出现了，但是在字符串 $b$ 中没有出现过。并且，显示的字母在字符串 $b$ 中出现了，但是在字符串 $a$ 中没有出现过。
• 安静的按键：按下的字母不会出现，而且也不会出现其他的字母。即在字符串 $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;
}