https://blog.csdn.net/Charles_Zaqdt/article/details/89810110
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3791
直接按第一个序列建二叉搜索树,然后接下来每一个需要判断的字符串都要建一个二叉搜索树,然后遍历一遍判断两个二叉搜索树是否相同就好了,需要注意的是最后遍历二叉搜索树的数据范围。
AC代码:
#include <bits/stdc++.h>
#define maxn 10005
using namespace std;
string str;
int a[maxn], b[maxn];
int n;
void insert(int x, int pre[]){
int cnt = 1;
while(pre[cnt] != -1){
if(pre[cnt] >= x){
cnt = (cnt << 1);
}
else cnt = (cnt << 1 | 1);
}
pre[cnt] = x;
return ;
}
void Build(string s, int pre[]){
pre[1] = (s[0] - '0');
int len = s.length();
for(int i=1;i<len;i++){
insert(s[i] - '0', pre);
}
return ;
}
int main()
{
while(~scanf("%d", &n)){
if(n == 0) break;
cin>>str;
memset(a, -1, sizeof(a));
Build(str, a);
while(n--){
cin>>str;
memset(b, -1, sizeof(b));
Build(str, b);
bool flag = true;
int len = str.length();
for(int i=0;i<=10000;i++){
if(a[i] != b[i]){
flag = false;
break;
}
}
if(flag) puts("YES");
else puts("NO");
}
}
return 0;
}