Java教程

P1928 外星密码 递归/模拟

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

题目描述

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

输入格式

第一行:一个字符串

输出格式

第一行:一个字符串

输入输出样例

输入 #1
AC[3FUN]
输出 #1
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 外星密码 递归/模拟的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!