POJ-1016-Numbers That Count-白红宇的个人博客

POJ-1016-Numbers That Count

发布日期：2021-06-30 16:05:00 浏览次数：3 分类：技术文章

本文共 1470 字，大约阅读时间需要 4 分钟。

大致题意：

题意不难懂，对于任意的数字串n，都可以压缩存储为

c1 d1 c2 d2 … ck dk 形式的数字串

而存在一些特别的数字串，其压缩前后的样子是一模一样的

定义这种数字串为self-inventorying

当我们把n看成原串，

A为n压缩1次后的数字串，

B为n压缩2次后的数字串（即A压缩1次后的数字串）

…以此类推

K为n压缩k次后的数字串（即K-1压缩k-1次后的数字串）

则可以延伸出数字串n的3种属性：

1、 n压缩1次就马上出现self-inventorying特性，即 n n n n n n n …

2、 n压缩j次后的数字串J出现self-inventorying特性，即 n A B C…H I J J J J J J J

3、 n压缩j次后的数字串J，每再压缩K次，重新出现数字串J，即n A B… J …K J …K J…K J

其中K称为循环间隔，K>=2。

现给定一字符串，输出其属性。属性1优于属性2，属性2优于属性3。

使用C++STL可以轻松解决这个题目，所以强大的STL还是要熟练掌握的。

AC代码：

/* Source CodeProblem: 1016		User: 160930010Memory: 720K		Time: 141MSLanguage: G++		Result: AcceptedSource Code*/ #include
   
    #include
    
     #include
     
      #include
      #include
       
        #include
        
         using namespace std;char ch[100][100];int main(){ while(scanf("%s",ch[0])!=EOF&&strcmp(ch[0],"-1")!=0) { map
         
          m; string s; s=ch[0]; if(!m.count(s)) m[s]=0; int len; int x,y; x=y=0; while(true) { int a[10]; len=strlen(ch[x]); for(int i=0;i<=9;i++) { a[i]=0; char kh=i+'0'; for(int j=0;j
          
           =0;h--) ch[x][y++]=qh[h]; ch[x][y++]=(char)(i+'0'); } } ch[x][y]='\0'; s=ch[x]; if(!m.count(s)&&x<=15) m[s]=x; else if(m.count(s)&&x<=15) { if(x-m[s]==1&&m[s]!=0) { printf("%s is self-inventorying after %d steps\n",ch[0],m[s]); } else if(m[s]==0&&x==1) printf("%s is self-inventorying\n",ch[0]); else if(x-m[s]>1) printf("%s enters an inventory loop of length %d\n",ch[0],x-m[s]); break; } else if(x>15) { printf("%s can not be classified after 15 iterations\n",ch[0]); break; } } }}

转载地址：https://kaven.blog.csdn.net/article/details/76862698 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：POJ-1251-Jungle Roads

下一篇：POJ-1002-(487-3279)

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章