题解

题面描述

给定一个长度为$n$的字符串$s$（$s$仅包含字符$'<'$和$'>'$），其中字符$'<'$代表向左移动，$'>'$代表向右移动。对于每个起始位置$i$（$0 \le i < n$），小红按照顺序依次执行$s_i, s_{i+1}, s_{i+2}, \dots$中的指令，但不必执行到字符串末尾。要求判断是否存在某个非空前缀，使得执行后小红能够回到原点（即净位移为$0$）。对于每个$i$，输出$1$表示存在这种可能，输出$0$表示不存在。

思路

令每个字符对应的移动量为：

• $a_j=+1$ 当$s[j] = '>'$
• $a_j=-1$ 当$s[j] = '<'$

设定义前缀和数组$P$满足
$P[0]=0$,$P[k]=a_0+a_1+\cdots+a_{k-1}$$(1\le k\le n)$

从起点$i$出发，执行$L$个指令后的位移为

因此要求存在$L\ge1$使得
$P[i+L]-P[i]$=0$\quad\Longleftrightarrow\quad$ $P[i+L]=P[i]$

换句话说，对于每个$i$，如果在区间$[i+1,n]$内存在某个位置$k$使得$P[k]=P[i]$，则答案为$1$，否则为$0$。

一种简单高效的方法是预处理整个$P$数组，并统计每个值最后出现的位置。对于每个$i$（对应$P[i]$），若该值最后出现的位置大于$i$，则说明后续至少存在一个位置使得前后前缀和相等。

C++

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    string s;
    cin >> s;
    
    // 计算前缀和，P[0]=0, P[i+1]=P[i]+(s[i]=='>'? 1 : -1)
    vector<int> P(n+1, 0);
    for (int i = 0; i < n; i++){
        P[i+1] = P[i] + (s[i] == '>' ? 1 : -1);
    }
    
    // 记录每个前缀和最后出现的位置
    unordered_map<int,int> lastPos;
    for (int i = 0; i <= n; i++){
        lastPos[P[i]] = i; // 每次覆盖即为最后出现位置
    }
    
    // 对于每个起始位置 i, 判断是否存在 k (i+1 <= k <= n) 使得 P[k]==P[i]
    for (int i = 0; i < n; i++){
        if (lastPos[P[i]] > i)
            cout << 1 << " ";
        else
            cout << 0 << " ";
    }
    
    return 0;
}

Python

# -*- coding: utf-8 -*-
# 读入数据
n = int(input().strip())
s = input().strip()

# 计算前缀和, P[0] = 0, P[i+1] = P[i] + (1 if s[i]=='>' else -1)
P = [0]*(n+1)
for i in range(n):
    P[i+1] = P[i] + (1 if s[i]=='>' else -1)

# 记录每个前缀和最后出现的位置
lastPos = {}
for i in range(n+1):
    lastPos[P[i]] = i  # 每次覆盖为最后一次出现

# 对于每个起始位置 i, 判断是否存在 k (i+1 <= k <= n) 使得 P[k] == P[i]
res = []
for i in range(n):
    if lastPos[P[i]] > i:
        res.append("1")
    else:
        res.append("0")
        
print(" ".join(res))

Java 解法

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 加速输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String s = br.readLine().trim();
        
        // 计算前缀和, P[0] = 0, P[i+1] = P[i] + (s.charAt(i)=='>'? 1 : -1)
        int[] P = new int[n+1];
        for (int i = 0; i < n; i++) {
            P[i+1] = P[i] + (s.charAt(i) == '>' ? 1 : -1);
        }
        
        // 使用 HashMap 记录每个前缀和最后出现的位置
        HashMap<Integer, Integer> lastPos = new HashMap<>();
        for (int i = 0; i <= n; i++) {
            lastPos.put(P[i], i); // 每次put覆盖即为最后出现位置
        }
        
        // 对于每个起始位置 i, 判断是否存在 k (i+1 <= k <= n) 使得 P[k] == P[i]
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (lastPos.get(P[i]) > i)
                sb.append("1 ");
            else
                sb.append("0 ");
        }
        
        System.out.println(sb.toString().trim());
    }
}

题目内容

小红在一维度的世界中，她可以向左或者向右移动。她拿到一个长度为$n$的字符串$s$，仅包含'$<$'和'$>$' 两种字符，'$<$' 表示向左移动，'$>$'表示向右移动。

小红想知道，如果从字符串$s$的第$i(0≤i<n)$个字符开始,然后按照$S_i,S_{i+1},S_{i+2},...$的顺序依次移动，那么小红有没有机会回到原地。

值得注意的是，你需要对于任意的$i(0≤i<n)$ 都判断是否存在一种移动方式，使得小红可以回到原地且不一定需要执行到$s_{n-1}$，每个$i$的判断互不影响。

输入描述

第一行一个整数$n(1≤n≤2×10^5)$,表示字符串s的长度。

第二行一个字符串$s$，仅包含'$<$'和'$>$'两种字符。

输出描述

输出$n$个整数，第$i$个整数表示从第$i$个字符开始移动，小红有没有机会回到原地，若有机会输出$1$，否则输出$0$。

样例1

输入

4
><><

输出

1 1 1 0