🎮倒转乾坤寻真身，去冗存真见精神
早上，我刚把一碗热气腾腾的泡面端上桌，准备享受这碳水与油脂交织的美好清晨，窗户又发出了熟悉的“砰砰”声。我眼疾手快地把碗往旁边一挪，果不其然，那只掉毛的信鸽像一架失去动力的无人机，精准地砸向桌面。
“你就不能换个着陆点？”我把鸽子往旁边拨了拨，熟练地抽出它嘴里叼着的羊皮纸。展开一看，村长的狂草再次扑面而来：“小白！字母大陆又更新了！这次不要求返回整个密文，只要求返回最终密文的第 k 个字母（下标从 0 开始）！如果 k 越界了，就返回一个 .！另外，字符串长度上限已经放宽到 10^5 ，祝你好运！”
“果然来了。” 我盯着那个 10^5，昨天 19 个井号就炸出 52 万个字符，模拟还能硬扛；今天 s 的长度放到十万，里面说不定藏着一整支井号军团。模拟要是敢上场，评测机怕是要把我的提交记录裱起来挂在“反面教材”专栏里。
我深吸一口气，把昨天老勇者画的那张竖杠图从魔法书里抽出来，平铺在桌上。
昨天老勇者已经给我透了底，说这类题是“空间逆推”的主场——“#号是复制对称，%号是镜像对称，*号是末端删减。找第 k 个字符，就是在一场逆向追踪里，从终点坐标一路剥开层层嵌套的几何变换，精准锁定最初的‘本体’。”
这段心法我在脑子里念叨了半宿，连做梦都在算对称位置。今天，是时候上招式了。
正向探路，反向溯源
开干之前先盘逻辑。昨天老勇者留下的话头很清楚——逆向追踪，从终点坐标一路剥开层层嵌套的几何变换。但在那之前，我得先正向探路，记下沿路操作对字符串几何结构的影响。就像顺着折痕一路摸回纸片最初的形状，首先得知道每次对折、翻面、撕角之后，纸片变成了多大。不需要知道纸上写了什么字，只需要知道尺寸。
“第一步，正向探路。”
我在纸上画了一个从左到右的箭头，“还是从左到右扫一遍操作序列，但不存实际字符，只记录每一步之后 result 的长度。字母来了，长度加一；星号来了，长度减一；井号来了，长度翻倍；百分号来了，长度不变。一趟扫完，我手里就有一张‘长度变化表’——每个操作时刻，result 有多长，清清楚楚。”
# 正向扫描，只记长度
n = len(s)
size = [0] * n
for i, c in enumerate(s):
if c.isalpha():
size[i] = (size[i - 1] if i > 0 else 0) + 1
elif c == '*':
size[i] = max(0, (size[i - 1] if i > 0 else 0) - 1)
elif c == '#':
size[i] = (size[i - 1] if i > 0 else 0) * 2
else:
size[i] = size[i - 1] if i > 0 else 0
全程只存长度，不存字母，井号再多也只翻倍长度值，不翻倍数据本身。不管字符串膨胀到多少个 2 的 n 次方，一个整数数组就能装下。size[i] 就是第 i 步操作后，result 的真实长度。
有了这张表，我就能从终点开始，拿着目标坐标 k 一路往回倒推。
“第二步，反向溯源。”
我盯着 size 数组，就像看到了一条从终点延伸回起点的时光隧道。从最后一个操作开始往前推，每一步都追问同一个问题：当前位置上的字符，到底是从哪来的？
如果当前操作是 #号，说明字符串是左右对称拼接的，长度翻倍前是 m，翻倍后是 2m。k 落在左半边就不用管，落在右半边就映射回左半边的对应位置——k -= m；
如果是%号，说明发生了镜像反转，直接把 k 映射到对称位置——size[i] - 1 - k；
如果是*号，它只删了末尾，对前面的字符位置没影响，直接跳过；
如果是字母，那就看 k 是不是刚好指向当前长度的末尾——如果是，恭喜你，抓到本体了，直接返回这个字母。
# 边界检查：如果 k 越界，直接返回 '.'
if k >= size[n - 1]:
return '.'
# 反向溯源，从后往前剥开几何变换
for i in range(n - 1, -1, -1):
c = s[i]
if c.isalpha():
# k 正好指向当前末尾的字母
if k == size[i] - 1:
return c
elif c == '*':
# 退格只删末尾，不影响前面的位置
continue
elif c == '#':
# 落在右半边，映射回左半边
m = size[i] // 2
if k >= m:
k -= m
else: # '%'
# 镜像映射
k = size[i] - 1 - k
return '.'
写完提交，AC 弹出。我靠到椅背上，端起泡面准备嗦一口——面已经坨了，但这不重要——后脑勺又挨了精准的一下。时机还是那么恰到好处，刚好卡在我 AC 之后、吃面之前的那零点五秒。
“不错，没让我失望。”老勇者的声音从背后传来，带着一丝赞许，“正向打表记长度，反向溯源追位置。时间复杂度 O(n)，空间也控制在了 O(n)。看来昨天的‘空间结构’心法，你已经炼成招式了。”
”不过——”他话锋一转，点了点屏幕上那个 size 数组，“你为了存这张‘长度变化表’，可是老老实实开了一个长度为 10^5 的数组。虽然没爆内存，但不够优雅。”
我愣了一下：“不存这个，逆推的时候怎么知道每一步的长度？”
“你忘了吗？”老勇者嘴角勾起一抹狡黠的笑，“所有的操作都是可逆的。既然你能从前往后算出长度，为什么不能从后往前把长度‘还原’回去？”
去冗存真，反向还原
“反向溯源的时候，真的需要整个 size 数组吗？”
老勇者拉过椅子坐下，继续说：“你从最后一步开始往前推。最后一步的长度拿到后，你完全可以根据当前操作倒推出前一步的长度——字母就减一，星号就加一，井号就除以二，百分号不变。这样逆着推回去，每一步你都能实时算出前一步的长度。一个 sz 变量就够了，数组是冗余的。”
我愣了半秒，恍然大悟——既然反向时能自己把长度重新算出来，那正向的数组打表确实可以扔了。
“正向探路，反向还原。一个变量足矣。”老勇者靠回椅背上，表情仿佛在说“接下来的活你自己干”。
我坐直身子，立刻动手优化。先正向扫一遍拿到最终长度 sz，然后反向遍历的同时用 sz 实时逆推。井号时看 k 在左半还是右半，同时把 sz 除以二；百分号时做镜像映射，sz 不变；星号时 sz 加一；字母时 sz 减一，如果 k 正好指向末尾就直接返回。
def processStr(self, s: str, k: int) -> str:
n = len(s)
# 第一步：正向探路，最终长度sz
sz = 0
for c in s:
if c == '*':
sz = max(sz - 1, 0)
elif c == '#':
sz *= 2
elif c != '%':
sz += 1
if k >= sz:
return '.'
# 第二步：反向溯源，同时倒推还原 sz
for c in reversed(s):
if c == '*':
# 还原长度，退格是减一，往前推就加一
sz += 1
elif c == '#':
# 还原长度，除以 2
sz //= 2
if k >= sz:
k -= sz
elif c == '%':
# 长度不变，反转 k 的位置
k = sz - 1 - k
else:
# 还原长度：字母让长度加一，所以往前推就减一
sz -= 1
if k == sz:
return c
return '.'
提交，再次 AC。代码更短，内存从 O(n) 压到 O(1)，连 size 数组的影都没了。正向的账在反向时一笔一笔倒着算清楚，数组是冗余，变量才是本质。
老勇者看着屏幕上的绿色大勾，微微点头：“逆推的极致，是把正向的账也一并省掉。能现场反推的，就别提前存。记住了？”
我端起泡面，终于嗦了一大口。面已经坨成了一团红烧牛肉味的线团，但汤汁吸得饱满，每一根面条都透着“ac完题”的满足感——比任何米其林摆盘都香。
我把两版代码并排夹进魔法书里，在昨天“正序模拟过试炼，空间逆推破天机”的下边又加了几行：
正序模拟过试炼，空间逆推破天机。 若问虚空第几字，倒转乾坤寻真身。 长度可逆无需表，去冗存真见精神。
写完最后一个字，我合上魔法书，起身去给那只还在掉毛的鸽子也分了点泡面。这家伙每次送信都预谋要砸我碗里，估计村长那个老抠门，连鸽粮钱都省下来充steam余额了，
“多吃点，”我掰了半根面条放到它面前，“回去还得飞呢。上次村长偷偷买《艾尔登法环》dlc的时候，我就知道你没好日子过。” 鸽子低头啄了两口面条，抬起头冲我咕咕两声，不知道是感谢还是嫌面太坨，扑棱着翅膀飞走了，临走还不忘在我手背上留下一根灰羽当“回执”。
我捏着那根羽毛笑了笑，把它夹进魔法书的扉页里。
本作品采用
知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议
进行许可。