理解前缀旋转操作:
每种前缀旋转操作将字符串的前 x_i 个字符移动到末尾,相当于将字符串向左移动 x_i 个字符。比如,x_i=2 操作会将前 2 个字符移到末尾,相当于将字符串左移 2 位。
目标:
本题为2025年8月24日米哈游机考原题
米哈游机考的介绍点击这里
给定正整数 n ,以及 k 个可用的前缀旋转操作:第 i 个操作将字符串的前 xi 个字符移动到末尾。你可以对字符串执行任意次操作(可重复使用相同的 xi ) 。
对于目标偏移 y(0≦y<n) ,定义目标结果为循环左移 y 位(即将前 y 个字符移至末尾)的字符串。现在需要回答 m 个查询:对于每个查询给定的偏移 yi ,求使用前缀旋转操作,达成目标偏移 如 所需的最少操作次数;若无法达到,则输出 −1 。
【名词解释】
第一行输入三个整数
n,k,m(1≦n≦5×104;1≦k≦100;1≦m≦105),分别表示字符串长度、可用操作数和查询次数;
第二行输入 k 个整数 x1,x2,...,xk(1≦xi≦n) ,表示可用的前缀旋转长度;
第三行输入 m 个整数 y1,y2,...,yn(0≦yi<n) ,表示目标偏移。
对于每个查询 yi ,按输入顺序,新起一行输出一个整数,表示使 s 循环左移 yi 位(即将前 yi 个字符移动至末尾)所需的最少前缀旋转操作次数;若不可达,则输出 −1 。
输入
5 2 3
1 3
0 1 4
输出
0
1
2
说明
在这个样例中:
偏移 0 :无需操作;
偏移 1 :使用 x1=1 一次;
偏移 4 :先使用 x2=3 ,再使用 x1=1 ,共 2 次。
输入
6 2 4
3 6
0 3 1 4
输出
0
1
-1
-1
说明
在此样例中,只有偏移 0 和 3 可达。