题目大意：
初始时站在树的根节点，若朝着远离根的方向走，记录“0”，接近根的方向走记录“1”。并且树的每一条边只能来回走一次（即向下和返回）。一个合法的01序列可以描述出一棵树的形态。现在给出两个合法的01序列，判断两棵树是否同构。
分析：
由于根节点确定，若两棵树同构，无非就是把子树的位置交换了一下。很自然的想法就是：将树的子树按照某种规则进行排序，若排序之后两个字符串相等，则同构；否则不同构。
现在来分析一下01序列，可以看出，当一个串的“0”和“1”个数相等时，恰好就是一棵子树。例如：
0010011101001011
可以划分为一下三棵子树
00100111，01，001011
而对于每部分划分来说，去掉第一个0和末尾的1，得到的就遍历是这棵子树的01序列（空串表示子树为空）。这样便出现了递归结构。
将这棵树最小表示的算法描述如下：
0、若01序列为空，返回。
1、划分出该01序列的每一棵子树。
2、对于每棵子树，去掉第一个0和末尾1之后，递归进行最小表示。
3、得到每棵子树的最小表示后，将子树的01串按照strcmp排序。
- /*
- ZJU1990 Subway tree systems
- */
- #include <stdio.h>
- #include <string.h>
- #include <stdlib.h>
- #define N 3005
- typedef struct{
- int f,len;
- }Node;
- Node bm[N/2][N/2];
- int nbm;
- char temp[N],*sp;
- int cmp(const void *A,const void *B){
- Node a = *((Node*)A);
- Node b = *((Node*)B);
- int i,m=(a.len>b.len?b.len:a.len);
- for(i=0;i<m;i++){
- if(sp[a.f+i]!=sp[b.f+i])
- return sp[a.f+i] - sp[b.f+i];
- }
- return 0;
- }
- void MinRep(char s[],int n){
- int i,j,k,m=0,count=0;
- Node *b=&bm[nbm++][0];
- if(n<=0) return;
- for(i=0;i<n;i++){
- if(count==0) b[m].f=i;
- if(s[i]=='0') count++;
- else count--;
- if(count==0) {
- b[m].len=i-b[m].f+1;
- m++;
- }
- }
- for(k=0;k<m;k++) Min(s+b[k].f+1,b[k].len-2);
- sp=s;
- qsort(b,m,sizeof(Node),cmp);
- for(i=k=0;k<m;k++){
- for(j=0;j<b[k].len;j++,i++)
- temp[i]=s[b[k].f+j];
- }
- for(i=0;i<n;i++) s[i]=temp[i];
- }
- int main()
- {
- int i,j,k,T;
- char s[N];
- char t[N];
- scanf("%d",&T);
- while(T--){
- scanf("%s%s",s,t);
- nbm=0;
- MinRep(s,strlen(s));
- nbm=0;
- MinRep(t,strlen(t));
- if(strcmp(s,t)==0) puts("same");
- else puts("different");
- }
- return 0;
- }