自动搬运

查看原文

来自洛谷，原作者为

	David_yang 没有一根棒棒糖解决不了的事情，如果有，就再来一根

搬运于2025-08-24 22:45:20，当前版本为作者最后更新于2024-02-03 16:17:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

传送门

第五篇题解，如有不妥请忽视指出。

题目大意：

给定两个字符串，求第一个字符串能否经过翻转得到第二个字符串（每次翻转的长度必须为奇数）。

算法：

字符串（其实算不上算法）。

解析：

首先拿到题，我觉得题目太长，懒得看。撇了一眼样例解释，原来是要通过翻转使两个字符串相同，可是我忽略了一个重要信息：每次翻转的长度必须为奇数！！！

于是，我天真地把代码交上去，还觉得这题太简单，难度介于澄和红之间。交上去一看，首先被 $246$ 个测试点所惊艳，然后一看，怎么会有 WA？而且对了那么多，只错了几个，由于捆绑测试，我获得了 $1000000000 \bmod 1000$ 分的好成绩。代码就不展示了……

我还没发现错误，只觉得某个地方没想到，加了点东西交上去绿的多了一点，但依然获得了 $1000000000 \bmod 1000$ 分的好成绩。改进后的代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[30],b[30];
string s,t;
int main()
{
	scanf("%d",&n);
	cin>>s>>t;
	for(int i=0;i<n;i++)
	{
		a[s[i]-'a']++;        		//我发现我忘记计算里面的个数，个数一样才能TAK。为什么把错误代码摆出来，是因为这一段加上奇偶判断就是AC代码中的最重要部分。
	}
	for(int i=0;i<n;i++)
	{
		b[t[i]-'a']++;
	}
	for(int i=0;i<=26;i++)
	{
		if(a[i]!=b[i])
		{
			printf("NIE");
			return 0;
		}
	}
	for(int i=0;i<n;i++)
	{
		if(t.find(s[i])==string::npos)
		{
			printf("NIE");
			return 0;
		}
	}
	printf("TAK");
	return 0;
}

我只好仔细读题，才注意到那一个很重要的点。每次只能翻转奇数个，所以翻转前后每字母所在位的奇偶性是一样的。

这次对的多了点，还拿了个 $10$ 分。

我实在没办法了，去看了一下仅有的一篇题解（感谢 heaksicn 让我突然明白过来）。当看到“只要要求每个字母在相同奇偶的位置上的数量相同即可”时我恍然大悟：哪还用去看有没有重复，直接算出各个字母在奇数位上的有多少个，比较一下，偶数位上有多少个，再比较一下，只要都相等就行了。

明白了这个，这道题基本上就可以说已经 AC 了。

AC Code:

#include<bits/stdc++.h>
using namespace std;
int n,tt;
string s,t;
struct d
{
	int ji,ou;
}a[30],b[30];
int main()
{
	scanf("%d",&n);
	cin>>s>>t;
	for(int i=0;i<n;i++)
	{
		if(i&1)
		{
			a[s[i]-'a'].ji++;
			b[t[i]-'a'].ji++;						//在奇数位上的字母有多少。
		}
		else
		{
			a[s[i]-'a'].ou++;
			b[t[i]-'a'].ou++;						//在偶数位上的有多少。
		}											//如我前面所说，只要加上判断奇偶，就是代码中最重要的部分。
	}
	for(int i=0;i<=26;i++)
	{
		if(a[i].ji!=b[i].ji || a[i].ou!=b[i].ou)	//比较，只要相等即可。
		{
			printf("NIE");
			return 0;
		}
	}
	printf("TAK");
	return 0;
}

$246$ 个测试点，绿起来挺好看的。

最后，浏览过看过也要赞过！