#19281. 毕昇的字架
毕昇的字架
你好!我是你的OI金牌教练。
刚才在演示样例逻辑时,为了展示思维过程显得有些啰嗦。 这里为你整理了修正后、精简且完全正确的版本。这道题结合了北宋活字印刷术的历史背景,考察 GESP 6级 核心算法——双指针/滑动窗口。
第一部分:背景知识讲解
1. 活字印刷术 (Movable Type Printing)
北宋庆历年间,毕昇发明了胶泥活字印刷术。相比于之前的雕版印刷,活字印刷的特点是“字是活的”,可以随意拼凑组合。
2. 排版效率问题
工匠需要在一个巨大的字架上寻找所需的汉字。如果所需的字分布在字架的一小段连续区域内,工匠就可以站定不动,快速取完所有字;反之,如果字分布太散,工匠就要来回奔波。 因此,如何在长序列中找到包含所有目标元素的最小区间,就成了一个经典的算法问题。
第二部分:题目内容
题目名称:毕昇的字架 (Bi Sheng's Type Rack)
题目描述
毕昇的工坊里有一个长条形的字架,上面按顺序摆放了 个活字。为了方便记录,我们用数字 来代表不同的汉字。字架上的活字编号依次为 。
现在,工匠需要排印一个包含 种不同汉字的标题。这 种汉字的编号分别是 。
为了节省体力,工匠希望在字架上找到一个连续的区间 ,使得这个区间内至少包含这 种所需的汉字(区间内可以包含其他无关的字,也可以包含多余的所需字)。
请你编写程序,计算出满足条件的最小区间长度(即 的最小值)。如果字架上找不到包含所有所需汉字的区间,请输出 Impossible。
输入格式
第一行包含两个正整数 。
- 表示字架上活字的总数。
- 表示需要排印的汉字种类的数量。
第二行包含 个正整数 ,表示字架上依次摆放的汉字编号。
第三行包含 个正整数 ,表示需要排印的那 种汉字的编号(保证互不相同)。
输出格式
输出一行。如果有解,输出最小连续区间的长度;无解则输出 Impossible。
输入输出样例 #1
输入:
10 3
1 2 3 5 4 2 1 5 3 6
1 3 5
输出:
3
样例 #1 解释:
我们需要找到包含 {1, 3, 5} 的最小区间。
- 整个字架序列为:
1 2 3 5 4 2 1 5 3 6 - 区间 内容为
1 2 3 5,包含所有目标,长度为 4。 - 区间 内容为
1 5 3,包含所有目标,长度为 3。 - 长度 3 是最小的,故输出 3。
输入输出样例 #2
输入:
5 3
1 2 1 2 1
1 2 3
输出:
Impossible
样例 #2 解释: 字架上只有 1 和 2,无论怎么选区间,都找不到 3。
数据范围
对于 的数据:
- 汉字编号范围 。