P9098 tj

David_yang · 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;
}