专栏文章

P2027 bf 题解

CCleanIce
P2027题解参与者 7已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
2 份
快照标识符
@mkktvww8
此快照首次捕获于
2026/01/19 15:12
上个月
此快照最后确认于
2026/01/19 15:12
上个月
查看原文

P2027 bf 题解

原题链接。

原题简述

一看就是模拟题，让我们写一个 BF 语言的解释器。给我们提供了容量为 3000030000 字节的内存，全部初始化为 00。还有内存指针，指向内存开始的位置。
然后说代码的字符集及其含义。这里进行了整理和修改，应该更好理解：
代码字符含义
>将内存指针右移（内存地址加一）。
<将内存指针左移（内存地址减一）。
+将存储在当前内存的值加一。
-将存储在当前内存的值减一。
,从输入流读取一个字符，并将其 ASCII 码存储到当前内存中。若输入流没有更多字符，存入 −1-1。
.将当前内存的值以 ASCII 码表翻译为字符后输出。
[循环开始。若当前内存值为 00，跳过直到与其配对的 ]。否则继续执行。
]循环结束。跳回与其配对的 [。
就是这么些简单的字符，实现也非常简单。但 BF 语言并不简单，它甚至达到了高级编程语言的基本标准：图灵完备。这里是题外话就不展开了。
然后说输入的数据格式为：
CPP
代码$ 输入流 $
注意空格的位置。输入流与左右两个 $ 符号之间有一个空格，但代码与第一个 $ 之间并没有！读入的时候需要注意。
另外，题目中说到的“代码中有注释”，注释指的是代码中除了上述字符集内字符之外的所有字符（不包括 $）。因此我们需要忽略它们。
下面来想想思路。

做题思路

先设几个变量，方便讲述（为了使使用其他语言的读者看懂，此处不考虑指针操作）：
  • code\text{code}：当前运行到的代码的字符。
  • input\text{input}：当前输入流准备读入的下一个字符。若没有更多字符，我们令 input←∅\text{input} \gets \varnothing。
  • mem\text{mem}：存储在当前内存的值。
  • addr\text{addr}：当前内存地址。
我们假设内存条越往右地址越大，初始地址为 00。
那么，我们一个个看字符集中的代码该如何处理：
  1. > 右移操作符：将当前内存地址增加一。也就是：addr←addr+1\text{addr} \gets \text{addr} + 1。
  2. < 左移操作符：将当前内存地址减少一。也就是：addr←addr−1\text{addr} \gets \text{addr} - 1。
  3. + 自增操作符：将存储在当前内存的值加一。也就是：mem←mem+1\text{mem} \gets \text{mem} + 1。
  4. - 自减操作符：将存储在当前内存的值减一。也就是：mem←mem−1\text{mem} \gets \text{mem} - 1。
  5. , 输入操作符：从输入流读入一个字符，并存储到当前内存位置。如果输入流没有更多字符，存入 −1-1。也就是：mem←{inputinput≠∅−1input=∅\text{mem} \gets \begin{cases} \text{input} & \text{input} \ne \varnothing \\ -1 & \text{input} = \varnothing \end{cases}，随后令 input←下一个输入流中的字符\text{input} \gets \text{下一个输入流中的字符}。
  6. . 输出操作符：将存储在当前内存的值按照 ASCII 表作为字符输出。也就是输出 mem\text{mem}。
接下来就是比较难的两个。上面在将字符集的时候说，就是跳到配对的目标括号。如何寻找配对的括号呢？
且看这一段字符：
CPP
+[+[>[,]-]+].
很明显，如果我们要找到第一个 [ 配对的字符，就是第三个 ]，第二个 [ 就是第二个 ]。
只要记录一共遇到了几个 [ 和几个 ] 就行了。也就是说，寻找第一个 [ 配对的符号时，还会遇到两个 [，找到两个 ] 并忽略后，第三个 ] 就是配对的了。寻找第二个 [ 配对的符号时，还会遇到一个 [，找到一个 ] 并忽略后，第二个 ] 就是配对的了。因此，写出伪代码：
CPP
// 伪代码
// count 为需要寻找的个数
count <- 1
ch <- #当前字符#
while (count != 0):
    if ch = '[':
        count <- count + 1
    elseif ch = ']':
        count <- count - 1
    ch <- #下一个字符#
ch <- #回退到上一个字符#
// 此时 ch 就是配对的 ]
] 符号同理，不再重复。

代码专区

我提供了现代化 C++ 代码和传统的 OI 代码。对于洛谷少数的程序设计人员（或非竞赛选手），可以看现代化的代码。对于 oiers，可以尝试阅读现代化代码，或者就直接看传统 OI 型的代码。两份代码都给了注释，其中现代化代码还给了技术注释。两份代码效率差不多（现代化的我测了一下可能还快一些）。
现代化代码使用了 C++23 的新特性，因此洛谷上提交不了（可能你也运行不了）。你可以根据我的注释修改为 C++20 以内的代码使用，当然也可以提交。
传统 OI 代码就给你们自己看吧。
由于代码长度比较长，我把它放到剪贴板里了。
代码在这里

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...