[codeforces 559B]Equivalent Strings

题目：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;}