加载中...

POJ 1016 - Numbers That Count


问题描述

题意不难懂,对于任意的数字串 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
}
  1. 对于整数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
    }
}
  1. 当且仅当 n 的 3 种属性都不存在时,n can not be classified after 15 iterations

测试数据

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;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
  目录