第 2 届河北省大学生程序设计竞赛（河北省赛）

编程入门行业动态更新时间:2024-10-26 20:34:36

第 2 届<a href=https://www.elefans.com/category/jswz/34/1731571.html style= 河北省大学生程序设计竞赛（河北省赛）"/>

第 2 届河北省大学生程序设计竞赛（河北省赛）

传送门

Problem A. Mex Query

Problem B. Nim Game

Problem C. icebound 的账单

Problem G. 520

Problem H. 神殿

Problem J. icebound 的商店

Problem K. Bitmap

哈希讲解

二维哈希讲解

Problem L. 跑图

文章目录

传送门
- - - Problem A. Mex Query
    - Problem B. Nim Game
    - Problem C. icebound 的账单
    - Problem G. 520
    - Problem H. 神殿
    - Problem J. icebound 的商店
    - Problem K. Bitmap
    - - 哈希讲解
        二维哈希讲解
    - Problem L. 跑图
Problem K. Bitmap
- - Description
  - Input
  - Output
  - Sample Input
  - Sample Output
- 题目大意
- 解题思路
- AC代码

Problem K. Bitmap

Time Limit: 1000ms
Memory Limit: 262144KB

Description

RSYJ is a computer scientist. He has developed many useful image search tools. But now he has encountered some problems.

We use a matrix of H × H H \times H H×H to represent a bitmap with H × H H \times H H×H size, and each pixel of the 8 8 8-bit bitmap is represented by the integer between [ 0 , 255 ] [0,255] [0,255].

Now, RSYJ have a 8 8 8-bit bitmap A A A with n × n n \times n n×n size, and a 8 8 8-bit bitmap B B B with m × m m \times m m×m size.RSYJ uses an image processing software to copy bitmap B B B to some positions in bitmap A A A. Due to RSYJ’s computer’s error, the value of each pixel in the bitmap B B B is added with an offset k k k , which is an integer, but RSYJ doesn’t know what k k k is.

Now your task is writing a program to help RSYJ find all positions of bitmap B B B in the bitmap A A A. To simplify the problem, you only need output how many positions of bitmap B B B in bitmap A A A.

For example, here are two bitmaps A A A and B B B:

A	B
10 9 3 11 6 5 15 7 2	4 3 5 0

Bitmap B B B was added with an offset: 6 6 6. It becomes:

10 9

11 6

Bitmap B B B was added with an offset: 2 2 2. It becomes:

6 5

7 2

So there are two positions of bitmap B B B in bitmap A A A.

Input

The first line of the input gives two positive integers n , m n , m n,m, representing the size of bitmap A A A and the size of bitmap B B B, respectively.

The next nn lines give the bitmap A A A . Each line contains nn integers.

The next mm lines give the bitmap B B B . Each line contains mm integers.

1 ≤ n ≤ 400 1 \leq n \leq 400 1≤n≤400,

1 ≤ m ≤ 200 1 \leq m \leq 200 1≤m≤200,

0 ≤ a i j ≤ 255 0 \leq a_{ij} \leq 255 0≤aij≤255,

0 ≤ b i j ≤ 255 0 \leq b_{ij} \leq 255 0≤bij≤255

Output

Please output an integer, representing the number of positions of bitmap B B B in bitmap A A A.

Sample Input

Sample Output

题目大意

给你两个矩阵，一个是大矩阵，一个是小矩阵。
矩阵中值的范围必须是0 ~ 255，你把小矩阵中的每个值都加上或减去一个相同的数（还要保证每个数范围都是0 ~ 255)，看看能不能在大矩阵中找到小矩阵。
尝试给小矩阵加上所有可以加的数，看看能在大矩阵中找到多少小矩阵。

解题思路

这是一道二维哈希题。
如果您还不会哈希，请先到这里 → \rightarrow →哈希
如果您还不会二维哈希，请再到这里 → \rightarrow →二维哈希

好了，请允许我认为你已经会了（二维）哈希 ( q w q qwq qwq)。

那么这一题，在给出矩阵A后，我们就可以求出A中所有的大小为B的子矩阵的哈希值，并记录下来（下标过大，可以使用map来记录）。
之后计算出矩阵B的哈希值，同时记录下来B的最大值和最小值，以便确定B的偏移量的范围。
如果每次都真的把B中的每一个数都加上一个偏移量，再重新计算B的哈希，那么复杂度是 O ( 255 × m 2 ) O(255\times m^2) O(255×m2)，此题可以通过。
但是我们想到哈希的意义，可以理解为 b a s e base base进制下的数。我们先拿大家最熟悉的 10 10 10进制来举例：

假如矩阵B是 5 7 4 2 5\ 7\ 4\ 2 5 7 4 2，那么十进制下矩阵B的哈希就是 5742 5742 5742。
把B中的每一个元素 + 1 +1 +1得 6853 6 8 5 3 6853，那么哈希值为 6853 6853 6853。
再加一得 7964 7964 7964。
不难发现 7964 − 6853 = 1111 , 6853 − 5742 = 1111 7964-6853=1111,6853-5742=1111 7964−6853=1111,6853−5742=1111。因此我们知道原来矩阵B的哈希值 5742 5742 5742后，就不需要每次都把B中的每个元素 + 1 +1 +1，只需要每次把B的哈希值 + 1111 +1111 +1111即可。
那么 1111 1111 1111是怎么来的呢？ 1111 = 1 + 1 ∗ 10 + 1 ∗ 10 ∗ 10 + 1 ∗ 10 ∗ 10 ∗ 10 1111=1+1*10+1*10*10+1*10*10*10 1111=1+1∗10+1∗10∗10+1∗10∗10∗10，其中 10 10 10为 10 10 10进制。

那么换成 p p p进制的话，我们可以先算出来那个“1111”（记为 o n c e once once），方法是： o n c e = ∑ i = 0 m ∗ m p i once=\sum_{i=0}^{m*m}p^i once=∑i=0m∗mpi。
因此，我们得到B的初始的哈希后，只需要每次都加上或减去 o n c e once once即可。

另外，这题在 p = 131 p=131 p=131下 u n s i g n e d l o n g l o n g unsigned\ long\ long unsigned long long自然溢出即可通过。

emmm，如果还不太懂，代码还有一些注释：

AC代码

#include<bits/stdc++.h>
#include<map>
using namespace std;
typedef unsigned long long ull;
const int N=400;//矩阵A的范围
const int M=200;//矩阵B的范围
const int p=131;//131进制
ull power[M*N+5];//power[i]代表p的i次方
ull A[N+5][N+5];//矩阵A的行哈希
ull getLine(int x,int l,int r)//第i行从l到r的哈希
{return A[x][r]-A[x][l-1]*power[r-l+1];
}
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++)//涉及到前缀的一般从1开始{A[i][0]=0;for(int j=1;j<=n;j++){int t;scanf("%d",&t);A[i][j]=A[i][j-1]*p+t;//这个数的行哈希=左边的行哈希*进制+这个数}}power[0]=1;//131^0=1for(int i=1;i<=m*m;i++)//最多用到131^(m*m){power[i]=power[i-1]*p;//不用取模，自然溢出即可（对2^64取模）}map<ull,int>Map;//用来记录A中一个大小为B的矩阵的哈希出现过哪几次for(int i=m;i<=n;i++)//先求列{ull s=0;//初始值是0int r=i,l=r-m+1;//从l到rfor(int j=1;j<=n;j++){s=s*power[m]+getLine(j,l,r);//上一行l~r的行哈希*p^m加上这一行l~r的行哈希if(j>m)s=s-getLine(j-m,l,r)*power[m*m];//如果这是第m+1行及更大，就需要减去多余B矩阵的那一行if(j>=m)Map[s]++;//如果这个矩阵的范围已经达到了B矩阵的范围，记录下来}}//B:ull s=0;//B矩阵的初始哈希int mb=256,Mb=0;//B矩阵中的最小值（初始值为256）、最大值（初始值为0）for(int i=1;i<=m;i++){for(int j=1;j<=m;j++){int t;scanf("%d",&t);//输入B矩阵mb=min(mb,t);//更新最小值Mb=max(Mb,t);//和最大值s=s*p+t;//哈希=前面的哈希*p+这个数}}ull once=0;//B中的所有元素都变化1时，B矩阵总的哈希值的变化for(int i=0;i<m*m;i++){once+=power[i];}int Jian=mb,Jia=255-Mb;//要减去的次数、要加上的次数int ans=0;//答案ull tempS=s;//拷贝一份B矩阵的原始哈希for(int i=1;i<Jian;i++)//这次从1开始，没有计算原始B矩阵的哈希{tempS-=once;//每次-onceans+=Map[tempS];}tempS=s;//再拷贝一份for(int i=0;i<=Jia;i++)//这次从0开始，计算了B矩阵的原始的值{ans+=Map[tempS];//因为含有原始的值，所以先更新ans再+oncetempS+=once;//每次+once}cout<<ans<<endl;return 0;
}