[CTSC2014] 企鹅QQ

发表于 | 分类于
字数统计 : 349   |   阅读时长 ≈ 2 mins.

题目

链接

[CTSC2014]企鹅QQ

题意简述

给定 个长度为 的字符串，求有多少对字符串等长且恰好只有一位不同。

思路

很明显这长度就是哈希（因为字符串我只会哈希
这道和某毒瘤czl的题很像啊。

哈希

枚举删除的位置，减掉即可。
然后排序找对数。
时间复杂度： $O(l \ * \ n \ logn)$ 。
预期得分： $(100)$。

代码

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
#include <bits/stdc++.h>
#define REG register
#define IN inline
#define For(x,y,z) for (REG int (x) = (y); (x) <= (z); ++(x))
#define FOR(x,y,z) for (REG int (x) = (y); (x) <  (z); ++(x))
const int kmax_num = 3e4 + 10, kmax_int = 2147483647, kmod = 1e9+7;

int n, l, s;
char c[kmax_num][210];

unsigned long long has[kmax_num], mod[kmax_num], mod_pow[201], bas = 233;

int main() {
    scanf(" %d %d %d", &n, &l, &s);
    For(i,1,n)  {
        scanf(" %s", c[i] + 1);
        For(h,1,l)  has[i] = has[i] * bas + c[i][h];
    }

    mod_pow[0] = 1;
    For(i,1,l)  mod_pow[i] = mod_pow[i - 1] * bas;

    REG int ans = 0;
    For(i,1,l)  {
        For(h,1,n)  {
            mod[h] = has[h] - mod_pow[l - i] * c[h][i];
        }
        std::sort(mod + 1, mod + n + 1);

        REG int cnt = 1;
        FOR(h,1,n)  {
            if(mod[h] == mod[h + 1]) ++cnt;
            else    {
                ans += cnt * (cnt - 1) / 2;
                cnt = 1;
            }
        }
        ans += cnt * (cnt - 1) / 2;
    }
    printf("%d\n", ans);
    return 0;
}

杂项

  • 这里使用 自然溢出。
  • 基数 要是被卡可以多换几个质数，如：（）。