解题思路

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

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

3. 数学分析： 每次旋转操作将字符串循环左移 x_i 个位置。我们需要通过多个操作组合，最终得到一个等于目标左移 y_i 的值。

   设 y_i 为目标偏移，那么我们想找到一种方式，使得通过多个操作 x_1, x_2, ..., x_k 的组合，最终得到 y_i 的值。这个问题可以转化为一个最短路径问题，寻找通过多个 x_i 组合得到 y_i 的最小操作次数。

4. 建图和最短路径： 将每个偏移量看成一个节点，边表示通过一个操作能从某个偏移量转移到另一个偏移量。问题转化为从起始位置（偏移量 0）出发，最短路径到达目标偏移量 y_i。

   我们可以使用 广度优先搜索（BFS） 来解决这个问题，因为 BFS 能够保证我们找到最少操作次数。

5. 具体步骤：

   • 使用 BFS 从偏移量 0 开始，尝试使用每个 x_i 来更新新的偏移量。
   • 对于每个查询 y_i，我们查看从 0 到 y_i 最短的操作次数。

代码实现

C++

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int main() {
    int n, k, m;
    cin >> n >> k >> m;

    vector<int> x(k);
    for (int i = 0; i < k; ++i) {
        cin >> x[i];
    }

    vector<int> y(m);
    for (int i = 0; i < m; ++i) {
        cin >> y[i];
    }

    // 最短路径数组
    vector<int> dist(n, -1);
    dist[0] = 0;  // 初始位置为 0，0 需要 0 次操作

    // BFS 队列
    queue<int> q;
    q.push(0);  // 从偏移量 0 开始

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        for (int i = 0; i < k; ++i) {
            int next = (curr + x[i]) % n;  // 新的偏移量
            if (dist[next] == -1) {  // 如果这个偏移量没有被访问过
                dist[next] = dist[curr] + 1;
                q.push(next);
            }
        }
    }

    // 对每个查询输出结果
    for (int i = 0; i < m; ++i) {
        cout << dist[y[i]] << endl;
    }

    return 0;
}

Python

from collections import deque

def solve(n, k, m, x, y):
    # 初始化最短路径数组
    dist = [-1] * n
    dist[0] = 0  # 初始位置为0，0需要0次操作

    # BFS 队列
    q = deque([0])  # 从偏移量 0 开始

    while q:
        curr = q.popleft()

        for xi in x:
            next_offset = (curr + xi) % n  # 新的偏移量
            if dist[next_offset] == -1:  # 如果这个偏移量没有被访问过
                dist[next_offset] = dist[curr] + 1
                q.append(next_offset)

    # 输出每个查询的结果
    for target in y:
        print(dist[target])

# 手动输入部分
n, k, m = map(int, input().split())  # 读取 n, k, m
x = list(map(int, input().split()))  # 读取 k 个旋转操作
y = list(map(int, input().split()))  # 读取 m 个查询

solve(n, k, m, x, y)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int m = scanner.nextInt();

        int[] x = new int[k];
        for (int i = 0; i < k; i++) {
            x[i] = scanner.nextInt();
        }

        int[] y = new int[m];
        for (int i = 0; i < m; i++) {
            y[i] = scanner.nextInt();
        }

        // 最短路径数组
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        dist[0] = 0;  // 初始位置为 0，0 需要 0 次操作

        // BFS 队列
        Queue<Integer> q = new LinkedList<>();
        q.add(0);  // 从偏移量 0 开始

        while (!q.isEmpty()) {
            int curr = q.poll();

            for (int xi : x) {
                int nextOffset = (curr + xi) % n;  // 新的偏移量
                if (dist[nextOffset] == -1) {  // 如果这个偏移量没有被访问过
                    dist[nextOffset] = dist[curr] + 1;
                    q.add(nextOffset);
                }
            }
        }

        // 输出每个查询的结果
        for (int target : y) {
            System.out.println(dist[target]);
        }

        scanner.close();
    }
}

题目内容

给定正整数 $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$ 可达。