青蛙跳跃问题

题目解析

这个问题要求我们判断青蛙在执行一系列包含确定指令（L、R）和不确定指令（?）后可能停留的位置。关键在于处理不确定指令的所有可能性，确定最终青蛙可能到达的所有位置。

解题思路

考虑到指令"?"可以是L或R，如果有多个"?"指令，我们需要考虑这些指令所有可能的组合。直接枚举所有可能性会导致指数级复杂度，这对于长度达10^6的指令序列是不可行的。

我发现可以用一种更高效的方法：跟踪青蛙可能到达的位置范围。具体来说，维护两个范围：

1. 外部范围(left到right)：表示青蛙一定可以到达的区域边界
2. 内部范围(inner_left到inner_right)：表示一个特殊区域，在这个区域内的位置按照特定模式（交替的0和1）可达

当遇到不同指令时：

• L指令：整体向左移动
• R指令：整体向右移动
• ?指令：结合L和R的效果，扩展可能位置的范围

算法复杂度

• 时间复杂度：O(|S|)，其中|S|是指令字符串的长度。我们只需遍历一次指令串。
• 空间复杂度：O(1)，只使用了常数级额外空间。

C++代码

#include <bits/stdc++.h>
using namespace std;

// 用于跟踪青蛙可能位置的结构体
struct Move {
    int left, right;         // 外部范围，这个范围内青蛙都可能到达
    int inner_left, inner_right; // 内部范围，这个范围内青蛙按特定模式可达
    int n; // 边界1到n
    // 构造函数，初始化单一位置
    Move(int idx, int n) {
        this->left = this->right = idx;
        this->inner_left = this->inner_right = -1; // -1表示没有内部范围
        this->n = n;
    }
    
    Move() {}
    
    // 处理L指令：向左移动
    Move moveLeft() {
        Move res;
        // 更新外部范围
        res.left = max(this->left - 1, 0);
        res.right = max(this->right - 1, 0);
        res.inner_left = -1;
        res.inner_right = -1;
        
        // 更新内部范围
        if (this->inner_left != -1) {
            if (this->inner_left - 1 == 0) {
                // 处理内部左边界
                res.inner_left = this->inner_left + 1;
                res.inner_right = this->inner_right - 1;
                if (res.inner_left > res.inner_right) {
                    res.inner_left = res.inner_right = -1;
                }
            } else {
                // 整体左移
                res.inner_left = this->inner_left - 1;
                res.inner_right = this->inner_right - 1;
            }
        }
        return res;
    }
    
    // 处理R指令：向右移动
    Move moveRight() {
        Move res;
        // 更新外部范围
        res.left = min(this->left + 1, n - 1);
        res.right = min(this->right + 1, n - 1);
        res.inner_left = -1;
        res.inner_right = -1;
        
        // 更新内部范围
        if (this->inner_left != -1) {
            if (this->inner_right + 1 == n - 1) {
                // 处理内部右边界
                res.inner_left = this->inner_left + 1;
                res.inner_right = this->inner_right - 1;
                if (res.inner_left > res.inner_right) {
                    res.inner_left = res.inner_right = -1;
                }
            } else {
                // 整体右移
                res.inner_left = this->inner_left + 1;
                res.inner_right = this->inner_right + 1;
            }
        }
        return res;
    }
    
    // 处理?指令：同时考虑左移和右移
    Move moveRandom() {
        Move res;
        // 更新外部范围（扩大范围）
        res.left = max(this->left - 1, 0);
        res.right = min(this->right + 1, n - 1);
        res.inner_left = -1;
        res.inner_right = -1;
        
        // 更新内部范围
        if (this->inner_left != -1) {
            // 左边界处理
            if (this->left + 1 == this->inner_left && this->left != 0) {
                res.inner_left = this->inner_left - 1;
            } else {
                res.inner_left = this->inner_left + 1;
            }
            
            // 右边界处理
            if (this->right - 1 == this->inner_right && this->right != n - 1) {
                res.inner_right = this->inner_right + 1;
            } else {
                res.inner_right = this->inner_right - 1;
            }
            
            // 如果内部范围无效，则清除
            if (res.inner_left > res.inner_right) {
                res.inner_left = res.inner_right = -1;
            }
        } else if (this->left == this->right && this->left > 0 && this->left + 1 < n) {
            // 创建新的内部范围
            res.inner_left = res.inner_right = this->left;
        }
        return res;
    }
};

int main(void) {
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    
    // 初始化，青蛙在位置k
    Move f(k - 1, n);  // 转为0-indexed
    
    // 处理每条指令
    for (char c : s) {
        if (c == 'L') {
            f = f.moveLeft();
        } else if (c == 'R') {
            f = f.moveRight();
        } else {  // c == '?'
            f = f.moveRandom();
        }
    }
    
    // 输出结果
    for (int i = 0; i < n; i++) {
        if (f.inner_left <= i && i <= f.inner_right) {
            // 内部范围：交替输出0和1
            cout << (i - f.inner_left) % 2;
        } else if (f.left <= i && i <= f.right) {
            // 外部范围：输出1
            cout << 1;
        } else {
            // 其他位置：输出0
            cout << 0;
        }
    }
    cout << endl;
    
    return 0;
}

Java代码

import java.util.Scanner;

public class Main {
    static int n;
    
    // 用于跟踪青蛙可能位置的类
    static class Move {
        int left, right;  // 外部范围
        int inner_left, inner_right;  // 内部范围
        
        // 构造函数，初始化单一位置
        public Move(int idx) {
            this.left = this.right = idx;
            this.inner_left = this.inner_right = -1;  // -1表示没有内部范围
        }
        
        public Move() {}
        
        // 处理L指令：向左移动
        public Move moveLeft() {
            Move res = new Move();
            // 更新外部范围
            res.left = Math.max(this.left - 1, 0);
            res.right = Math.max(this.right - 1, 0);
            res.inner_left = -1;
            res.inner_right = -1;
            
            // 更新内部范围
            if (this.inner_left != -1) {
                if (this.inner_left - 1 == 0) {
                    // 处理内部左边界
                    res.inner_left = this.inner_left + 1;
                    res.inner_right = this.inner_right - 1;
                    if (res.inner_left > res.inner_right) {
                        res.inner_left = res.inner_right = -1;
                    }
                } else {
                    // 整体左移
                    res.inner_left = this.inner_left - 1;
                    res.inner_right = this.inner_right - 1;
                }
            }
            return res;
        }
        
        // 处理R指令：向右移动
        public Move moveRight() {
            Move res = new Move();
            // 更新外部范围
            res.left = Math.min(this.left + 1, n - 1);
            res.right = Math.min(this.right + 1, n - 1);
            res.inner_left = -1;
            res.inner_right = -1;
            
            // 更新内部范围
            if (this.inner_left != -1) {
                if (this.inner_right + 1 == n - 1) {
                    // 处理内部右边界
                    res.inner_left = this.inner_left + 1;
                    res.inner_right = this.inner_right - 1;
                    if (res.inner_left > res.inner_right) {
                        res.inner_left = res.inner_right = -1;
                    }
                } else {
                    // 整体右移
                    res.inner_left = this.inner_left + 1;
                    res.inner_right = this.inner_right + 1;
                }
            }
            return res;
        }
        
        // 处理?指令：同时考虑左移和右移
        public Move moveRandom() {
            Move res = new Move();
            // 更新外部范围（扩大范围）
            res.left = Math.max(this.left - 1, 0);
            res.right = Math.min(this.right + 1, n - 1);
            res.inner_left = -1;
            res.inner_right = -1;
            
            // 更新内部范围
            if (this.inner_left != -1) {
                // 左边界处理
                if (this.left + 1 == this.inner_left && this.left != 0) {
                    res.inner_left = this.inner_left - 1;
                } else {
                    res.inner_left = this.inner_left + 1;
                }
                
                // 右边界处理
                if (this.right - 1 == this.inner_right && this.right != n - 1) {
                    res.inner_right = this.inner_right + 1;
                } else {
                    res.inner_right = this.inner_right - 1;
                }
                
                // 如果内部范围无效，则清除
                if (res.inner_left > res.inner_right) {
                    res.inner_left = res.inner_right = -1;
                }
            } else if (this.left == this.right && this.left > 0 && this.left + 1 < n) {
                // 创建新的内部范围
                res.inner_left = res.inner_right = this.left;
            }
            return res;
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        int k = scanner.nextInt();
        String s = scanner.next();
        
        // 初始化，青蛙在位置k
        Move f = new Move(k - 1);  // 转为0-indexed
        
        // 处理每条指令
        for (char c : s.toCharArray()) {
            if (c == 'L') {
                f = f.moveLeft();
            } else if (c == 'R') {
                f = f.moveRight();
            } else {  // c == '?'
                f = f.moveRandom();
            }
        }
        
        // 输出结果
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (f.inner_left <= i && i <= f.inner_right) {
                // 内部范围：交替输出0和1
                result.append((i - f.inner_left) % 2);
            } else if (f.left <= i && i <= f.right) {
                // 外部范围：输出1
                result.append(1);
            } else {
                // 其他位置：输出0
                result.append(0);
            }
        }
        System.out.println(result.toString());
        
        scanner.close();
    }
}

Python代码

class Move:
    def __init__(self, idx=None):
        if idx is not None:
            # 初始化单一位置
            self.left = self.right = idx
            self.inner_left = self.inner_right = -1  # -1表示没有内部范围
        else:
            self.left = self.right = 0
            self.inner_left = self.inner_right = -1
    
    # 处理L指令：向左移动
    def move_left(self):
        res = Move()
        # 更新外部范围
        res.left = max(self.left - 1, 0)
        res.right = max(self.right - 1, 0)
        
        # 更新内部范围
        if self.inner_left != -1:
            if self.inner_left - 1 == 0:
                # 处理内部左边界
                res.inner_left = self.inner_left + 1
                res.inner_right = self.inner_right - 1
                if res.inner_left > res.inner_right:
                    res.inner_left = res.inner_right = -1
            else:
                # 整体左移
                res.inner_left = self.inner_left - 1
                res.inner_right = self.inner_right - 1
        return res
    
    # 处理R指令：向右移动
    def move_right(self):
        res = Move()
        # 更新外部范围
        res.left = min(self.left + 1, n - 1)
        res.right = min(self.right + 1, n - 1)
        
        # 更新内部范围
        if self.inner_left != -1:
            if self.inner_right + 1 == n - 1:
                # 处理内部右边界
                res.inner_left = self.inner_left + 1
                res.inner_right = self.inner_right - 1
                if res.inner_left > res.inner_right:
                    res.inner_left = res.inner_right = -1
            else:
                # 整体右移
                res.inner_left = self.inner_left + 1
                res.inner_right = self.inner_right + 1
        return res
    
    # 处理?指令：同时考虑左移和右移
    def move_random(self):
        res = Move()
        # 更新外部范围（扩大范围）
        res.left = max(self.left - 1, 0)
        res.right = min(self.right + 1, n - 1)
        
        # 更新内部范围
        if self.inner_left != -1:
            # 左边界处理
            if self.left + 1 == self.inner_left and self.left != 0:
                res.inner_left = self.inner_left - 1
            else:
                res.inner_left = self.inner_left + 1
            
            # 右边界处理
            if self.right - 1 == self.inner_right and self.right != n - 1:
                res.inner_right = self.inner_right + 1
            else:
                res.inner_right = self.inner_right - 1
            
            # 如果内部范围无效，则清除
            if res.inner_left > res.inner_right:
                res.inner_left = res.inner_right = -1
        elif self.left == self.right and self.left > 0 and self.left + 1 < n:
            # 创建新的内部范围
            res.inner_left = res.inner_right = self.left
        return res

# 读取输入
n, k = map(int, input().split())
s = input().strip()

# 初始化，青蛙在位置k
f = Move(k - 1)  # 转为0-indexed

# 处理每条指令
for c in s:
    if c == 'L':
        f = f.move_left()
    elif c == 'R':
        f = f.move_right()
    else:  # c == '?'
        f = f.move_random()

# 生成结果
result = ""
for i in range(n):
    if f.inner_left <= i <= f.inner_right:
        # 内部范围：交替输出0和1
        result += str((i - f.inner_left) % 2)
    elif f.left <= i <= f.right:
        # 外部范围：输出1
        result += "1"
    else:
        # 其他位置：输出0
        result += "0"

print(result)

题目内容

小美有一个一维的坐标系，上面一共有$n$个点，依次为$1,2,...,n$，她有一只遥控青蛙，初始时位于$k$。现在，她在纸上书写了一个指令集:

• 指令$L$:指挥青蛙向左移动一个单位，如果当前位于$1$，则原地不动。
• 指令$R$:指挥青蛙向右移动一个单位，如果当前位于$n$，则原地不动。
• 指令$?$:未知，随机变成$L$或者$R$，并指挥青蛙移动。

对于指令$?$的全部可能取值，小美想知道青蛙最终有概率停在哪些位置。如果该点可能成为终点，输出$1$，否则输出$0$

输入描述

第一行输入两个整数$n,k(1≤n≤10^6;1≤k≤n)$分别表示坐标系长度和青娃的初始位置。

第二行输入一个长度不超过$10^6$且仅由$L,R$和$?$构成的字符串$S$，表示移动的指令集。

输出描述

在一行上输出 $n$个数字$a_1,a_2,...,a_n(0≤a_i≤1)$代表

每一个点是否可能成为青蛙的终点，数字之间不必使用空格隔开。

样例1

输入

3 2
RL?

输出

101

说明

青蛙会先向右一格到达$3$，随后向左一格回到$2$；由于第三个指令是$?$，小红有可能指挥青蛙向左到达1，也有可能向右到达$3$。

样例2

输入

5 2
?????

输出

11111