🎮 正序模拟过试炼，空间逆推破天机

距离上次在字母大陆抓“双面间谍”已经过去好一阵子了。我本以为那片大陆的服务器早已关服，大家各自安好。没想到今天一大早，我正蹲在火炉边嗦泡面，窗户就被啄得砰砰作响——一只明显没睡醒的鸽子叼着封信，扑腾了两下，精准地一头栽进了我的泡面碗里。

我捞出那封湿漉漉的羊皮纸信，展开一看，上面赫然是村长那仿佛被狗啃过一样的狂草：“小白！字母大陆更新资料片了！那些字母不知道怎么搞的，混进了一批‘魔法操作符’——星号、井号和百分号。现在整条字符串就像被施了咒一样，你得按照规则从左到右处理每个字符，才能还原出最终的真言！规则如下——”

• 小写字母：正常添加到结果中；
• '*'：退格符，删掉结果中的最后一个字母（如果有的话）；
• '#'：复制符，把当前的结果复制一份，追加到自身后面；
• '%'：反转符，把当前的结果整个倒过来。

“这不就是纯纯的字符串模拟吗？”我看着这一大串规则，眉头微挑，“只要建个空列表，按顺序遍历一遍，遇到啥操作就执行啥，最后返回结果不就完事了？”

栈式模拟：result就是一个操作栈

我把那只还在碗里打嗝的鸽子拎出去，抄起键盘开始敲代码：这种从左到右逐字符处理的任务，核心就是一个可变的result字符串。Python里直接拿list当栈用——字母来了就append，星号来了就pop，井号和百分号稍微复杂点但也都是列表操作，整个流程就是一台简单的状态机。

def applyOperations(self, s: str) -> str:
    result = []
    for ch in s:
        if ch == '*':
            if result:
                result.pop()           # 退格
        elif ch == '#':
            result = result + result   # 复制
        elif ch == '%':
            result.reverse()           # 反转
        else:
            result.append(ch)          # 追加
    return ''.join(result)

写完，提交，AC！我刚惬意地靠到椅背上，后脑勺又"啪"地挨了轻轻一下——力道极其精准，刚好能让我精神一振，又不至于把我拍痛。

“又来？” 我捂着后脑勺，不用回头就知道是谁。

“逻辑清晰，没有遗漏，时间复杂度也合格。” 老勇者慢条斯理地说道，“但是小白啊，你有没有想过一个问题？”

我叹了口气，熟练地摆出虚心求教的姿态：“什么问题？难道我的 if-elif 分支不够优雅？”

“内存问题。”老勇者指着屏幕上那行 result = result + result，“你看这个 # 操作，如果遇到连续的几个 #，比如 a##，你的 result 会瞬间从长度 1 变成 2，再变成 4。每次翻倍，你都在重新分配一块新内存，把整个 result 从头到尾拷贝一遍。”

他又指了指数据范围：“现在这题 s.length ≤ 20，最极端的情况——一个 a 后面跟 19 个 # 号。19次翻倍之后，result 最终长度是 2 的 19 次方，大约 52 万个字符。内存占用也就 4 到 5 兆，中间所有拷贝操作加起来大概一百万次元素复制，Python 眨个眼就完事了。“

老勇者顿了顿，眼神变得深邃起来：“ 你的模拟现在能 AC，不是因为它没问题，是数据量太小，小到把问题捂住了。这就好比你在澡盆里试航一艘纸船——不漏水，不代表它能出海。”

“如果把 s 的长度提到十万呢？或者仅仅是 a 后面跟上 49 个 # 号——49次翻倍，result 长度变成 2 的 49 次方，” 老勇者瞅了我一眼，“你知道那占多少内存吗？大约 4.5 PB。别说你的电脑，全村锅炉房的魔法硬盘加起来都塞不下。到时候直接一个 MemoryError，原地炸锅。”

我盯着代码，倒吸一口凉气。刚才跑样例还觉得模拟挺丝滑，现在一想——那不过是因为策划手下留情，把数据范围压到了 20。如果数据量不加限制，# 号的指数膨胀就是一颗定时炸弹，只等大数据量的 II 版本一发布就引爆。

“那 …… II 版本怎么办？”我挠着头，刚 AC 的喜悦凉了大半，“如果要返回整个字符串，模拟肯定扛不住啊！”

“问得好。”老勇者神秘一笑，眼角的皱纹都透着狡黠，“如果 II 版本不问整个字符串，只问你一个问题——最终 result 的第 k 个字符是什么？你还会爆内存吗？”

我愣住了。只找第 k 个字符？那确实不用把整个 result 算出来，只需要知道k位置上的字符是谁就行了——就像你不需要把整卷录像带从头放一遍，只需定位到第 k 帧，看一眼那一帧的画面就够了。

“可是……” 我追问，“不存整个 result，怎么知道第 k 个位置上的字符是从哪来的？”

找第 k 个字符？那又是另一个故事了

“换个角度——”

老勇者拿过笔，在纸上画了一条长横线，然后在线中间画了一道竖杠，把横线一分为二。“你看，每次#号操作，本质上是把当前字符串一式两份——左边是原来的，右边是复制出来的。%号呢，是把左边倒过来。* 号是把最右边那个删掉。” 他把笔尖在那条竖杠上敲了敲，“仔细看，每种操作，都在字符串的空间结构上留下了痕迹。”

“ 假设你经过 n 次#操作后，最终字符串的长度膨胀到了 2 的 n 次方。那么第 k 个字符，它一定在这个庞然大物的某一半里。要么在左半边，要么在右半边。如果是右半边，它一定是被某个#号从左边复制过去的；如果是左半边，它根本没被那次#号影响。%号同理——如果一个字符在反转区间里，它的实际来源一定在对称位置。”

我盯着纸上那条竖杠，脑子里突然闪过一道光：“等等——所以我不需要把整个字符串造出来？只需要拿着 k，从最后一个操作开始往前推，判断它落在当前区间的哪一半，然后反向映射回去？”

“正是。”老勇者把笔一搁，“每次操作都在改变字符串的几何结构——# 号是复制对称，% 号是镜像对称，* 号是末端删减。你从最终位置出发，一层一层剥开这些操作，就能追溯到最初的来源。”

他顿了顿，看着我若有所思的表情，嘴角勾起一抹意味深长的笑：“今天先把这个‘空间结构’的直觉消化下。具体怎么从后往前推、怎么判断左半右半、怎么处理反转映射……明天再教你。”

他站起身朝门口走去，走到门边又停了一下：“心法先入脑，招式才使得出来。”

门轻轻关上。我重新看向屏幕上那段刚 AC 的模拟代码——刚才还觉得它挺靠谱，现在再看，那行 result = result + result 简直像在嘲笑我：你能 AC，是因为策划给你放了片海。

我默念着老勇者的心法：“#号是复制对称，%号是镜像对称，*号是末端删减。找第 k 个字符，就是在一场逆向追踪里，从终点坐标一路剥开层层嵌套的几何变换，精准锁定最初的’本体‘。” 哪天村长真把我扔进 II 版本那 4.5 PB 的虚空里，我还得靠这套“空间逆推”的招式，捞出唯一的真相。

本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。