P4503 [CTSC2014] 企鹅 QQ
Link:Luogu
P4503 [CTSC2014] 企鹅 QQ
题目背景
PenguinQQ 是中国最大、最具影响力的 SNS（Social Networking Services）网站，以实名制为基础，为用户提供日志、群、即时通讯、相册、集市等丰富强大的互联网功能体验，满足用户对社交、资讯、娱乐、交易等多方面的需求。
题目描述
小 Q 是 PenguinQQ 网站的管理员，他最近在进行一项有趣的研究——哪些账户是同一个人注册的。经过长时间的分析，小Q发现同一个人注册的账户名称总是很相似的，例如 Penguin1，Penguin2，Penguin3……于是小 Q 决定先对这种相似的情形进行统计。
小 Q 定义，若两个账户名称是相似的，当且仅当这两个字符串等长且恰好只有一位不同。例如“Penguin1”和“Penguin2”是相似的，但“Penguin1”和“2Penguin”不是相似的。而小 Q 想知道，在给定的 $n$ 个账户名称中，有多少对是相似的。
为了简化你的工作，小Q给你的N 个字符串长度均等于L ，且只包含大小写字母、数字、下划线以及‘@’共64种字符，而且不存在两个相同的账户名称。
输入格式
第一行包含三个正整数 $N,L,S$。其中 $N$ 表示账户名称数量，$L$ 表示账户名称长度，$S$ 用来表示字符集规模大小，它的值只可能为 $2$ 或 $64$。
若 $S$ 等于 $2$，账户名称中只包含字符 0 和 1 共 $2$ 种字符；
若 $S$ 等于 $64$，账户名称中可能包含大小写字母、数字、下划线以及 @ 共 $64$ 种字符。
随后 $N$ 行，每行一个长度为 $L$ 的字符串，用来描述一个账户名称。数据保证 $N$ 个字符串是两两不同的。
输出格式
仅一行一个正整数，表示共有多少对相似的账户名称。
输入输出样例 #1
输入 #1
1
2
3
4
5
4 3 64
Fax
fax
max
mac
输出 #1
1
4
说明/提示
$4$ 对相似的字符串分别为：Fax 与 fax，Fax 与 max，fax 与 max，max 与 mac。
| 测试点编号 | $N$ | $L$ | $S$ |
|---|---|---|---|
| $1$ | $50$ | $10$ | $64$ |
| $2$ | $500$ | $100$ | $64$ |
| $3$ | $3000$ | $100$ | $2$ |
| $4$ | $3000$ | $100$ | $64$ |
| $5$ | $30000$ | $50$ | $2$ |
| $6$ | $30000$ | $50$ | $64$ |
| $7$ | $30000$ | $200$ | $2$ |
| $8$ | $30000$ | $200$ | $64$ |
| $9$ | $30000$ | $200$ | $2$ |
| $10$ | $30000$ | $200$ | $64$ |
解析
这个题看着很简单，但是想都不用想，暴力绝对会超时。 联想一下，我们一般怎么检测一个字符串是重复的呢？哈希表！ 所以我们可以有一个思路：即我们去除字符串的特定位置的字符，然后对剩余的字符串做哈希计算
怎么计算$Hash$值？
$h(s) = \sum_{i = 1}^{n} s[i] \times p^{n - i} \mod M$
例如字符串$abc$，其$Hash$值为 $ap^2 + bp^1 +cp^0$
我们这里运用前缀和来进行辅助，得到去除特定位置字符的字符串的哈希值
1
2
3
int pre = ha[j][i - 1];
int suf = ha[j][l] - ha[j][i] * pw[l - i];
t[j] = pre * pw[l - i] + suf;
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
const int N = 3e4 + 5;
const int M = 205;
const int p = 2333;
int ha[N][M], t[N], pw[M];
// ha[N][M] 每一位的哈希值 t[N] 中间数组 pw[M] 幂次方表
void solve()
{
int n, l, s; cin >> n >> l >> s;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= l; j++)
{
char c; cin >> c;
ha[i][j] = ha[i][j - 1] * p + c;
// 滚动计算哈希值
}
}
pw[0] = 1;
for (int i = 1; i <= l; i++) pw[i] = pw[i - 1] * p;
// 初始化幂表
int ans = 0;
for (int i = 1; i <= l; i++)
{// 列举字符位置
for (int j = 1; j <= n; j++)
{// 列举字符串
int pre = ha[j][i - 1];
int suf = ha[j][l] - ha[j][i] * pw[l - i];
t[j] = pre * pw[l - i] + suf;
}
sort(t + 1, t + n + 1);
// 排序，方便后续统计
int cnt = 1;
for (int j = 1; j < n; j++)
{
if (t[j] == t[j + 1])
{
ans += cnt;
cnt++;
}
else cnt = 1;
}
}
cout << ans << endl;
}