题解 | #环形字符串跃迁#

题目链接

题目描述

有一个长度为 $N$ 的环形字符串 $s$ 。初始时光标位于第 $start$ 个字符。接下来进行 $k$ 次移动，每次移动的规则如下：

假设当前光标在第 $i$ 个位置，向后观察 $M$ 个字符（不包括当前字符）。

如果在观察的 $M$ 个字符中存在字符 '0'，则光标移动到其中最远的一个 '0' 的位置。
如果观察范围内没有 '0'，则光标移动到下一个字符的位置，即 $(i \pmod N) + 1$ 。

需要回答 $Q$ 次独立的询问，每次给定不同的 $start$ 和 $k$ ，求出最终光标停留的位置。

解题思路

由于移动次数 $k$ 的值很大，对每次查询都进行模拟是不可行的。注意到从任意位置开始的下一次移动位置是固定的，这构成了一个功能图（functional graph）。在这类图上求 $k$ 步后的节点，是倍增（Binary Lifting） 算法的典型应用场景。

算法主要分为三个步骤：

预计算单步跳转：我们需要先计算出从每个位置 $i$ ( $0 \le i < N$ ) 出发，移动一次后会到达的目标位置 next_pos[i]。

为了高效地找到环形字符串中一个区间内最远的 '0'，我们可以采用一个技巧：
- 将原字符串 $s$ 复制一次拼接在自身后方，得到一个长度为 $2N$ 的新字符串 $s'$ 。
- 创建一个辅助数组 prev_zero，prev_zero[j] 存储在 $s'$ 中，位置 $j$ （包含 $j$ ）之前最后一个 '0' 的下标。这个数组可以通过一次 $O(N)$ 的遍历来完成。
- 现在，对于原字符串的任意位置 $i$ ，其搜索窗口是 (i, i+M]。这个窗口中最远的 '0' 的位置就可以通过 p = prev_zero[i+M] 查到。
- 如果 p > i，说明在窗口内找到了 '0'，那么 next_pos[i] = p % N。
- 如果 p <= i，说明窗口内没有 '0'，那么 next_pos[i] = (i + 1) % N。
这一步的整体时间复杂度为 $O(N)$ 。
构建倍增表：我们定义一个二维数组 jump[p][i]，它表示从位置 $i$ 出发，连续跳转 $2^p$ 次后到达的位置。
- 基础状态: jump[0][i] = next_pos[i]，即跳转 $2^0=1$ 次。
- 递推关系: jump[p][i] = jump[p-1][jump[p-1][i]]。其含义是，从 $i$ 跳 $2^p$ 步，等价于先跳 $2^{p-1}$ 步，再从落点继续跳 $2^{p-1}$ 步。
我们可以预先计算并存储这个表，时间复杂度为 $O(N \log K_{max})$ 。
处理查询：对于每一次查询 $(start, k)$ ，我们可以利用倍增表快速求解。
- 我们将 $k$ 进行二进制分解。例如， $k=13$ ( $1101_2$ ) 相当于移动 $8+4+1$ 步。
- 我们从 current_pos = start - 1 开始，检查 $k$ 的二进制表示。如果第 $p$ 位是 $1$ ，我们就让 current_pos 执行一次 $2^p$ 步的跳转，即 current_pos = jump[p][current_pos]。
- 通过这种方式，我们可以在 $O(\log k)$ 的时间内完成一次查询。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

const int LOGK = 60; // 2^60 > 10^18, k的最大值

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, q;
    cin >> n >> m >> q;
    string s;
    cin >> s;

    string s_double = s + s;
    vector<int> prev_zero(2 * n, -1);
    if (s_double[0] == '0') {
        prev_zero[0] = 0;
    }
    for (int i = 1; i < 2 * n; ++i) {
        if (s_double[i] == '0') {
            prev_zero[i] = i;
        } else {
            prev_zero[i] = prev_zero[i - 1];
        }
    }

    vector<vector<int>> jump(LOGK, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        int farthest_zero_pos = prev_zero[i + m];
        if (farthest_zero_pos > i) {
            jump[0][i] = farthest_zero_pos % n;
        } else {
            jump[0][i] = (i + 1) % n;
        }
    }

    for (int p = 1; p < LOGK; ++p) {
        for (int i = 0; i < n; ++i) {
            jump[p][i] = jump[p - 1][jump[p - 1][i]];
        }
    }

    for (int i = 0; i < q; ++i) {
        int start;
        long long k;
        cin >> start >> k;
        int current_pos = start - 1;

        for (int p = LOGK - 1; p >= 0; --p) {
            if ((k >> p) & 1) {
                current_pos = jump[p][current_pos];
            }
        }
        cout << current_pos + 1 << "\n";
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    private static final int LOGK = 60; // 2^60 > 10^18

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();
        String s = sc.next();

        String sDouble = s + s;
        int[] prevZero = new int[2 * n];
        if (sDouble.charAt(0) == '0') {
            prevZero[0] = 0;
        } else {
            prevZero[0] = -1;
        }
        for (int i = 1; i < 2 * n; i++) {
            if (sDouble.charAt(i) == '0') {
                prevZero[i] = i;
            } else {
                prevZero[i] = prevZero[i - 1];
            }
        }

        int[][] jump = new int[LOGK][n];
        for (int i = 0; i < n; i++) {
            int farthestZeroPos = prevZero[i + m];
            if (farthestZeroPos > i) {
                jump[0][i] = farthestZeroPos % n;
            } else {
                jump[0][i] = (i + 1) % n;
            }
        }

        for (int p = 1; p < LOGK; p++) {
            for (int i = 0; i < n; i++) {
                jump[p][i] = jump[p - 1][jump[p - 1][i]];
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            int start = sc.nextInt();
            long k = sc.nextLong();
            int currentPos = start - 1;

            for (int p = LOGK - 1; p >= 0; p--) {
                if (((k >> p) & 1) == 1) {
                    currentPos = jump[p][currentPos];
                }
            }
            sb.append(currentPos + 1).append("\n");
        }
        System.out.print(sb.toString());
    }
}

def solve():
    n, m, q = map(int, input().split())
    s = input()
    
    LOGK = 60 # 2^60 > 10^18

    s_double = s + s
    prev_zero = [-1] * (2 * n)
    if s_double[0] == '0':
        prev_zero[0] = 0
    
    for i in range(1, 2 * n):
        if s_double[i] == '0':
            prev_zero[i] = i
        else:
            prev_zero[i] = prev_zero[i-1]

    jump = [[0] * n for _ in range(LOGK)]
    for i in range(n):
        farthest_zero_pos = prev_zero[i + m]
        if farthest_zero_pos > i:
            jump[0][i] = farthest_zero_pos % n
        else:
            jump[0][i] = (i + 1) % n

    for p in range(1, LOGK):
        for i in range(n):
            jump[p][i] = jump[p - 1][jump[p - 1][i]]

    results = []
    for _ in range(q):
        start, k = map(int, input().split())
        current_pos = start - 1
        
        for p in range(LOGK - 1, -1, -1):
            if (k >> p) & 1:
                current_pos = jump[p][current_pos]
        results.append(str(current_pos + 1))
        
    print("\n".join(results))

solve()

算法及复杂度

算法：倍增 (Binary Lifting)
时间复杂度： $O(N \cdot \log K_{max} + Q \cdot \log K_{max})$ 。其中 $N, Q, K$ 分别是字符串长度、查询次数和最大移动步数。预处理倍增表需要 $O(N \log K)$ ，每次查询需要 $O(\log K)$ 。
空间复杂度： $O(N \cdot \log K_{max})$ 。用于存储倍增表。