【POJ1016】-数字串压缩

2016-10-15 本文已影响0人其中一个cc

问题描述：

inventorying number：可以看做是对字符串的一种转换。对于一个数字串N，串中的每个数字均为0~9的整数，计算出0、1、2……9每个数字出线的次数，对于次数大于等于1的数字di，按照出线次数ci的升序记录，格式为c1d1c2d2……ckdk。其中，0<=d1<d2<d3<d4<……<dk<<=9.：

例如：数字串5553141的inventorying number是21131435（两个1，一个3，一个4，三个5）

（1）self-inventorying number，满足以下性质：字符串N的inventory number等于数字串N。如：22的inventorying number是22（两个2）

（2）self-inventorying after j steps，满足：字符串N1在经过j次inventory转换之后，之后的数字串满足self-inventorying number性质。即N1->N2->……->Nj->Nj->Nj->Nj->Nj->Nj->……

（3）enters an inventory loop of length k，满足：对N1每经过j次转换，得到的数字串N j+k总是等于Nj，其中j>=0

（4）can not be classified after 15 iterations：在经过15次转换后，不满足上述三种情况的数字串。

题目要求是给定几组数字串，要求输出这几组数字串属于上述四种情况的某一种。每组数字串的长度不大于80.

解题思路：

可以把每组字符串存储到vector<vector<int>>中，这样做可以方便数字串的比较。每个数字串存储在vector<int>中。

转换函数Inv（vector<int>）：这里分别对0~9出线的次数进行统计，并且记录到转换后的数字串invsc中，需要注意的是由于每个数字串最多有80位，那么可能会有80个X（X为0~9的某个数字）的情况，需要存储两位数字到转换后的数字串中，在这里加入了invc的判断。