重名剔除（消除重复数据)
清华OJ——数据结构与算法实验（中国石油大学)
重名剔除(Deduplicate)
Description
伊壁鸠鲁先生正在编纂一本食品百科全书。他收集了一长串由几个肚腩提名的候选人名单。由于名单中的候选人是由几个人提名的，名字重复是不可避免的。伊壁鸠鲁先生拜访你寻求帮助。他要求你消除所有重复，这对你来说是一项容易的任务。所以请抓住这个机会，让所有的肚腩都出名。
Input
第一行一个整数表示提名名单的长度。在接下来的n行中，每一行都给出了每个提名。
Output
所有重复的提名（如果重复出现多次，则只输出一次),按照重复首先出现的顺序排序。
Example
投入
10
奶油蛋卷
卡门伯特
意大利水饺
萨伐仑松饼
切达干酪
意大利水饺
特尔尼
羊角面包
奶油蛋卷
mapotoufu
输出
意大利水饺
奶油蛋卷
Restrictions
1 n 6 * 10^5
所有提名都是小写的。不包括其他字符。每个项目的长度不超过40。
时间： 2秒
内存： 256兆字节
Hints
混杂
描述
老饕老师正在编撰一本美食百科全书。为此，他已从众多的同好者那里搜集到了一份冗长的美食提名清单。既然源自多人之手，其中自然不乏重复的提名，故必须予以筛除伊壁鸠鲁老师因此登门求助，并认定此事对你而言不过是"一碟小菜",相信你不会错过在美食界扬名立万的这一良机
输入
第一行为一个整数n，表示提名清单的长度。以下n行各为一项提名
输出
所有出现重复的提名（多次重复的仅输出一次),且以其在原清单中首次出现重复（即第二次出现)的位置为序
样例
见英文题面
限制
1 n 6 * 10^5
提名均由小写字母组成，不含其它字符，且每项长度不超过40
时间：2秒
空间：256兆字节
提示
散列
1 #包括ecstdio
2 #包括字符串
3 #定义N 605000
四使用命名空间标准；
5个常量无符号长长基数=27;
6
七个字符[无][45]；
8
9结构
10 {
11 int索引；
12个无符号长长h；
13
14 bool运算符（常量s)常量
15 {
16 if(h！=s.h)返回hs.h
17返回索引
18 }
19 };
20党卫队逮捕[N]；
21 int vis[N]={ 0 }；
22不锈钢；
23
24空排序(国际，国际)
25 {
26 if(l==r)返回；
27 int mid=(l r)/2；
28排序(l，中);
29排序（中间1，r)；
30
31 int c1=l，C2=mid 1；
32 int c=l；
33
34 while(c1=midc2=r)
35 {
36 if(arr[C1]arr[C2])ls[c]=arr[C1]；
其他37个
38ls[c]=arr[C2]；
39 }
40
41而(C1=中)ls[c]=arr[C1]；
42而(C2=r)ls[c]=arr[C2]；
43表示(int I=l；I=r；一)arr[I]=ls[I]；
44 }
45
46 int main()
47 {
48 int n；
49 scanf('%d '，n)；
50表示(int I=0；在；（一)
51 {
52 scanf('%s '，s[I])；
53 int len=strlen(s[I])；
54无符号很长很长现在=0;
55
对于(int j=0；jlenj)
57 {
58 now=now * base s[I][j]；
59 }
60 arr[i].索引=我；
61 arr[i].h=现在；
62 }
63
64排序(0，n-1)；
65 int C1=1；
66
67//for(int I=0；在；i )printf('%llu %d\n '，arr[i].啊，啊[我]。索引);
68
69 while(c1n)
70 {
71 if(arr[c1]).h==arr[c1-1].h)
72 {
73 vis[arr[C1]].index]=1；
74 while(arr[c1]).h==arr[c1-1].C1；
75 }
76其他
77 {
78 c1
79 }
80 }
81
82表示(int I=0；在；（一)
83 if(vis[i])printf('%s\n '，s[I])；
84
85返回0;
86 }
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/121790.html