1084. 外观数列 (20)

时间限制

400 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

CHEN, Yue

外观数列是指具有以下特点的整数序列：

d, d1, d111, d113, d11231, d112213111, ...

它从不等于 1 的数字 d 开始，序列的第 n+1 项是对第 n 项的描述。比如第 2 项表示第 1 项有 1 个 d，所以就是 d1；第 2 项是 1 个 d（对应 d1）和 1 个 1（对应 11），所以第 3 项就是 d111。又比如第 4 项是 d113，其描述就是 1 个 d，2 个 1，1 个 3，所以下一项就是 d11231。当然这个定义对 d = 1 也成立。本题要求你推算任意给定数字 d 的外观数列的第 N 项。

输入格式：

输入第一行给出[0,9]范围内的一个整数 d、以及一个正整数 N（<=40），用空格分隔。

输出格式：

在一行中给出数字 d 的外观数列的第 N 项。

输入样例：

1 8

输出样例：

1123123111

解析：这题有俩个地方很关键，一是整数d属于[0,9]，第二个地方就是N<40.这代表着我们并不需要多么复杂的算法优化空间与时间，简单的暴力求解就可以解决。这题和字符串压缩解压类似，从头开始遍历，遇到相同字符时cnt+1，否则就保存已经连续几个相同字符。要注意最后要判断cnt是否大于0，防止字符串从头到尾都相等。

代码如下：

#include
    
     using namespace std;int main(){	string a;	int n;	cin >> a >> n;	while(--n){		string ans;		char c = a[0];		int cnt = 0;		for(int i = 0;i < a.length();i++){			if(a[i] == c)	cnt++;			else{				ans+=c;				ans+=cnt+'0';				c = a[i];				cnt = 1;			}		}		if(cnt > 0){			ans+=c;			ans+=cnt+'0';		}		a = ans;	}	cout << a <