P9098 [PA2020] Zabawki 题解

· · 题解

题目

模拟题。

概要题意：

将两字符串取其一，并可以无数次取长度为奇数（这个很重要）的子串颠倒其顺序，看其能否经过若干次操作与另一个字符串相同。

举例是最好的试金石

样例。

但在做题时我会想到 NOIP2023 词典 这题：样例解释与正解无关，因为可以无数次交换，那么只要比较字符串中的字母个数就行了。

本题异曲同工之妙（废话结束）。

Idea

Part1

因为只能取长度为奇数的子串进行颠倒其顺序，由此发现位于奇数位置颠倒后仍然在奇数位置，偶数位置颠倒后仍然在偶数位置（结合 Part2）。

Part2

再试着手玩些例子：

发现当取 3 长度时，这样就实现头尾位置互换（b 与 e）。

发现当取 5 长度时，（b 与 e）（a 与 f）发生了互换，为了不打乱序列，因此可以进行上面取 3 长度的操作，这样就实现（a 与 f）互换。

若要实现更长距离的交换，只要同上思想即可。

Part3

结合 Part1 和 Part2 ：只要两个字符串的每种出现的字母的个数、字母位置的奇数个数和偶数个数相同就可以使一字符串经过若干次颠倒操作后与另一个字符串相同。

下面用样例理解一下：

Code

#include<bits/stdc++.h>
#define intt register int
using namespace std;
string s1,s2;
int n,l1,l2,t;
struct t1{int x,y;}f1[26];
struct t2{int x,y;}f2[26];
int main()
{
    cin>>n>>s1>>s2;
    l1=s1.size();l2=s2.size();
    for(intt i=0;i<l1;i++)
      if(i%2) f1[s1[i]-'a'].x++;
      else    f1[s1[i]-'a'].y++;
    for(intt i=0;i<l2;i++)
      if(i%2) f2[s2[i]-'a'].x++;
      else    f2[s2[i]-'a'].y++;
    for(intt i=0;i<26;i++) 
      if(f1[i].x!=f2[i].x||f1[i].y!=f2[i].y) t=1;//可以少判断一个每种出现的字母的个数。
    if(t)cout<<"NIE";
    else cout<<"TAK";
    return 0;
}

完结。