题解：P10474 [BeiJing2011] Matrix 矩阵哈希

· · 题解

前言

事情的起因是，我在用别的平台上课时碰到了这道题不太会，来这道题在洛谷的题解区转了一圈，发现好像大家的代码都过不了那个平台上的题，有一个点总是 TLE 。在请教完老师后，决定来发一篇题解。

本题的主要思路

其实这道题就是一个二维哈希。关于这一点的知识大家可以去看其他的题解，讲的都非常详细。我在这里就只作简单讲解。

  //二维 Hash 模板
    p1[0] = p2[0] = 1;
    for (int i = 1; i <= n; i++) p1[i] = p1[i - 1] * P1;
    for (int i = 1; i <= m; i++) p2[i] = p2[i - 1] * P2;
    for (int i = 1; i <= n; i++)
    {
        ULL c = 0;
        scanf("%s", s+1);
        for (int j = 1; j <= m; j++)
        {
            c = c * P2 + s[j];
            h[i][j] = h[i - 1][j] * P1 + c;
        }
    }
//先不用管下面的这个 insert ()
    for (int i = A; i <= n; i++)
        for (int j = B; j <= m; j++)
            insert(h[i][j] - h[i - A][j] * p1[A] - h[i][j - B] * p2[B] + h[i - A][j - B] * p1[A] * p2[B]);

这就是一个很普通的二维 Hash 模板了。二维 Hash 和一维 Hash 大体上是一样的，只不过要采用二维前缀和的思想来运算和求值。

时间问题的发现

关于解决时间上的问题，这里使用哈希表会比使用 map 要快，原因也显而易见，map 的每一个操作都有一个无法去除的 log ，这就是导致时间过慢的主要原因。

时间问题的解决

上面也说到了，就是使用哈希表。我这里就讲一下本题中使用到的 insert() , 和 find() 函数，对于它的其他用法可以参考 OI Wiki。

首先，我要先引入哈希表的概念。哈希表的原理与map类似，都是使用一个关键词（ key ）来查找一个值（ value ）。使用一个数组来建立 key 与 value 的映射关系即可。

a[key] = value;

但有些时候 key 并不是一个整数，我们就需要用 Hash 来把它换成整数，可问题出现了。 Hash 值过大时，就没有办法使用数组下标来查找了。因此我们可以取模。

但取模后， key 是很容易重复的（冲突），对于这种情况我们可以这样来办。把同一个 key 的 value 用链表存起来，每次查找值的时候，只需要扫一遍对应 key 的链表即可。

以上所说即为 find() 函数。

// find() 函数
int find(ULL x) 
{
    int id = x % mod;
    for (int i = last[id]; i; i = nxt[i])
        if (num[i] == x) return i;
    return 0;
}

好，现在我们把目光移到第一段代码上，注意那个 insert() 函数。 insert() 函数，顾名思义是用来插入的。前面已经提到过，哈希表使用链表来存的，所以此处使用像链表一样的插入方式。

// insert() 函数
int insert(ULL x)
{
    //这一步是为了查重，与 find() 函数一致
    int id = x % mod;
    for (int i = last[id]; i; i = nxt[i])
        if (num[i] == x) return i;

    // num[] 就是存数据的链表， nxt[] 是存指针的， last[] 就是每一个表的头指针。
    num[++cnt] = x;
    nxt[cnt] = last[id];
    last[id] = cnt;
    return cnt;
}

如果你到现在全部看懂了的话，那么恭喜你，你已经会了！

最终代码

这里放上无注释版本的代码，方便各位粘贴。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;

const int P1 = 10003, P2 = 11117, mod = 1000007, N = 1005;

int n, m, T, A, B;
char s[N];
ULL p1[N], p2[N], h[N][N], num[N * N];
int cnt, last[mod], nxt[N * N];

int find(ULL x) 
{
    int id = x % mod;
    for (int i = last[id]; i; i = nxt[i])
        if (num[i] == x) return i;
    return 0;
}

int insert(ULL x)
{
    int id = x % mod;
    for (int i = last[id]; i; i = nxt[i])
        if (num[i] == x) return i;
    num[++cnt] = x;
    nxt[cnt] = last[id];
    last[id] = cnt;
    return cnt;
}

int main()
{
    cin >> n >> m >> A >> B;
    p1[0] = p2[0] = 1;
    for (int i = 1; i <= n; i++) p1[i] = p1[i - 1] * P1;
    for (int i = 1; i <= m; i++) p2[i] = p2[i - 1] * P2;
    for (int i = 1; i <= n; i++)
    {
        ULL c = 0;
        scanf("%s", s+1);
        for (int j = 1; j <= m; j++)
        {
            c = c * P2 + s[j];
            h[i][j] = h[i - 1][j] * P1 + c;
        }
    }
    for (int i = A; i <= n; i++)
        for (int j = B; j <= m; j++)
            insert(h[i][j] - h[i - A][j] * p1[A] - h[i][j - B] * p2[B] + h[i - A][j - B] * p1[A] * p2[B]);

    cin >> T;
    while (T--)
    {
        ULL res = 0;
        for (int i = 1; i <= A; i++)
        {
            scanf("%s", s+1);
            for (int j = 1; j <= B; j++)
                res += s[j] * p1[A - i] * p2[B - j];
        }
        if (find(res)) cout << 1 << endl;
        else cout << 0 << endl;
    }
    return 0;
}

结语

这是本蒟蒻的第一篇题解，跪求管理员大大给个通过吧！！！如有不当，请各位大佬多多指教！！！！