哈希刷题记录

2024-01-16 16:56:58

简介
第一题
第二题
第三题
第四题
第五题
第六题
第七题
第八题
第九题
第十题

简介

这就是用来记录我对于《信息学奥赛一本通 · 提高篇》一书中的习题的刷题记录以及学习笔记。

一般分专题来写（全部写一起可能要加载很久...），比如本章就是用来记录哈希的。

再插一句：Loj 真是个不错的 OJ，如果说洛谷是最棒的 OIer 社区，那 Loj 就是最棒的刷题专区。

PS：这里的“最棒的”仅仅指带给我的练习感觉最好，例如画风好康，且仅代表个人意见。

专题介绍：哈希，一个将复杂数列映射到简单值域使之便于维护的算法，相似的还有字符串哈希。

不了解 Hash 的可以康康我的一篇文章。

第一题

#10033 「一本通 2.1 例 1」Oulipo

事实上这就是一道模板题。。。（没什么好讲的）

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <cstring>
#define N 1000010
using namespace std;
typedef unsigned long long ull;

ull p[N], f[N], s;
int ans = 0;
char a[N], b[N];

int main() {
    scanf("%s", a + 1);
    scanf("%s", b + 1);
    int n = strlen(a + 1), m = strlen(b + 1);
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        f[i] = f[i - 1] * 131 + (a[i] - 'A' + 1);
        p[i] = p[i - 1] * 131;
    }
    for (int i = 1; i <= m; i++) {
        s = s * 131 + (b[i] - 'A' + 1);
    }
    for (int i = 0; i <= n - m; i++) {
        if (s == f[i + m] - f[i] * p[m])
            ans++;
    }
    printf("%d\n", ans);
    return 0;
}

第二题

#10034 「一本通 2.1 例 2」图书管理

对于会字符串哈希 + 哈希表的同学这就是模拟题。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#define mod 32441
using namespace std;

int n;
string type, s;
vector<string> v[35010];

int hash(string a) {
    int sum = 0;
    for (int i = 0; i < a.length(); i++) {
        sum = (sum * 131 + a[i]) % mod;
    }
    return sum;
}

string read() {
    string s = "";
    char c = getchar();
    while (c != '\n' && c != '\r') {//避免 Windows 与 Linux 的冲突。
        s += c;
        c = getchar();
    }
    return s;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        cin >> type;
        if (type == "add") {
            s = read();
            v[hash(s)].push_back(s);
        } else {
            bool flag = false;
            s = read();
            for (int i = 0; i < (int)v[hash(s)].size(); i++) {
                if (s == v[hash(s)][i]) {
                    flag = true;
                    break;
                }
            }
            if (flag)
                printf("yes\n");
            else
                printf("no\n");
        }
    }
    return 0;
}

第三题

#10035 「一本通 2.1 练习 1」Power Strings

经典的 KMP 求最小循环节问题，这里的核心语句就是：

if (n % (n - next[n]) == 0) printf("%d\n", n / (n - next[n]));

那么为什么是这样呢？下文转载自这篇文章。

定理：假设 \(S\) 的长度为 \(len\) 则 \(S\) 存在最小循环节，循环节的长度 \(L\) 为 \(len-next[len]\)，子串为 \(S[0…len-next[len]-1]\)。

如果 \(len\) 可以被 \(len - next[len]\) 整除，则表明字符串 \(S\) 可以完全由循环节循环组成，循环周期 \(T=len/L\)。

如果不能，说明还需要再添加几个字母才能补全。需要补的个数是循环个数 \(L-len\ mod\ L=L-(len-L)\ L=L-next[len]\ mod\ L，L=len-next[len]\)。

理解该定理，首先要理解 next 数组的含义：next[i] 表示前面长度为i的子串中，前缀和后缀相等的最大长度。

如：abcdabc

index	0	1	2	3	4	5	6	7
char	a	b	c	d	a	b	C
next	-1	0	0	0	0	1	2	3

如对于 a,ab,abc,abcd，很明显，前缀和后缀相同的长度为 0。

对于长度为5的子串 abcda，前缀的 a 和后缀的 a 相同，长度为 1。

对于长度为6的子串 abcdab，前缀的 ab 和后缀的 ab 相同，长度为 2。

接下来举几个例子来说明最小循环节和循环周期：

为方便说明，先设字符串的长度为 \(len\)，循环子串的长度为 \(L\)。

s0 s1 s2 s3 s4 s5 ，\(next[6]=3\)。

即 s0 s1 s2=s3 s4 s5。

很明显可知：循环子串为 s0 s1 s2，\(L=len-next[6]=3\)，且能被 \(len\) 整除。

s0 s1 s2 s3 s4 s5 s6 s7 ，\(next[8]=6\)。

此时 \(len-next[8]=2\) ，即 \(L=2\)。

由 s0 s1 s2 s3 s4 s5=s2 s3 s4 s5 s6 s7。

可知 s0 s1=s2 s3,s2 s3=s4 s5,s4 s5=s6 s7。

显然 s0 s1 为循环子串。

s0 s1 s2 s3 s4 s5 s6 ，\(next[7]=4\)。

此时 \(len-next[7]=3\)，即 \(L=3\)。

由 s0 s1 s2 s3=s3 s4 s5 s6。

可知 s0 s1=s3 s4,s2 s3=s5 s6。

从而可知 s0 s1 s2=s3 s4 s5，s0=s3=s6

即如果再添加 \(3-4\ mod\ 3=2\) 个字母s1 s2，那么得到的字符串就可以由 s0 s1 s2 循环 \(3\) 次组成

这个定理可以这么理解：

如 abcd abcd abcd，由长度为 \(4\) 的字符串 abcd 重复 \(3\) 次得到，那么必然有原字符串的前八位等于后八位。

也就是说，对于某个字符串 \(S\)，长度为 \(len\)，由长度为 \(L\) 的字符串 \(s\) 重复 \(R\) 次得到，当 \(R\geq 2\) 时必然有 \(S[0..len-L-1]=S[L..len-1]\)，字符串下标从 \(0\) 开始。

那么对于 KMP 算法来说，就有 \(next[len]=len-L\)。此时 \(L\) 肯定已经是最小的了。

因为 \(next\) 的值是前缀和后缀相等的最大长度，即 \(len-L\) 是最大的，那么在 \(len\) 已经确定的情况下，\(L\) 是最小的。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#define N 1000010
using namespace std;

int next[N];
char s[N];

void work() {
    int n = strlen(s + 1);
    next[1] = 0;
    for (int i = 2, j = 0; i <= n; i++) {
        while (j > 0 && s[i] != s[j + 1]) j = next[j];
        if (s[i] == s[j + 1])
            j++;
        next[i] = j;
    }
    if (n % (n - next[n]) == 0)
        printf("%d\n", n / (n - next[n]));
    else
        printf("1\n");
    return;
}

int main() {
    while (1) {
        scanf("%s", s + 1);
        if (s[1] == '.')
            break;
        work();
    }
    return 0;
}

第四题

#10036 「一本通 2.1 练习 2」Seek the Name, Seek the Fame

字符串哈希即可 \(O(N)\) 处理每一个字符串。

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <iostream>
#define mod1 1000000007
#define mod2 1000000009
#define N 400010
using namespace std;

unsigned long long f[N], p[N];
char s[N];

int main() {
    while (scanf("%s", s + 1) != EOF) {
        int n = strlen(s + 1);
        p[0] = 1;
        for (int i = 1; i <= n; i++) {
            f[i] = (f[i - 1] * 131 + s[i]);
            p[i] = (p[i - 1] * 131);
        }
        for (int i = 1; i <= n; i++) {
            if (f[i] == f[n] - (f[n - i] * p[i]))
                printf("%d ", i);
        }
        printf("\n");
    }
    return 0;
}

第五题

#10037 「一本通 2.1 练习 3」Friends

~~这题吼啊~~。

其实就是枚举每一个插入的字符，然后判断剩下的两部分是否相同即可。

看起来没那么难？细节多呀。

首先明确所有偶数串都不可能，然后求出这个奇数串的中间一个下标 \(mid=(n+1)>>1\)。
分三种情况讨论删除的字符：<mid =mid >mid。
注意：两个字符串不同仅当两者不同。（即删除字符不同但得到的串相同的算一个）。
枚举每一个删除的字符，依照以上步骤模拟即可。
没了。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#define N 2000010
using namespace std;
typedef unsigned long long ull;

ull f[N], p[N], last;
int n, mid, cnt = 0, tot = 0;
char s[N], ans[N];

ull get(int l, int r) {
    ull sum = f[r] - f[l - 1] * p[r - l + 1];
    return sum;
}

bool chck(int pos) {
    ull x, y, z;
    bool flag = false;
    if (pos < mid) {
        x = get(1, pos - 1) * p[mid - pos] + get(pos + 1, mid);
        y = get(mid + 1, n);
    } else if (pos > mid) {
        x = get(1, mid - 1);
        y = get(mid, pos - 1) * p[n - pos] + get(pos + 1, n);
    } else if (pos == mid) {
        x = get(1, mid - 1);
        y = get(mid + 1, n);
    }
    if (x == y) {
        if (x == last)
            return false;
        last = x;
        if (pos <= mid)
            for (int i = mid + 1; i <= n; i++) ans[++tot] = s[i];
        else
            for (int i = 1; i < mid; i++) ans[++tot] = s[i];
        return true;
    }
    return false;
}

int main() {
    scanf("%d", &n);
    if (n % 2 == 0) {
        printf("NOT POSSIBLE\n");
        return 0;
    }
    mid = (n + 1) >> 1;
    scanf("%s", s + 1);
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        f[i] = f[i - 1] * 131 + s[i];
        p[i] = p[i - 1] * 131;
    }
    for (int i = 1; i <= n; i++) {
        if (chck(i))
            cnt++;
    }
    if (cnt > 1) {
        printf("NOT UNIQUE\n");
        return 0;
    } else if (!cnt) {
        printf("NOT POSSIBLE\n");
        return 0;
    }
    for (int i = 1; i <= tot; i++) printf("%c", ans[i]);
    printf("\n");
    return 0;
}

第六题

#10038 「一本通 2.1 练习 4」A Horrible Poem

又是最小循环节？KMP 上。

半小时过后...，~~怎么又tmTLE了（口吐芬芳中）~~。

嗯，选举可能的每一个子串进行判断最小循环节用 KMP 是肯定 TLE 的，那怎么办？我们有玄学数学呀。

首先假设字符串 \([l,r]\) 的最小循环节长度为 \(len\)，那么显然 \(n=k\times len\)。

我们来研究 \(k\) ，发现当 \(k\) 最大时 \(len\) 最小，且 \(k\) 和 \(len\) 一定是 \(n\) 的因子。（~~这还要你说~~）

然后又发现：当 \(len'\) 为其循环节，\(k'=n\div len'\)，时（不一定最小），\(k'\) 一定是 \(k\) 的整数倍。（自己想）

那么可以将 \(n\) 分解质因数，对于 \(n\) 的每一个质因子 \(p\)，当 \([l,r-n\div p]=[l+n\div p,r]\) 时，\(n/=p\)。

这样即可求出最小的 \(len\)。（因为你除掉了最大的 \(k\)）

怎么分解质因数？显然 \(O(\sqrt N)\) 的方法会让你 GG。

那怎么办？利用筛法求质数，并且同时维护每一个数的最小质因子，那么：

\(n=mind[n]\times mind[n/mind[n]]\times ...\)。预处理时间复杂度 \(O(N）\)，查询时间复杂度 \(O(log\ N)\)。

总时间复杂度：\(O(M\ log\ N)\)。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#define N 500010
using namespace std;
typedef unsigned long long ull;

int n, m, prime[N], mind[N], tot = 0, t[N];
ull f[N], p[N];
char s[N];

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}

void get_prime() {
    for (int i = 2; i <= n; i++) {
        if (!mind[i])
            prime[++tot] = mind[i] = i;
        for (int j = 1; j <= tot && i * prime[j] <= n; j++) {
            mind[i * prime[j]] = prime[j];
        }
    }
    return;
}

ull get(int l, int r) {
    ull sum = f[r] - f[l - 1] * p[r - l + 1];
    return sum;
}

int main() {
    n = read();
    scanf("%s", s + 1);
    m = read();
    get_prime();
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        f[i] = f[i - 1] * 131 + (s[i] - 'a');
        p[i] = p[i - 1] * 131;
    }
    for (int i = 1; i <= m; i++) {
        int l = read(), r = read();
        int cnt = 0;
        t[1] = 1;
        int len = r - l + 1;
        while (len > 1) {
            t[++cnt] = mind[len];
            len /= mind[len];
        }
        len = r - l + 1;
        for (int i = 1; i <= cnt; i++) {
            len /= t[i];
            if (get(l, r - len) != get(l + len, r))
                len *= t[i];
        }
        printf("%d\n", len);
    }
    return 0;
}

第七题

#10039 「一本通 2.1 练习 5」Beads

~~不会算时间复杂度是致命的~~

想到了方法但是算了算时间以为不可做，苦苦思索 INF 年后决定先交再说，交完后发现过了...

想法很简单，就是枚举每一个长度，用 set + hash 判断即可。

时间复杂度：\(O(N/1+N/2+N/3+N/4+...+N/(N-1)+1)=O(N\ log\ N)\)。

~~我是一个一直以为是 \(O(N^2)\) 的蒟蒻~~。

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#define N 200010
using namespace std;
typedef unsigned long long ull;

int n, a[N], ans[N], sum = 0, tot = 0;
ull f1[N], f2[N], p[N];
set<ull> s;

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}

ull get(int l, int r) { return min(f1[r] - f1[l - 1] * p[r - l + 1], f2[l] - f2[r + 1] * p[r - l + 1]); }//双向相同算一个，所以取 min 即可。

int work(int len) {
    s.clear();
    for (int i = 1; i + len - 1 <= n; i += len) {
        s.insert(get(i, i + len - 1));//set 自动去重。（STL 大法好）
    }
    return s.size();
}

int main() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        f1[i] = f1[i - 1] * 13331 + a[i];
        p[i] = p[i - 1] * 13331;
    }
    for (int i = n; i >= 1; i--) f2[i] = f2[i + 1] * 13331 + a[i];
    for (int i = 1; i <= n; i++) {
        int p = work(i);
        if (p > sum) {
            sum = p;
            tot = 1;
            ans[tot] = i;
        } else if (p == sum)
            ans[++tot] = i;
    }
    printf("%d %d\n", sum, tot);
    for (int i = 1; i <= tot; i++) printf("%d ", ans[i]);
    return 0;
}

第八题

#10040 「一本通 2.1 练习 6」Antisymmetry

以为又是什么水题，于是简单分析了一波：

奇数串不可能成功。（中间那一个一定变了）
偶数串成功当且仅当 \([1,n/2]=![n,n/2+1]\)。（即取反 + 倒序）

于是我就开开心心的交了一发下面的代码：

#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <cstring>
#define N 500010
#define base 13331
using namespace std;
typedef unsigned long long ull;

ull f1[N], f2[N], p[N];
int n;
long long ans = 0;
char s[N];

ull get1(int l, int r) { return f1[r] - f1[l - 1] * p[r - l + 1]; }

ull get2(int l, int r) { return f2[l] - f2[r + 1] * p[r - l + 1]; }

long long work(int len) {
    long long sum = 0;
    for (int i = 1; i + len - 1 <= n; i++) {
        if (get1(i, i + len / 2 - 1) == get2(i + len / 2, i + len - 1))
            sum++;
    }
    return sum;
}

int main() {
    scanf("%d", &n);
    scanf("%s", s + 1);
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        f1[i] = f1[i - 1] * base + s[i] - '0';
        p[i] = p[i - 1] * base;
    }
    for (int i = n; i >= 1; i--) {
        f2[i] = f2[i + 1] * base + !(s[i] - '0');
    }
    for (int i = 2; i <= n; i += 2) {
        ans += work(i);
    }
    printf("%lld\n", ans);
    return 0;
}

然后 TLE 滚粗，之后计算了一下时间发现是 \(O(N^2/2)\) 的。（不 TLE 才怪）

之后撑死没看出单调性，翻了翻题解才恍（geng）然（jia）大（mi）悟（mang）。

定理（如果这是定理的话）：当串 \([l,r]\) 符合题意，所有 \([l+k,r-k]_{0\leq k\leq (r-l-1)/2}\) 均符合题意。

证明过于简单，略。

然后就可以二分啦。

#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <cstring>
#define N 500010
#define base 13331
using namespace std;
typedef unsigned long long ull;

ull f1[N], f2[N], p[N];
int n;
long long ans = 0;
char s[N];

ull get1(int l, int r) { return f1[r] - f1[l - 1] * p[r - l + 1]; }

ull get2(int l, int r) { return f2[l] - f2[r + 1] * p[r - l + 1]; }

long long work(int x) {
    long long sum = 0;
    int l = 1, r = min(x, n - x), mid;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (get1(x - mid + 1, x) == get2(x + 1, x + mid))
            l = mid + 1;
        else
            r = mid - 1;
    }
    return r;
}

int main() {
    scanf("%d", &n);
    scanf("%s", s + 1);
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        f1[i] = f1[i - 1] * base + s[i] - '0';
        p[i] = p[i - 1] * base;
    }
    for (int i = n; i >= 1; i--) {
        f2[i] = f2[i + 1] * base + !(s[i] - '0');
    }
    for (int i = 1; i < n; i++) {
        ans += work(i);
    }
    printf("%lld\n", ans);
    return 0;
}

时间：\(O(N\ log\ N)\)。

第九题

#10041 「一本通 2.1 练习 7」门票

哈希表模板题...

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <cstring>
#define mod 10000007
using namespace std;
typedef long long ll;

struct node {
    ll x, next;
} hash[mod << 1];
int cnt = 0, head[mod];

void add(int p, int v) {
    cnt++;
    hash[cnt].x = v;
    hash[cnt].next = head[p];
    head[p] = cnt;
}

bool find(int p, int v) {
    for (int i = head[p]; i; i = hash[i].next)
        if (hash[i].x == v)
            return true;
    return false;
}

int main() {
    int a, b, c;
    ll ans = 1;
    add(1, 1);
    scanf("%d %d %d", &a, &b, &c);
    for (int i = 1; i <= 2000000; i++) {
        ans = (ans * a + ans % b) % c;
        if (find(ans % mod, ans)) {
            printf("%d\n", i);
            return 0;
        }
        add(ans % mod, ans);
    }
    printf("-1\n");
    return 0;
}

第十题

#10042 「一本通 2.1 练习 8」收集雪花

事实证明，一切关于此题哈希做法都有问题。（出题人每看到一个哈希代码就加一组 hack 数据）

然后因为数据范围小，可以用离散化来水，复杂度 \(O(N\ log\ N)\) 据说有 \(O(N)\) 大法但我不会呀。

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <cstring>
#define N 1000010
using namespace std;

int n, a[N], b[N], l = 1, ans = 0, cnt = 0;
bool f[N];

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}

int main() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read(), b[i] = a[i];
    memset(f, false, sizeof(f));
    sort(b + 1, b + n + 1);
    int m = unique(b + 1, b + n + 1) - (b + 1);
    for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
    for (int r = 1; r <= n; r++) {
        if (!f[a[r]])
            ans = max(ans, ++cnt);
        else {
            while (a[l] != a[r]) f[a[l++]] = false;
            cnt = r - l;
        }
        f[a[r]] = true;
    }
    printf("%d\n", ans);
    return 0;
}

码农公寓

简介

第一题

第二题

第三题

第四题

第五题

第六题

第七题

第八题

第九题

第十题

相关文章