题解 P1928 【外星密码】

· · 题解

\color{green}{\text{洛谷P1928\ \ \ \ \ 外星密码}}

**【数据范围】：** - 对于 $50\%$ 的数据：解压后的字符串长度在 $1000$ 以内，最多只有三重压缩。 - 对于 $100\%$ 的数据：解压后的字符串长度在 $20000$ 以内，最多只有十重压缩。保证只包含数字、大写字母、`[` 和 `]`。 --------------------------------------- $\color{blue}{\text{【思路】：}}$ 因为最多只有 $10$ 重的压缩，所以我们可以从此入口。记 $S_i$ 表示第 $i$ 重的压缩展开后的结果，我们可以如此计算它（$dep$ 表示当前是第 $dep$ 重的压缩）： - 如果当前字符是一个字母的话，直接把它放至 $S_{dep}$ 的最后一位。 - 如果当前字符是 `[`，代表我们可以了新的一层压缩，我们可以先取出 $D$，然后把 $S_{dep+1}$ 求出。第 $dep+1$ 层压缩对 $S_{dep}$ 的贡献就是 $num$ 个 $S_{dep+1}$，直接把 $num$ 个 $S_{dep+1}$ 放入 $S_{dep}$ 的后面即可。 考虑到递归的层数很小（只有 $10$），所以我们可以用**递归**解决问题。 -------------------------------- $\color{blue}{\text{【代码】：}}

如果洛谷的 LaTeX 公式显示不出来，大家可以参考我的同期博客。

博客地址：https://blog.csdn.net/ZHUYINGYE_123456/article/details/104877546