首页 > 试题广场 >

小红的坐标移动(Hard Version)

[编程题]小红的坐标移动(Hard Version)
  • 热度指数：27 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\,\,\,\,\,\,\,\,\,\,小红有一个一维的坐标系，上面一共有 n 个点，依次为 1,2,\dots,n ，她初始时位于 k 。现在她按照一个指令集合运动，如下：
\,\,\,\,\,\,\,\,\,\,● 指令 \tt L : 向左移动一个单位，如果当前位于 1 ，则原地不动。
\,\,\,\,\,\,\,\,\,\,● 指令 \tt R : 向右移动一个单位，如果当前位于 n ，则原地不动。
\,\,\,\,\,\,\,\,\,\,● 指令 \tt ? : 未知，小红将随机移动 L 或者 R 。
\,\,\,\,\,\,\,\,\,\,在经过所有指令运动后，小红想知道哪些位置有可能成为终点。如果该点可能成为终点，输出 1 ，否则输出 0 。

输入描述:
\,\,\,\,\,\,\,\,\,\,第一行输入两个整数 n,k\left(1 \leq n \leq 10^5;\ 1 \leq k \leq n\right) ，分别表示坐标系长度和小红的初始位置。
\,\,\,\,\,\,\,\,\,\,第二行输入一个长度不超过 10^5 、且仅由 \tt L 、\tt R 和 \tt ? 构成的字符串 s ，表示移动的指令集。


输出描述:
\,\,\,\,\,\,\,\,\,\,在一行上输出 n 个数字 a_1,a_2,\dots,a_n\left( 0\le a_i \le 1 \right) 代表每一个点是否可能成为小红的终点。
示例1

输入

3 2
RL?

输出

101

说明

\,\,\,\,\,\,\,\,\,\,小红会先向右一格到达 3 ，随后向左一格回到 2 ；由于第三个指令是 \tt ? ，小红有可能向左到达 1 ，也有可能向右到达 3 。
示例2

输入

5 2
?????

输出

11111
算法知识视频讲解
开通博客

暂无题解

问题信息

动态规划 位运算 模拟
来自：2024年秋招-蚂蚁集...
难度：
0条回答 107浏览

热门推荐

相关试题

小红的坐标移动(Hard Version)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号