解题思路

1. 理解前缀旋转操作： 每种前缀旋转操作将字符串的前 x_i 个字符移动到末尾，相当于将字符串向左移动 x_i 个字符。比如，x_i=2 操作会将前 2 个字符移到末尾，相当于将字符串左移 2 位。

2. 目标： 对于每个查询，目标是将字符串循环左移 y_i 位，我们需要通过 x_1, x_2, ..., x_k 中的操作来组合出目标左移 y_i。

本题为2025年8月24日米哈游机考原题

米哈游机考的介绍点击这里

题目内容

给定正整数 $n$ ，以及 $k$ 个可用的前缀旋转操作：第 $i$ 个操作将字符串的前 $x_i$ 个字符移动到末尾。你可以对字符串执行任意次操作(可重复使用相同的 $x_i$ ) 。

对于目标偏移 $y(0 ≦y<n)$ ，定义目标结果为循环左移 $y$ 位(即将前 $y$ 个字符移至末尾)的字符串。现在需要回答 $m$ 个查询：对于每个查询给定的偏移 $y_i$ ，求使用前缀旋转操作，达成目标偏移 如 所需的最少操作次数;若无法达到，则输出 $-1$ 。

【名词解释】

• 前缀旋转：前缀旋转 指将字符串 $s$ 的前 $x$ 个字符移动到末尾，例如将 "$abcde$" 的前 $2$ 个字符旋转后得到“$cdeab$" 。

输入描述

第一行输入三个整数

$n,k,m(1≦n≦5×10^4;1≦k≦100;1≦m≦10^5)$，分别表示字符串长度、可用操作数和查询次数；

第二行输入 $k$ 个整数 $x_1,x2,...,x_k(1 ≦x_i≦n)$ ，表示可用的前缀旋转长度；

第三行输入 $m$ 个整数 $y_1,y_2,...,y_n(0 ≦y_i<n)$ ，表示目标偏移。

输出描述

对于每个查询 $y_i$ ，按输入顺序，新起一行输出一个整数，表示使 $s$ 循环左移 $y_i$ 位(即将前 $y_i$ 个字符移动至末尾)所需的最少前缀旋转操作次数；若不可达，则输出 $-1$ 。

样例1

输入

5 2 3
1 3
0 1 4

输出

0
1
2

说明

在这个样例中：

• 偏移 $0$ ：无需操作；

• 偏移 $1$ ：使用 $x_1=1$ 一次；

• 偏移 $4$ ：先使用 $x_2= 3$ ，再使用 $x_1=1$ ，共 $2$ 次。

样例2

输入

6 2 4
3 6
0 3 1 4

输出

0
1
-1
-1

说明

在此样例中，只有偏移 $0$ 和 $3$ 可达。