2015年7月25日 星期六

[CF 559B] Equivalent Strings

作法:

首先我們可以證明,題目給的等於的定義是一個「等價關係」(equivalence relation),可以對字串的長度用數學歸納法即可,因此不難證明,兩個字串是等價的若且唯若:把兩個字串都換成與他等價的字典序最小的字串,兩字串相等。而這個過程就可以用分治來解決了。

另外,這題有很多人直接寫了$O(n^2)$的解卻過了(也就是直接遞迴檢查$4$種可能的子字串配對),例如這份 code 的寫法,實際上可以證明這樣的複雜度其實是$O(n^{1.57})$的,詳細可以參考這篇 comment

code :



#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10 ;
 
void solve(char *s,int n)
{
    if(n%2) return ;
    solve(s,n/2) ; solve(s+n/2,n/2) ;
    bool ch=0 ;
    for(int i=0;i<n/2;i++) if(s[i]!=s[i+n/2])
    {
        if(s[i]<s[i+n/2]) return ;
        ch=1 ; break ;
    }
    if(ch) for(int i=0;i<n/2;i++) swap(s[i],s[i+n/2]) ;
}
char s[maxn],t[maxn] ;
main()
{
    scanf("%s%s",s,t) ;
    int n=strlen(s) ;
    solve(s,n) ; solve(t,n) ;
    for(int i=0;i<n;i++) if(s[i]!=t[i])
        {printf("NO\n") ; return 0 ;}
    printf("YES\n") ;
}
 

沒有留言:

張貼留言