- POJ 1016 - Numbers That Count
- Time: 1000MS
- Memory: 10000K
- 难度: 初级
- 分类: 串
问题描述
题意不难懂，对于任意的数字串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种属性：
- n压缩1次就马上出现self-inventorying特性，即 n n n n n n n …..
- n压缩j次后的数字串J出现self-inventorying特性，即 n A B C….H I J J J J J J J
- n压缩j次后的数字串J，每再压缩K次，重新出现数字串J，即n A B… J ..K J ..K J..K J
其中K称为循环间隔，K>=2
现给定一字符串，输出其属性。
属性1优于属性2，属性2优于属性3
解题思路
字符串处理，纯粹的模拟题
压缩n时要注意，ck可能是1位，也可能是2位，需要判断。
设R(n)为描述整数n的压缩数字串
1、 当R(n)==R(R(n))时，则n is self-inventorying
2、 对于整数n：
令N = n
for j=1 to 15
{
令tj =R(N)
若R(tj)== R(R(tj)) ，则n is self-inventorying after j steps 且 break
否则 N=tj
}3、 对于整数n：
令N = n，记录num[0]= n
for j=1 to 15
{
令tj =R(N)，记录num[j]=tj
for i=0 to j-2 (保证k>=2)
{
若tj== num[i] ，则n enters an inventory loop of length k ( k=j-i )
break
}
}4、 当且仅当n的3种属性都不存在时，n can not be classified after 15 iterations
测试数据
- 来源（已失效）：East Central North America 1998
- 输入：input
- 输出：output
AC 源码
//Memory Time
//232K 32MS
#include<iostream>
#include<string>
using namespace std;
/*压缩数字串n，存放到t*/
void R(char* n,char* t)
{
int i,j;
int time[10]={0}; //记录n中各个数字出现的次数
for(i=0;n[i];i++)
time[ n[i]-'0' ]++;
for(i=0,j=0;i<10;i++)
{
if(time[i])
{
if(time[i]<10) //数字i出现次数<10，即占1位
{
t[j++]=time[i]+'0';
t[j++]=i+'0';
}
else //数字i出现次数>=10，即占2位
{
t[j++]=time[i]/10+'0';
t[j++]=time[i]%10+'0';
t[j++]=i+'0';
}
}
}
t[j]='\0';
return;
}
int main(int i,int j)
{
char n[16][85]; //n[0]为原串，n[1~15]分别为n连续压缩15次的数字串
while(cin>>n[0] && n[0][0]!='-')
{
bool flag1=false; //属性1，n is self-inventorying
int flag2=0; //属性2，n is self-inventorying after j steps，顺便记录j
int flag3=0; //属性3，n is enters an inventory loop of length k，顺便记录k
for(i=1;i<=15;i++)
R(n[i-1],n[i]);
if(!strcmp(n[0],n[1])) //属性1，n压缩1次就是其本身
flag1=true;
if(!flag1)
{
for(j=1;j<15;j++)
if(!strcmp(n[j],n[j+1])) //属性2, n压缩j次后的数字串n[j]具有属性1
{
flag2=j;
break;
}
if(!flag2)
{
for(j=1;j<=15;j++) //属性3，两两枚举各次压缩的数字串，注意循环间隔>=2
{
for(i=0;i<=j-2;i++)
{
if(!strcmp(n[j],n[i]))
{
flag3=j-i;
break;
}
}
if(flag3)
break;
}
}
}
if(flag1)
cout<<n[0]<<" is self-inventorying"<<endl;
else if(flag2)
cout<<n[0]<<" is self-inventorying after "<<flag2<<" steps"<<endl;
else if(flag3)
cout<<n[0]<<" enters an inventory loop of length "<<flag3<<endl;
else
cout<<n[0]<<" can not be classified after 15 iterations"<<endl;
}
return 0;
}
