POJ 1016 - Numbers That Count

算法

原创

发布日期: 2011-12-16

更新日期: 2024-11-17

文章字数: 1k

阅读时长: 5 分

阅读次数:

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