题目链接

移动

题目描述

小红在一个一维坐标轴上移动，初始位置为 0。她有一个长度为 的指令字符串 ，由 > (向右, +1) 和 < (向左, -1) 组成。

对于每一个可能的出发点 (从 1 到 )，你需要判断：如果小红从指令 开始，依次执行后续的指令 ()，她是否有机会在执行了至少一个指令后，恰好回到原点 0。

你需要对所有的 个出发点进行判断，并输出一个包含 个 0 或 1 的结果。

解题思路

这是一个典型的路径求和问题，直接对每个出发点进行模拟会导致 的复杂度，对于 的数据范围会超时。我们需要一个更高效的算法，而前缀和是解决此类问题的经典工具。

问题转化

首先，我们将移动指令数字化：> 对应 +1，< 对应 -1。 对于一个从第 个字符（0-indexed 为 ）开始的移动序列，如果在 步之后（）回到原点，意味着从第 个到第 个指令的代数和为 0。

利用前缀和

为了快速计算任意区间的指令和，我们引入前缀和数组 pref。 令 pref[k] 表示执行完前 个指令后的最终位置。即 pref[k] = sum(val(S[0...k-1]))。我们定义 pref[0] = 0。

那么，从第 个指令开始，执行到第 个指令（）的总位移就是 sum(val(S[i-1...p]))。这可以通过前缀和数组表示为 pref[p+1] - pref[i-1]。

我们要判断的是：对于一个起始点 ，是否存在一个结束点 ，使得 pref[p+1] - pref[i-1] = 0？ 这个条件等价于：是否存在一个索引 (令 )，使得 pref[k] == pref[i-1]。

高效求解

现在问题被转化成了：对于 pref 数组中的每一个位置 i-1，我们需要判断它的值 pref[i-1] 是否在数组的后续部分 pref[i...n] 中再次出现。

一个非常高效的实现方法是，预先计算出 pref 数组中每个数值最后一次出现的位置。

  1. 计算前缀和数组 pref： 创建一个大小为 的数组。pref[0] = 0。遍历指令字符串，计算出 pref[1] 到 pref[n]。

  2. 记录最后出现位置： 创建一个哈希表（map 或 unordered_map），记为 last_pos。遍历 pref 数组（从索引 0 到 ），对于 pref 中的每个值，更新 last_pos 中该值对应的索引。遍历结束后，last_pos[v] 将存储值 v 在 pref 数组中最后一次出现的索引。

  3. 判断并生成结果： 遍历所有出发点 （从 1 到 ，对应 pref 数组索引 ）：

    • 获取当前出发点对应的前缀和值 val = pref[i-1]。
    • 查询哈希表，得到 val 最后出现的索引 last_idx = last_pos[val]。
    • 如果 last_idx > i-1，这意味着 val 在当前位置之后再次出现了，说明可以回到原点。结果为 1。
    • 否则，说明 val 没有在后面再次出现，无法回到原点。结果为 0。

这个算法的每一步都是线性的，因此总时间复杂度为 ，空间复杂度也为 ，足以应对本题的数据范围。

代码

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

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

    int n;
    cin >> n;
    string s;
    cin >> s;

    vector<long long> pref(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        pref[i + 1] = pref[i] + (s[i] == '>' ? 1 : -1);
    }

    unordered_map<long long, int> last_pos;
    for (int i = 0; i <= n; ++i) {
        last_pos[pref[i]] = i;
    }

    for (int i = 0; i < n; ++i) {
        long long current_val = pref[i];
        if (last_pos[current_val] > i) {
            cout << 1 << (i == n - 1 ? "" : " ");
        } else {
            cout << 0 << (i == n - 1 ? "" : " ");
        }
    }
    cout << endl;

    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String s = br.readLine();

        long[] pref = new long[n + 1];
        pref[0] = 0;
        for (int i = 0; i < n; i++) {
            pref[i + 1] = pref[i] + (s.charAt(i) == '>' ? 1 : -1);
        }

        Map<Long, Integer> lastPos = new HashMap<>();
        for (int i = 0; i <= n; i++) {
            lastPos.put(pref[i], i);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            long currentVal = pref[i];
            if (lastPos.get(currentVal) > i) {
                sb.append("1");
            } else {
                sb.append("0");
            }
            if (i < n - 1) {
                sb.append(" ");
            }
        }
        System.out.println(sb.toString());
    }
}

import sys

def solve():
    n = int(sys.stdin.readline())
    s = sys.stdin.readline().strip()

    pref = [0] * (n + 1)
    for i in range(n):
        pref[i+1] = pref[i] + (1 if s[i] == '>' else -1)
    
    last_pos = {}
    for i, val in enumerate(pref):
        last_pos[val] = i
        
    ans = []
    for i in range(n):
        current_val = pref[i]
        if last_pos[current_val] > i:
            ans.append("1")
        else:
            ans.append("0")
            
    print(" ".join(ans))

solve()

算法及复杂度

  • 算法：前缀和、哈希表
  • 时间复杂度：。构建前缀和数组需要 ，构建最后出现位置的哈希表需要 ，最后遍历并查询生成结果也需要 。
  • 空间复杂度：。前缀和数组需要 的空间，哈希表在最坏情况下（所有前缀和都不同）也需要 的空间。