- 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 的压缩数字串：
- 当
R(n)==R(R(n))时，则 n is self-inventorying - 对于整数 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
}- 对于整数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
}
}- 当且仅当 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;
}
