欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[codeforces 559B]Equivalent Strings

程序员文章站 2022-03-02 22:46:37
...

题目:559B
题意:给定两个字符串,判断是不是一个神奇的字符串。
他们满足如下两个条件的其中之一:
1、 A与B相等。
2、 如果我们把字符串A分成两个长度相等的字符串A1,A2,并将字符串B分成两个长度相等的字符串B1,B2 然后他们满足以下的其中一项条件:
(1) A1与B1是一对神奇的字符串,并且A2与B2是一对神奇的字符串。
(2) A2与B1是一对神奇的字符串,并且A1与B2是一对神奇的字符串。
思路:
很显然用递归的思想,但是单纯的递归会TLE

#include<iostream>
#include<string>
using namespace std;
bool judge(string a,string b,int len)
{
    if(a==b) return true;
    if(len&1) return false;
    int n = len>>1;
    if(judge(a.substr(0,n),b.substr(n,n),n)&&judge(a.substr(n,n),b.substr(0,n),n))///如果把这个和下面那个调换一下位置,就会TLE。很搞笑
        return true;
    if(judge(a.substr(0,n),b.substr(0,n),n)&&judge(a.substr(n,n),b.substr(n,n),n))
       return true;
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    string a,b;
    cin>>a>>b;
    if(judge(a,b,a.size())) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

不过,这样就能过了……
……
……
正经思路是:
一个字符串可以拆成很多的小部分,这些小部分是可以任意排序的。(这个小部分的最小单位是2)(可以任意排序是因为条件2有两项。里面有很多种可能性的组合。)
按照字典顺序递归处理一下,再进行拼接。(具体是a>b还是b>a其实并不重要)
如果拼接之后的两个字符串相等,就可以了。

#include<bits/stdc++.h>
using namespace std;
string handle(string s){
    if(s.size()%2 == 1) return s;
    string s1 = handle(s.substr(0,s.size()/2));
    string s2 = handle(s.substr(s.size()/2,s.size()));
    if(s1 > s2) return s1 + s2;
    else return s2 + s1;
}
int main()
{
    string a,b;
    cin>>a>>b;
    a = handle(a);
    b = handle(b);
    if(a==b) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

相关标签: 题解