POJ-1016-Numbers That Count

​​题目传送门​​​ 大致题意:
题意不难懂,对于任意的数字串n,都可以压缩存储为
c1 d1 c2 d2 … ck dk 形式数字
而存在一些特别的数字串,其压缩前后的样子是一模一样的
定义这种数字串为self-i++nventoryi++ng

当我们把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 Code
Problem: 1016 User: 160930010
Memory: 720K Time: 141MS
Language: G++ Result: Accepted
Source Code
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<cstdio>
#include<cmath>
using namespace std;
char ch[100][100];
int main()
{
while(scanf("%s",ch[0])!=EOF&&strcmp(ch[0],"-1")!=0)
{
map<string,int>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<len;j++)
{
if(ch[x][j]==kh)
a[i]++;
}
}
y=0;
x++;
for(int i=0;i<=9;i++)
{
if(a[i]!=0)
{
char qh[10];
int q=a[i];
int j=0;
while(q)
{
qh[j++]=(char)(q%10+'0');
q/=10;
}
for(int h=j-1;h>=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;
}
}
}
}