P1928 外星密码

admin

https://www.luogu.org/problemnew/show/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%的数据：保证只包含数字、大写字母、’[‘和’]‘

admin

1. #include <iostream>
   
2. using namespace std;
   
3. string ms(string s)
   
4. {
   
5.     ///自左向右找第一个] 他的左边第一个就是对应的[  要是没有找到] 说明无法分解
   
6.     int i,j,k,l,x;
   
7.     string t,tt;
   
8.     i=s.find(']');
   
9.     l=s.size();
   
10.     if (i==-1) return s;
    
11.     else
    
12.     {
    
13.         j=i;
    
14.         while (s[j]!='[' && j>=0)  j--;
    
15.         if (j<0) return "ERROR!!!" ;///按照题意，这个应该不可能
    
16.         k=j+1;
    
17.         x=0;
    
18.         while (s[k]>='0' && s[k]<='9')
    
19.         {
    
20.             x=10*x+s[k]-'0';    ///数字合成
    
21.             k++;
    
22.         }
    
23.         tt=t="";
    
24.         for (int kk=k; kk<=i-1; kk++) t=t+s[kk];  ///生成单串
    
25.         for (int kk=1; kk<=x; kk++) tt=tt+t;  ///生成重复
    
26.         tt=s.substr(0,j)+tt+s.substr(i+1,l-i-1) ///合成展开串
    
27.         return ms(tt);///递归
    
28.     }
    
29. }
    
30. int main()
    
31. {
    
32.     string s;cin>>s;
    
33.     cout<<ms(s);
    
34.     return 0;
    
35. }
    

复制代码

张笑宇

1. #include<iostream>
   
2. using namespace std;
   
3. string s;
   
4. int l,sum,i,j,p[100];///sum个正括号,分别在p[i]
   
5. int num(int x)
   
6. {
   
7.     int nn;
   
8.     if (s[x+2]>='0' && s[x+2]<='9')
   
9.         nn=(s[x+1]-'0')*10+(s[x+2]-'0');
   
10.     else
    
11.         nn=(s[x+1]-'0');
    
12.     return nn;
    
13. }
    
14. string be(int x)
    
15. {
    
16.     string bes="";
    
17.     for (j=0;j<=x-1;j++) bes=bes+s[j];
    
18.     return bes;
    
19. }
    
20. string he(int l,int r,int c)///左端点 右端点 重复次数
    
21. {
    
22.     string her="",sher;///sher记录her
    
23.     if (c<=9) l=l+2;
    
24.     else l=l+3;
    
25.     r--;
    
26.     for (j=l;j<=r;j++) her=her+s[j];
    
27.     sher=her;
    
28.     for (j=1;j<=c-1;j++) her=her+sher;
    
29.     return her;
    
30. }
    
31. string af(int l,int r)
    
32. {
    
33.     string aft="";
    
34.     for (j=l+1;j<=r;j++) aft=aft+s[j];
    
35.     return aft;
    
36. }
    
37. int main()
    
38. {
    
39.     cin>>s;
    
40.     l=s.size(),sum=0;///sum括号的个数
    
41.     for (i=0;i<=l-1;i++)
    
42.     {
    
43.         if (s[i]=='[') sum++,p[sum]=i;
    
44.     }
    
45.     for (i=sum;i>=1;i--)///从内向外扫
    
46.     {
    
47.         l=s.size();
    
48.         int number=num(p[i]);///重复次数
    
49.         string before=be(p[i]);///把该括号之前的串复制下来
    
50.         int pp=p[i];
    
51.         while (s[pp]!=']') pp++;///反括号在s[pp]
    
52.         string here=he(p[i],pp,number);///在[]中的字符串
    
53.         string after=af(pp,l);///在反括号之后的串
    
54.         s=before+here+after;
    
55.     }
    
56.     cout<<s;
    
57.     return 0;
    
58. }

复制代码

admin

点评下楼上zxy同学的程序，感觉太过于随意。
1、截取字符串里面的一段有现成的函数
2、数字串合并成数字也有标准的做法
3、至于那个判断位置的那段，也有隐患
这三个地方或者用函数，或者应该用扫描算法，这需要大家的编程功底

黄煦喆

1. #include<iostream>
   
2. using namespace std;
   
3. string s,ss,t;
   
4. int l,r,a;
   
5. string ms(string s)
   
6. {
   
7.     r=s.find(']');
   
8.     if(r==-1)return s;
   
9.     r--;
   
10.     l=r;
    
11.     while(s[l]!='[')l--;
    
12.     l++;
    
13.     a=s[l]-'0';
    
14.     l++;
    
15.     if(s[l]>='0'&&s[l]<='9'){a=a*10+(s[l]-'0');l++;}
    
16.     for(int j=l;j<=r;j++)t+=s[j];
    
17.     for(int m=1;m<=a;m++)ss+=t;
    
18.     ss=s.substr(0,l-2)+ss+s.substr(r+2,s.size()-r-1);
    
19.     return ms(ss);
    
20. }
    
21. int main()
    
22. {
    
23.     cin>>s;
    
24.     cout<<ms(s);
    
25.     return 0;
    
26. }
    

复制代码

这个同学t ss没有赋初值，肯定有问题！！！而且，变量最好专用，多设几个无所谓的，你看他的l  r总在变，很容易糊涂的，这里有隐患

黄煦喆

1. #include<iostream>
   
2. using namespace std;
   
3. string ts,ss,t;
   
4. int l,r,a;
   
5. string ms(string s)
   
6. {
   
7.     a=0;
   
8.     t=ss="";
   
9.     r=s.find(']');
   
10.     if(r==-1)return s;
    
11.     int p=r;
    
12.     l=r;
    
13.     while(s[l]!='['&&l>=0)l--;
    
14.     int q=l+1;
    
15.     while(s[q]<='9'&&s[q]>='0')
    
16.     {
    
17.         a=10*a+(s[q]-'0');
    
18.         q++;
    
19.     }
    
20.     for(int j=q; j<p; j++)t+=s[j];
    
21.     for(int m=1; m<=a; m++)ss+=t;
    
22.     ss=s.substr(0,l)+ss+s.substr(r+1);
    
23.     return ms(ss);
    
24. }
    
25. int main()
    
26. {
    
27.     cin>>ts;
    
28.     cout<<ms(ts);
    
29.     return 0;
    
30. }
    

复制代码