poj Organize Your Train part II

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 #define maxn 600000
  5 using namespace std;
  6 
  7 struct node
  8 {
  9     char s[1000];
 10     node *next;
 11 };
 12 int ans;
 13 node *hash[maxn];
 14 
 15 void insert(char s[])
 16 {
 17     int k=strlen(s);
 18     int sum=0;
 19     for(int i=0; i<k; i++)
 20     {
 21         sum+=s[i]*i;
 22     }
 23     //printf("%d %s
",sum,s);
 24     if(!hash[sum])
 25     {
 26         node *p=new node();
 27         strcpy(p->s,s);
 28         hash[sum]=p;
 29         ans++;
 30         //printf("*%d %s
",sum,s);
 31     }
 32     else
 33     {
 34         node *p=hash[sum];
 35         if(!strcmp(p->s,s)) return ;
 36         else
 37         {
 38             while(p->next!=NULL)
 39             {
 40                 if(!strcmp(p->next->s,s))
 41                 return ;
 42                 p=p->next;
 43             }
 44             node *q=new node();
 45             strcpy(q->s,s);
 46             p->next=q;
 47             ans++;
 48             //printf("*%d %s
",sum,s);
 49         }
 50     }
 51     return ;
 52 }
 53 
 54 void change(char s1[],char s2[],char s3[],char s4[])
 55 {
 56     int k1=strlen(s1);
 57     int k2=strlen(s2);
 58     int t1=0,t2=0;
 59     for(int i=k1-1; i>=0; i--)
 60     {
 61         s3[t1++]=s1[i];
 62     }
 63     s3[t1]='';
 64     for(int j=k2-1; j>=0; j--)
 65     {
 66         s4[t2++]=s2[j];
 67     }
 68     s4[t2]='';
 69 }
 70 
 71 void merge(char str1[],char str2[],char str3[])
 72 {
 73     int m=0;
 74     int k1=strlen(str1);
 75     int k2=strlen(str2);
 76     for(int i=0; i<k1; i++)
 77     {
 78         str3[m++]=str1[i];
 79     }
 80     for(int j=0; j<k2; j++)
 81     {
 82         str3[m++]=str2[j];
 83     }
 84     str3[m]='';
 85 }
 86 
 87 
 88 int main()
 89 {
 90     int t;
 91     char str[1000],s1[1000],s2[1000],s3[1000],s4[1000],s[1000];
 92     scanf("%d",&t);
 93     while(t--){
 94         ans=0;
 95         scanf("%s",str);
 96         if(strlen(str)==1){
 97         printf("1
");
 98         continue;
 99         }
100         memset(hash,0,sizeof(hash));
101         int k=strlen(str);
102         for(int i=1; i<=k-1; i++)
103         {
104             //printf("%d
",i);
105             int t1=0,t2=0,j;
106             for(j=0; j<i; j++)
107             {
108                 s1[t1++]=str[j];
109             }
110             s1[t1]='';
111             for(; j<k; j++)
112             {
113                 s2[t2++]=str[j];
114             }
115             s2[t2]='';
116             change(s1,s2,s3,s4);
117             merge(s1,s4,s);
118             insert(s);
119             merge(s1,s2,s);
120             insert(s);
121             merge(s2,s3,s);
122             insert(s);
123             merge(s4,s1,s);
124             insert(s);
125             merge(s2,s1,s);
126             insert(s);
127             merge(s3,s2,s);
128             insert(s);
129             merge(s4,s3,s);
130             insert(s);
131             merge(s3,s4,s);
132             insert(s);
133         }
134         printf("%d
",ans);
135     }
136     return 0;
137 }
View Code