题意:给定两个等长串a,b。推断是否等价。等价的含义为:若长度为奇数,则必须是同样串。若长度是偶数,则将两串都均分成长度为原串一半的两个子串al,ar和bl,br,当中al和bl等价且ar和br等价,或者al和br等价且ar和bl等价。
实际上非常水。直接依照题意模拟写个递归分治就能够求。比赛的时候总认为这样暴力写会TLE,由于算了下大概是4^(log2(n))的复杂度。也就是n^2。所以比赛的时候就想了下。将两个串都依照题意转化为字典序最小串(循环节的最小表示法)然后比較a和b的两个最小表示法是否是同样的就可以。
后来想了半天为什么分治到不了4^(log2(n))的复杂度呢?原因是这种:我们就依照这个复杂度去构造串。
首先,假设要让al和ar比較,bl和br比較。且al和br也比較,ar和bl也比較的话。则必须满足al和bl等价。ar和br不等价,且al和br等价。这样才干保证让ar和bl去比較。然而我们在比較的al和bl的时候,再分治,设al分成了all,alr,bl分成了bll。blr,要想让它再比較4次。则有all和bll等价。alr和blr不等价,alr和bll等价,但由于这个情况下al和bl是等价的。所以必须有alr和bll等价。
我们简单的写成
all = bll
alr != blr
alr = bll
all = blr
然而这4个等式能够推出all = bll = alr = blr,即4个子串随意都能等价。与第二个等式矛盾。
这说明无法构造一种串使得复杂度达到4^(log2(n))。实际上。在非常多时候递归仅仅进行了三次甚至两次一次就返回了。
因此分治的效率也是非常高的。当然。最小表示法的复杂度是O(n*log(n))的。那是一定能够过。
实际上还是分治的思想。仅仅只是处理上有点不同罢了。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <set>
using namespace std;
const int MAX = 2*1e5 + 5;
char a[MAX], b[MAX];
int cmp(char *x, int l1, int l2, int len)
{
for(int i = 0; i < len; i++)
{
if(x[l1 + i] < x[l2 + i])
return -1;
if(x[l1 + i] > x[l2 + i])
return 1;
}
return 0;
}
void translation(char *x, int l, int r) //将原串变为字典序最小的串
{
if((r - l + 1)&1)
return;
int mid = (l + r) >> 1, len = (r - l + 1) >> 1;
translation(x, l, mid);
translation(x, mid + 1, r);
if(cmp(x, l, mid + 1, len) < 0)
{
for(int i = 0; i < len; i++)
swap(x[l + i], x[mid + 1 + i]);
}
}
void solve()
{
int lena = strlen(a), lenb = strlen(b);
translation(a, 0, lena - 1);
translation(b, 0, lenb - 1);
printf("%s\n", strcmp(a, b) == 0 ? "YES" : "NO");
}
int main()
{
while(scanf("%s%s", a, b) != EOF)
solve();
return 0;
}