Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 696 Solved: 294
PenguinQQ是中国最大、最具影响力的SNS(Social Networking Services)网站,以实名制为基础,为用户提供日志、群、即时通讯、相册、集市等丰富强大的互联网功能体验,满足用户对社交、资讯、娱乐、交易等多方面的需求。 小Q是PenguinQQ网站的管理员,他最近在进行一项有趣的研究——哪些账户是同一个人注册的。经过长时间的分析,小Q发现同一个人注册的账户名称总是很相似的,例如Penguin1,Penguin2,Penguin3……于是小Q决定先对这种相似的情形进行统计。 小Q定义,若两个账户名称是相似的,当且仅当这两个字符串等长且恰好只有一位不同。例如“Penguin1”和“Penguin2”是相似的,但“Penguin1”和“2Penguin”不是相似的。而小Q想知道,在给定的 个账户名称中,有多少对是相似的。 为了简化你的工作,小Q给你的 个字符串长度均等于 ,且只包含大小写字母、数字、下划线以及‘@’共64种字符,而且不存在两个相同的账户名称。
第一行包含三个正整数 , , 。其中 表示账户名称数量, 表示账户名称长度, 用来表示字符集规模大小,它的值只可能为2或64。 若 等于2,账户名称中只包含字符‘0’和‘1’共2种字符; 若 等于64,账户名称中可能包含大小写字母、数字、下划线以及‘@’共64种字符。 随后 行,每行一个长度为 的字符串,用来描述一个账户名称。数据保证 个字符串是两两不同的。
仅一行一个正整数,表示共有多少对相似的账户名称。
4 3 64 Fax fax max mac
4
4对相似的字符串分别为:Fax与fax,Fax与max,fax与max,max与mac。N<=30000,L<=200,S<=64
题解:显然的字符串哈希。。。
这里由于是恰好一位不一样,所以可以在进行双值哈希的时候统一抹掉那一位,然后如果仅仅是那一位不一样的话,那么剩下的部分必定哈希值一样,所以接下来排个序求出各种哈希值出现的次数,然后统计下即可(话说随机化快排居然比二分快排慢那么多是什么梗QAQ,最下面的那个是二分快排,上面是两个随机快排)
(还有我貌似成了第一个在BZOJ上面用pascal秒掉此题的人好开心^_^)
1 /**************************************************************
2 Problem: 3555
3 User: HansBug
4 Language: Pascal
5 Result: Accepted
6 Time:18504 ms
7 Memory:10764 kb
8 ****************************************************************/
9
10 const p=314159;q=951413;
11 type arr=array[0..50000,1..2] of int64;
12 var
13 i,j,k,l,m,n,t:longint;
14 ans,x,y:int64;ch:char;
15 ap:array[char] of longint;
16 ml,a,b:arr;
17 ss:ansistring;
18 st:array[0..50000] of ansistring;
19 procedure sort(l,r:longint;var a:arr);
20 var i,j:longint;x,y,z:int64;
21 begin
22 i:=l;j:=r;x:=a[(l+r) div 2,1];y:=a[(l+r) div 2,2];
23 repeat
24 while (a[i,1]<x) or ((a[i,1]=x) and (a[i,2]<y)) do inc(i);
25 while (a[j,1]>x) or ((a[j,1]=x) and (a[j,2]>y)) do dec(j);
26 if i<=j then
27 begin
28 z:=a[i,1];a[i,1]:=a[j,1];a[j,1]:=z;
29 z:=a[i,2];a[i,2]:=a[j,2];a[j,2]:=z;
30 inc(i);dec(j);
31 end;
32 until i>j;
33 if i<r then sort(i,r,a);
34 if l<j then sort(l,j,a);
35 end;
36 begin
37 readln(n,m,t);
38 fillchar(ap,sizeof(ap),0);
39 if t=64 then
40 begin
41 i:=0;
42 for ch:='A' to 'Z' do
43 begin
44 inc(i);
45 ap[ch]:=i;
46 end;
47 for ch:='a' to 'z' do
48 begin
49 inc(i);
50 ap[ch]:=i;
51 end;
52 for ch:='0' to '9' do
53 begin
54 inc(i);
55 ap[ch]:=i;
56 end;
57 inc(i);ap['_']:=i;
58 inc(i);ap['@']:=i;
59 end
60 else
61 begin
62 ap['0']:=1;
63 ap['1']:=2;
64 ap['2']:=3;
65 end;
66 ml[0,1]:=1;ml[0,2]:=1;
67 for i:=1 to 1000 do
68 begin
69 ml[i,1]:=(ml[i-1,1]*p) mod q;
70 ml[i,2]:=(ml[i-1,2]*q) mod p;
71 end;
72 for i:=1 to n do
73 begin
74 readln(ss);
75 x:=0;y:=0;st[i]:=ss;
76 for j:=1 to m do
77 begin
78 x:=(x+(ap[ss[j]]*ml[j,1]) mod q) mod q;
79 y:=(y+(ap[ss[j]]*ml[j,2]) mod p) mod p;
80 end;
81 a[i,1]:=x;a[i,2]:=y;
82 end;
83 ans:=0;
84 for i:=1 to m do
85 begin
86
87 for j:=1 to n do
88 begin
89 b[j,1]:=(a[j,1]-(ap[st[j][i]]*ml[i,1]) mod q+q) mod q;
90 b[j,2]:=(a[j,2]-(ap[st[j][i]]*ml[i,2]) mod p+p) mod p;
91 end;
92 sort(1,n,b);
93 b[n+1,1]:=-maxlongint;b[n+1,2]:=-maxlongint;
94 k:=1;l:=1;
95 for j:=2 to n+1 do
96 begin
97 if (b[j,1]<>b[k,1]) or (b[j,2]<>b[k,2]) then
98 begin
99 ans:=ans+(l*(l-1)) div 2;
100 k:=j;l:=1;
101 end
102 else inc(l);
103 end;
104 end;
105 writeln(ans);
106 readln;
107 end.