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

Codeforces 559B Equivalent Strings 等价串

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

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