【题意】给出两个字符串,确定,是否相等,定义字符串是否相等为,如果为奇数串,只能比较是否每个字符相同,如果为偶数串,第一个串分成两个相等长度的串为a1 b1,第二个串也分成a2 b2,a1== a2 && b1 == b2 || a1 == b2 && a2 == b2.
【分析】类似树上的最小表示法,和字符串的最小表示是不同的,每次偶数个合并时比较大小,找出最小表示,字符串ab最小表示是否相同,复杂度N*logN。还可以暴力,按照Q神的方法可以达到31ms。但还是感觉最小表示复杂度稳定点。
【AC CODE(最小表示)】202ms
#include <cstdio> #include <cstring> #include <cctype> #include <cmath> #include <set> //#include <unordered_set> #include <queue> #include <stack> #include <vector> #include <string> #include <algorithm> using namespace std; typedef long long LL; #define rep(i,a,n) for(int i = a; i < n; i++) #define repe(i,a,n) for(int i = a; i <= n; i++) #define per(i,n,a) for(int i = n; i >= a; i--) #define clc(a,b) memset(a,b,sizeof(a)) const int INF = 0x3f3f3f3f, MAXN = 200000+10; char a[MAXN],b[MAXN]; string dfs(char *s, int x, int y) { if((y-x+1)&1) { string ans = ""; repe(i,x,y) ans += s[i]; return ans; } int m = (x+y)>>1; string l = dfs(s,x,m),r = dfs(s,m+1,y); return l<r?l+r:r+l; } int main() { #ifdef SHY freopen("d:\\1.txt", "r", stdin); #endif scanf("%s%s",a,b); int len = strlen(a); if(dfs(a,0,len-1) == dfs(b,0,len-1)) puts("YES"); else puts("NO"); return 0; }
【暴力剪枝】31ms
#include <cstdio> #include <cstring> #include <cctype> #include <cmath> #include <set> //#include <unordered_set> #include <queue> #include <stack> #include <vector> #include <string> #include <algorithm> using namespace std; typedef long long LL; #define rep(i,a,n) for(int i = a; i < n; i++) #define repe(i,a,n) for(int i = a; i <= n; i++) #define per(i,n,a) for(int i = n; i >= a; i--) #define clc(a,b) memset(a,b,sizeof(a)) const int INF = 0x3f3f3f3f, MAXN = 200000+10; char a[MAXN],b[MAXN]; bool dfs(int x1, int y1, int x2, int y2) { int len = y1-x1+1; if(!strncmp(a+x1,b+x2,len)) return true; if(len&1) return false; int m1 = (x1+y1)>>1, m2 = (x2+y2)>>1; if(dfs(x1,m1,m2+1,y2)) return dfs(m1+1,y1,x2,m2); else return dfs(x1,m1,x2,m2) && dfs(m1+1,y1,m2+1,y2); return false; } int main() { #ifdef SHY freopen("d:\\1.txt", "r", stdin); #endif scanf("%s%s", a,b); int len = strlen(a); if(dfs(0,len-1,0,len-1)) puts("YES"); else puts("NO"); return 0; }