P1928 外星密码 递归/模拟

本文主要是介绍P1928 外星密码 递归/模拟，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目描述

有了防护伞，并不能完全避免 2012 的灾难。地球防卫小队决定去求助外星种族的帮 助。经过很长时间的努力，小队终于收到了外星生命的回信。但是外星人发过来的却是一 串密码。只有解开密码，才能知道外星人给的准确回复。解开密码的第一道工序就是解压 缩密码，外星人对于连续的若干个相同的子串“X”会压缩为“[DX]”的形式（D 是一个整 数且 1≤D≤99），比如说字符串“CBCBCBCB”就压缩为“[4CB]”或者“[2[2CB]]”，类 似于后面这种压缩之后再压缩的称为二重压缩。如果是“[2[2[2CB]]]”则是三重的。现 在我们给你外星人发送的密码，请你对其进行解压缩。

输入格式

第一行：一个字符串

输出格式

第一行：一个字符串

输入输出样例

AC[3FUN]

ACFUNFUNFUN

说明/提示

【数据范围】

对于 50%的数据：解压后的字符串长度在 1000 以内，最多只有三重压缩。

对于 100%的数据：解压后的字符串长度在 20000 以内，最多只有十重压缩。 对于 100%的数据：保证只包含数字、大写字母、’[‘和’]‘

看到这题的第一反应就是，这不是一道大模拟嘛

大概思路是先将整个字符串先读入STR[]之中，然后将其分成两部分，[]里面的部分和[]外面的部分，对于[]里面的部分用string类里的find（）函数去找[和]，然后从内层开始一层一层拆出来

一开始是用循环去做，非常非常麻烦，代码不贴了，看得人直恶心

后来想到这是一道递归题目，于是对上述思路进行优化

我们挑选一段[]中的内容来分析

核心代码：now=s.find('[',now);

now表示的是当前[的位置，上述递归的边界条件是(now<s.find(']',r)),这个r就是是第一个now

这样的递归之后我们就能找到最里面的[]，然后开始拆包

我们从头开始走一遍

我们在递归内部定义三个变量，int n     string s,str   

n表示重复次数，s表示当前[]内的最终的答案字符串（也就是拆完包之后的结果），str表示当前[]的内部第一个[]拆包出来的结果

首先读取重复次数，令ans=1,从当前[]的左端点[一路向右端点]扫描，读入一位(>='0'&&<='9')的字符就将ans乘10并加上当前数字

然后立刻(就是在读取完次数的下一行、)开始递归调用，去找下一个[]部分，并将其结果存在str当中，遇到了边界条件之后返回一个空字符

now=s.find('[',now);

str=solve(now);

边界条件：(now<STR.find(']',r))

这样一层层下来我们就会找到最里面的[]部分，读取完重复次数后继续扫描，遇到一个非]的字符就把其拼接在s后面，

s+=STR[i];

直到遇到]为止，此时我们已经获得了需要重复的字符串s，然后将其重复ans次后返回

string s1=“”；

while(ans--)s1+=s;

return s1；

此时我们回到了上一层的

str=solve(now);

顺便更新一下当前层的]的位置，保存在r中

r=STR.find(']',r);

下一层[]中拆包后的结果已经保存在str中了，我们还是继续扫描，遇到一个非[的字符就把它拼接在s后面（此时的s已经是这一层[]中的s），遇到[的时候就把str直接拼接在当前s的后面，然后找到与其对应的]，从]之后继续从STR[]中读取字符，直到遇到这一层的](也就是走到r的位置)，然后重复以上步骤，将这一层的s重复这一层的重复次数之后返回，并保存在上一层的str中，然后逐层递归回去，最后的s里面保存的就是彻底拆完包之后的字符串

到这里最复杂的[]内的拆包部分就写完了，剩下的[]之外的部分就不多说了，没难度了已经

然后我在看题解的时候发现了更好的做法，思路和我上面说的一样，但是人家是边读入边完成的工作，也就是说，省去了用find()一个个查找[]区间并且反复更新now和r这些繁琐的步骤，这里就贴别人的优秀代码了，我自己那个奇丑无比的就不拿出来献丑了

#include<bits/stdc++.h>
using namespace std;
string read()
{
    int n;
    string s="",s1;
    char c;
    while (cin>>c)//一直读入字符，直到Ctrl+z
    {
        if (c=='[')
        {
            cin>>n;//读入D
            s1=read();//读入X
            while (n--) s+=s1;//重复D次X
            //注：上面不能写成while (n--) s+=read();
        }
        else 
        {
            if (c==']') return s;//返回X
            else s+=c;//如果不是'['和']'，那就是X的一个字符，所以加进X
        }
    }
}
int main()//巨短主函数
{
    cout<<read(); 
    return 0;
}
此代码来自a1_1

这篇关于P1928 外星密码 递归/模拟的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！