[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;
}
推荐阅读
-
CodeForces 1320D - Reachable Strings
-
codeforces 1301A Three Strings 水
-
Equivalent Strings————分治与归并
-
Equivalent Strings (递归)(分治)
-
Equivalent Strings 【DFS】
-
codeforces 559B Equivalent Strings (最小表示法)
-
【Codeforces】 Vitaly and Strings
-
【CodeForce】559B Equivalent Strings 等效字符串
-
CodeForces 1144 A - Diverse Strings
-
Codeforces - Reachable Strings