Codeforces 559B Equivalent Strings 等价串

题意：给定两个等长串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;

}