华师一附中OI组

标题: P1928 外星密码 [打印本页]
作者: admin    时间: 2018-5-5 18:57
标题: P1928 外星密码
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    时间: 2018-5-5 20:30
  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. }
复制代码
作者: 张笑宇    时间: 2018-5-5 20:57
  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    时间: 2018-5-5 21:12
点评下楼上zxy同学的程序，感觉太过于随意。
1、截取字符串里面的一段有现成的函数
2、数字串合并成数字也有标准的做法
3、至于那个判断位置的那段，也有隐患
这三个地方或者用函数，或者应该用扫描算法，这需要大家的编程功底
作者: 黄煦喆    时间: 2018-5-5 21:13
  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总在变，很容易糊涂的，这里有隐患
作者: 黄煦喆    时间: 2018-8-2 10:25
  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2