POJ3007-Organize Your Train part II

来源:转载

转载请注明出处:優YoU  http://user.qzone.qq.com/289065406/blog/1307515870

 

大致题意:

给定一个字符串,从任意位置把它切为两半,得到两条子串

定义 子串1为s1,子串2为s2,子串1的反串为s3,子串2的反串为s4

现在从s1 s2 s3 s4中任意取出两个串组合,问有多少种不同的组合方法

 

规定:

(1)       串Si不能和其 反串 组合

(2)       Si+Sj 与 Sj+Si 是两种组合方式(但未必是不同的组合方式)

 

解题思路:

利用hash表查重

 

穷举全部组合的情况,每枚举一个就记录一次,假如后面枚举的组合已经存在记录,说明组合重复,计数器不变,否则计数器+1

 

本题不能用STL的map映射,map太慢会超时

自己写Hash表吧!

对于*ps指向的字符串s,我定义的关键字 

 

可以认为i为权重,利用字母的ASCII得到key

解决冲突方法为链地址法

 

 1 //Memory Time 
2 //2380K 157MS
3
4 #include<iostream>
5 using namespace std;
6
7 const int size=80;
8 const int mod=99991;
9 int count; //计数器
10
11 typedef struct HASH
12 {
13 char s[size];
14 struct HASH* next;
15 HASH()
16 {
17 next=0; //0<=>NULL
18 }
19 }Hashtable;
20
21 Hashtable* Hash[mod]; //hash[]是指针数组,存放地址
22
23 void hash(char* s);
24 void StrCopy(char* s1,char* s2); //把s2复制到s1,要确保s1.len>s2.len
25 void StrCut(char* s,char* s1,char* s2,int k,int slen); //把s前k个字符(0~k-1)复制到s1,第k到slen的字符复制到s2
26 void StrInvert(char* s1,char* s2,int len); //把s1逆序存放到s2
27 char* StrCat(char* s1,char* s2,char* str); //把s2连接到s1后,存放到s
28
29 int main(void)
30 {
31 int n;
32 cin>>n;
33 while(n--)
34 {
35 char train[size];
36 cin>>train;
37 int len=strlen(train);
38 if(len==1)
39 {
40 cout<<1<<endl;
41 continue;
42 }
43
44 memset(Hash,0,sizeof(Hash)); //0 <-> NULL
45 count=0;
46
47 for(int i=1;i<=len-1;i++) //i为火车分开的两部分中,前一部分的节数
48 {
49 char s1[size],s2[size];
50 char s3[size],s4[size]; //s3为s1的逆序,s4为s2的逆序
51 char str[size];
52
53 StrCut(train,s1,s2,i,len);
54 StrInvert(s1,s3,i);
55 StrInvert(s2,s4,len-i);
56
57 /*标记组合方式*/
58
59 hash(train); //s1与s2组合就是原来的train
60 StrCat(s2,s1,str);
61 hash(str);
62 StrCat(s1,s4,str);
63 hash(str);
64 StrCat(s4,s1,str);
65 hash(str);
66 StrCat(s3,s2,str);
67 hash(str);
68 StrCat(s2,s3,str);
69 hash(str);
70 StrCat(s3,s4,str);
71 hash(str);
72 StrCat(s4,s3,str);
73 hash(str);
74 }
75
76 cout<<count<<endl;
77 }
78 return 0;
79 }
80
81
82 void hash(char* s)
83 {
84 char* ps=s;
85
86 int key=0;
87 for(int i=1;*ps;i++)
88 key+=*(ps++)*i;
89 key%=mod;
90
91 if(!Hash[key]) //新key
92 {
93 Hashtable* pn=new Hashtable; //由于要存放数据,必须申请空间
94 //Hashtable* pn;只是单纯申请一个地址空间
95 StrCopy(pn->s,s);
96 Hash[key]=pn;
97
98 count++;
99 }
100 else //key值冲突
101 {
102 Hashtable* pn=Hash[key]; //pn指向冲突位置的链表开头
103
104 if(!strcmp(pn->s,s))
105 return; //不计数返回
106 else
107 {
108 while(pn->next)
109 {
110 if(!strcmp(pn->next->s,s)) //地址冲突且字符串相同
111 return;
112
113 pn=pn->next;
114 }
115
116 //地址冲突但字符串不同
117
118 Hashtable* temp=new Hashtable;
119 StrCopy(temp->s,s);
120 pn->next=temp; //记录新字符串
121
122 count++;
123 }
124 }
125 return;
126 }
127
128 void StrCopy(char* s1,char* s2) //把s2复制到s1
129 {
130 char* ps1=s1;
131 char* ps2=s2;
132 while(*ps2)
133 *(ps1++)=*(ps2++);
134 *ps1='/0';
135
136 return;
137 }
138
139 void StrCut(char* s,char* s1,char* s2,int k,int slen) //把s前k个字符(0~k-1)复制到s1,第k到slen的字符复制到s2
140 {
141 int i,ps1=0,ps2=0;
142
143 for(i=0;i<k;i++)
144 s1[ps1++]=s[i];
145 s1[ps1]='/0';
146
147 for(;i<slen;i++)
148 s2[ps2++]=s[i];
149 s2[ps2]='/0';
150
151 return;
152 }
153
154 void StrInvert(char* s1,char* s2,int len) //把s1逆序存放到s2
155 {
156 int ps=0;
157 s2[len]='/0';
158 for(int i=len-1;i>=0;i--)
159 s2[i]=s1[ps++];
160
161 return;
162 }
163
164 char* StrCat(char* s1,char* s2,char* str) //把s2连接到s1后,存放到s
165 {
166 int i,ps=0;
167 for(i=0;s1[i]!='/0';i++)
168 str[ps++]=s1[i];
169 for(i=0;s2[i]!='/0';i++)
170 str[ps++]=s2[i];
171 str[ps]='/0';
172
173 return str;
174 }
我的所有ACM解题报告:http://user.qzone.qq.com/289065406/blog/1301632863 || 我的CSDN:http://hi.csdn.net/invite.php?u=10114444&c=57929f66dd919f2b || 我的新浪微博:http://weibo.com/lyy289065406 || 我的腾讯微博:http://t.qq.com/lyy289065406 || 我的QQ空间:http://user.qzone.qq.com/289065406 || 我的百度空间:http://hi.baidu.com/you289065406/home || 我的金山网盘:http://www.kuaipan.cn/register/?invite=evpga1


分享给朋友:
您可能感兴趣的文章:
随机阅读: