2021-2022-1 北京化工大学程序设计月赛（1） - 问题 G: 游戏的彩蛋 - 题解 - 哈希讲解

本文主要是介绍2021-2022-1 北京化工大学程序设计月赛（1） - 问题 G: 游戏的彩蛋 - 题解 - 哈希讲解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

游戏的彩蛋

• 游戏的彩蛋

时间限制：1秒
空间限制：256M

---

题目描述

Ron Milner 在 $1977$ 年的游戏 《$Starship1$》中隐藏了彩蛋，玩家进行一系列操作后游戏会说：“HI RON!”并赠送玩家$10$条命。

随着时间的流逝 Ron Milner 忘记了彩蛋如何触发，但确实在程序里找到了HI RON!的字样。

小T的男神做了一款游戏，程序十进制序列为 $a$，小T认为某彩蛋（十进制序列为$b$）藏在其中，想让你确认序列$a$中是否有一段连续的序列$b$，如果有，就认为该彩蛋藏在游戏中。

• 例如程序的序列$a$是53 81 33 93 93 31 74， 彩蛋的序列$b$是93 93 31 74（能在$a$中找到连续的序列$b$），就认为程序中隐藏有该彩蛋。

• 例如程序的序列$a$是23 93 31 74 22，彩蛋的序列$b$是72 74 73 23（不能在$a$中找到连续的序列$b$），就认为此程序中没隐藏该彩蛋。

---

输入描述

输入包括$3$行

• 第$1$行是空格隔开的两个整数 $mn$，其中 $1\le m\le 10^5,1\le n\le 10^5$，分别代表程序的序列$a$和彩蛋的序列$b$的长度（十进制数的个数）
• 第$2$行是空格隔开的$m$个整数$a_1{a}_2\cdots a_m$，代表程序的序列$a$，其中 0 ≤ a i ≤ 255 ∀ i ∈ { 1 , 2 , ⋯ , m } 0\leq a_i \leq 255\ \ \forall i\in \{1,2,\cdots, m\} 0≤ai​≤255  ∀i∈{1,2,⋯,m}
• 第$3$行是空格隔开的$n$个整数$b_1{b}_2\cdots b_n$，代表程序的序列$b$，其中 0 ≤ b i ≤ 255 ∀ i ∈ { 1 , 2 , ⋯ , n } 0\leq b_i \leq 255\ \ \forall i\in \{1,2,\cdots, n\} 0≤bi​≤255  ∀i∈{1,2,⋯,n}

---

输出描述

输出包括$1$行$1$个字符串

• 如果程序中隐藏有该彩蛋，输出Yes
• 如果程序没有隐藏该彩蛋，输出No

---

样例一

输入

7 4
53 81 33 93 93 31 74
93 93 31 74

输出

Yes

样例二

输入

5 4
23 93 31 74 22
72 74 73 23

输出

No

---

题目分析

这道题说白了就是找序列$a$中是否存在连续子序列$b$。

$a$中元素个数和$b$中元素个数都是$1e5$级别，使用KMP即可复杂度O(n+m)$地通过此题。

如果觉得KMP比较麻烦，使用哈希也可解决。

---

本题彩蛋

在本题的题目描述第一行游戏 《Starship 1》中隐藏了彩蛋中隐藏了彩蛋。快速并连续地点击这句话中的彩蛋二字5次，即可得到本题解题思路：$KMP$

---

哈希简介

本题的哈希算法主要就是将一系列数映射成一个数，进而快速比较两个序列是否相同（如果两个序列用同样的方法映射成的两个数相同，就可以很大程度上认为两个序列完全相同）

那么问题主要就在于如何将一系列数映射成一个数，这个问题蒟蒻之前写过一些，相同部分就不再做过多赘述。

👉最基本的哈希算法

假如给你一系列的个位数$a$，又给你了一系列的个位数$b$，问你能否在$a$中找到连续子序列$b$， 那么不就是这道题的简化版吗？

序列$a$: $57496126$，序列$b$: $961$。

首先我能不能把序列$a$转化成$1$个数？

当然，我们可以很容易地把序列$a$: $57496126$转化成一个数$57496126$。同理可以把序列$b$转化成$1$个数$961$。

但是序列$b$的长度是$3$，序列$a$的长度是$8$，要想找到序列$a$中是否有连续的子序列正好是$b$，即找$a$中是否有长度为$3$的序列正好是$b$。
如果是，那么这个长度为$3$的序列转化成一个数后必须是$961$（和$b$相等）

$a$中长度为$3$的序列转换成一个数后都是什么呢？

前$3$个数$\to 574$，之后是$749$，之后$496$，然后$961$，$612$，$126$。其中正好第$3$个数是$961$（和$b$转化成的数相等）。因此我们认为序列$a$中能找到连续子序列$b$

数与数的比较复杂度是$O(1)$，但是能不能快速将序列$a$转换成很多长度为$3$的数呢？

如果三个三个转换的化，每次转换都需要计算$3$次，共需要转换$len(m)-3+1$次，记$3$为$len(b)$，复杂度为$O(len(b)\ast (len(m)-len(b)))$，还是很慢。

但是前一个的值可以为后一个所用。

前$3$个数是$574$，$1$到$4$个数是$749$，中间有相同的部分$74$。怎么由$574$得到$749$呢？$759=(574-5\ast 10^2)\ast 10+9$，这样计算新的哈希值复杂度就是$O(1)$了

但上面都是以十进制为例子说的，其实最好以一个素数为进制（比如$131$）。同时也不能用一个特别大的数来存，因此要取模。

加上这两点，我们只需要把上述的十进制中的$10$换成$base$（比如$131$），并且计算后及时取模就可以了。

---

KMP

教程很多，数据结构课也可能讲，就不再赘述了。

---

反思

我承认数据还是太弱了，python的find甚至暴力都能过☠

但是，真正掌握了算法才是最重要的。

---

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;const int mod = 100001651;
#define Yes {puts("Yes");return 0;}
#define No {puts("No");return 0;}
int a[100010],b[100010];
int base=131; //131进制
int main()
{int m,n;cin>>m>>n;if(m<n)No;for(int i=0;i<m;i++)scanf("%d",&a[i]);for(int i=0;i<n;i++)scanf("%d",&b[i]);ll hash=0; // 哈希值for(int i=0;i<n;i++)hash = (hash*base+b[i])%mod; // 算出序列b的哈希ll Pow=1; // 计算base的n-1次方for(int i=1;i<n;i++)Pow=(Pow*base)%mod; // 再算出base的(n-1)次方（如上述讲解中的100就是10的3-1次方）ll hashA=0; // 哈希值for(int i=0;i<n;i++) // 先算出前n个数的哈希（第一个长度为n的序列）hashA=(hashA*base+a[i])%mod;if(hashA==hash) // 如果哈希值恰好等于序列b的哈希值，就认为序列a的前n个元素正好是bYes;for(int i=n;i<m;i++) // 剩下的每个可以作为结尾的数{hashA = (((hashA - a[i-n]*Pow)%mod+mod*2)*base+a[i])%mod; // 如前面介绍，减去前面不属于这n个数的数，加上新的一个属于这n个数的数if(hashA==hash) // 相等就认为存在Yes;}No; // 都不相等肯定不存在return 0;
}

原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/120424809

这篇关于2021-2022-1 北京化工大学程序设计月赛（1） - 问题 G: 游戏的彩蛋 - 题解 - 哈希讲解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---