#329. 问题3:不适的曲调(moosick)
问题3:不适的曲调(moosick)
题目描述
所有人都知道奶牛喜欢听所有种类的音乐。几乎所有种类,也就意味着,伟大的奶牛作曲家 Wolfgang Amadeus Moozart 有次发现了一个特殊的和弦可以让奶牛感到不适。这个和弦就是著名的反刍动物第七和弦,因此所有的奶牛音乐作曲家都会特意回避它。
Farmer John 并不了解奶牛作曲史的细节,他打算在牛棚大声的播放他喜欢的音乐。你的任务就是在这首歌中识别出所有的反刍动物第七和弦,从而评估它会让奶牛感到有多不适。
FJ 播放的这首歌由一系列的 ( )个音符组成,每个音符表示成一个范围在 内的整数。反刍动物第七和弦可以用 ( )个独特的音符序列表示,每个音符也是范围在 内的整数。然而,即便这些音符是变调的(同时增加或者减少一个常数),或者重排的,它依旧是反刍动物第七和弦!例如,如果 是反刍动物第七和弦,那么 (同时减 并重排), (同时加 ), (重排), (变调并重排)都是反刍动物第七和弦。
一个反刍动物第七和弦就是满足上述标准的长为 的连续音符序列。因此它可以用在歌曲中的起始位置进行唯一标识。请求出所有反刍动物第七和弦在歌曲中出现的起始位置。
输入格式(文件名:moosick.in)
第 行:一个整数 。
第 行: FJ 的歌曲的 个音符,每个音符一行。
第 行:一个整数 。
第 行:反刍动物第七和弦的 个音符样例。所有的变调或者重排都还是反刍动物第七和弦。
输出格式(文件名:moosick.out)
第 行:一个数量 ,表示 FJ 的歌中反刍动物第七和弦出现的次数。注意不同的和弦段是可以有重叠部分的。
第 行:每行一个反刍动物第七和弦的起始下标( 是 FJ 的歌中的第一个音符, 是最后一个)。下标需要按照升序排列。
输入样例
6
1
8
5
7
9
10
3
4
6
7
输出样例
2
2
4
样例解释
FJ 的歌是 ,一个反刍动物第七和弦是 的变调或者重排。
FJ 的歌中出现了两次反刍动物第七和弦(并且这两次出现有一个音符的重叠)。第一个是起点为 的 (变调 并重排),第二个是起点为 的 (变调 )。