题目:http://poj.org/problem?id=3007
题意:按照图示的改变字符串,问有多少种。。字符串。。
思路:分几种排序的方法,,刚开始用map 超时(map效率不高啊。。),后来搜了一下题解,用二叉排序树。。。
先贴AC代码:
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 typedef struct tree 7 { 8 char str[100]; 9 struct tree *l,*r; 10 }tr; 11 tr head; 12 int check(char s[]) 13 { 14 tr *q; 15 tr *p=&head; 16 while(p) 17 { 18 if(strcmp(p->str,s)>0) 19 { 20 if(p->l) 21 p=p->l; 22 else 23 { 24 q=new tr; 25 strcpy(q->str,s); 26 q->l=NULL; 27 q->r=NULL; 28 p->l=q; 29 return 1; 30 } 31 } 32 else if(strcmp(p->str,s)<0) 33 { 34 if(p->r) 35 p=p->r; 36 else 37 { 38 q=new tr; 39 strcpy(q->str,s); 40 q->l=NULL; 41 q->r=NULL; 42 p->r=q; 43 return 1; 44 } 45 } 46 else 47 return 0; 48 } 49 return 0; 50 } 51 /*void pre(tr *qqq) 52 { 53 if(qqq) 54 { 55 cout<<qqq->str<<endl; 56 pre(qqq->l); 57 pre(qqq->r); 58 } 59 }*/ 60 int main() 61 { 62 int t,i,j,len,cou,sum; 63 char s[100],s1[100]; 64 cin>>t; 65 while(t--) 66 { 67 cin>>s; 68 strcpy(head.str,s); 69 head.l=NULL; head.r=NULL; 70 sum=1; 71 len=strlen(s); 72 for(i=1; i<len; i++) 73 { 74 cou=0; 75 for(j=0; j<i; j++) 76 s1[cou++]=s[j]; 77 for(j=len-1; j>=i; j--) 78 s1[cou++]=s[j]; 79 s1[cou]='