Codeforces Round #313 (Div. 2) D. Equivalent Strings（字符串+递归）-白红宇

Codeforces Round #313 (Div. 2) D. Equivalent Strings（字符串+递归）

阅读量：7061 次

发布时间：2019-06-28

本文共 2130 字，大约阅读时间需要 7 分钟。

题意：

给两个字符串，判断是否"相等"。

这里”相等“的定义是：1、字符串对应字符相同；

2、将第一个字符串对半分成c1和d1,第二个字符串对半分成c2和d2。

如果c1==c2 && d1==d2 或者c1==d2 && c2==d1则两个字符串相等。

当字符串长度为奇数时，只有两个字符串对应字符相同才相等。

分析：

结合题意和样例，可以看出这里的相等是递归定义。显然要用到递归。

但是用string.lengtn()和str.substr(s,e)这些库函数以及cin读入的写法在89组test上tle挂了。。

后来试着用char []来存字符串，用strncpy来截取子字符串。但是要开很多数组，而且字符串长度为200000，

不能开在函数内，不然可能爆内存。。。

其实根本不需要求子串，按照递归定义递归到最底层比较返回即可一步步回溯得到结果啊！

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                using namespace std;typedef long long ll;char a[200010],b[200010];bool StrEqu(char *s1,char *s2,int l1,int r1,int l2){ for(int i=l1;i<=r1;i++) { if(s1[i]!=s2[l2++]) return false; } return true;}bool solve(char *s1,char *s2,int l1,int r1,int l2,int r2){ int len = r1-l1+1; if(len&1) return StrEqu(s1,s2,l1,r1,l2); else { if(StrEqu(s1,s2,l1,r1,l2)) return true; int mid = len/2; if(solve(s1,s2,l1,l1+mid-1,l2,l2+mid-1) && solve(s1,s2,l1+mid,r1,l2+mid,r2)) return true; if(solve(s1,s2,l1,l1+mid-1,l2+mid,r2) && solve(s1,s2,l1+mid,r1,l2,l2+mid-1)) return true; return false; }}int main(){ scanf("%s%s",&a,&b); int len = strlen(a); if(solve(a,b,0,len-1,0,len-1)) puts("YES"); else puts("NO"); return 0;}

View Code

下面是第一次用string敲的代码- -

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                using namespace std;typedef long long ll;string a,b;bool solve(string s1,string s2){ int len = s1.length(); if(len&1) { if(s1==s2) return true; else return false; } else { if(s1==s2) return true; string c1,c2,d1,d2; c1 = s1.substr(0,len/2); c2 = s1.substr(len/2,len); d1 = s2.substr(0,len/2); d2 = s2.substr(len/2,len); if(solve(c1,d1) && solve(c2,d2)) return true; if(solve(c1,d2) && solve(c2,d1)) return true; return false; }}int main(){ cin>>a>>b; if(solve(a,b)) puts("YES"); else puts("NO"); return 0;}