PAT乙级:1084 外观数列 (20分)

题干

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

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

思路

双指针法。思路写在注释中。

code

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
vector<int> vec;
int d=0,steps=0;
cin>>d>>steps;
vec.push_back(d);
for(int i=0;i<steps-1;i++){
int p=0,q=0;//双指针
vector<int> temp;//临时存储
vec.push_back(0);//哨兵,可以节省特判步骤
while(p<vec.size()){
if(vec[p]!=vec[q]){//p和q指向的数据不相同,说明已经到临界点了
temp.push_back(vec[q]);//将数据放进数组
temp.push_back(p-q);//将个数放进数组
q=p;//更新q指针的位置
}
p++;//p指针一直往前走
}
vec=temp;
}
for(int values:vec) cout<<values;
return 0;
}

最新文章

  1. php上传图片文件常用的几个方法
  2. DateTime还是DateTimeOffset?Now还是UtcNow?
  3. android夜间模式实现
  4. linux设备树笔记__dts基本概念及语法【转】
  5. loadrunner使用system()函数调用Tesseract-OCR识别验证码遇到的问题
  6. HUST 1601 Shepherd
  7. java.lang.String 类源码解读
  8. 音乐API
  9. UVA12265-Selling Land(细节处理)
  10. (6).NET CORE微服务 Micro-Service ---- AOP框架
  11. 281A
  12. [转载]web安全之token
  13. javascript 对象克隆
  14. error_reporting 报错
  15. 华为console口配置
  16. Python 读取写入配置文件 ConfigParser
  17. C#获取mp3文件时长、解决发布到服务器无法使用问题
  18. BZOJ P2157 旅游
  19. [APIO / CTSC2007]数据备份 --- 贪心
  20. HDU4513:吉哥系列故事——完美队形II(Manacher)

热门文章

  1. 5G和AI机器人平台为工业4.0和无人机提供服务
  2. httprunner 2.5.7 下.env 文件环境变量的使用及debugtalk的使用,对test的参数化及执行
  3. 我的N年软件测试感悟
  4. 性能工具之Jmeter-Dubbo脚本开发
  5. 整合Spring Cloud Stream Binder与GCP Pubsub进行消息发送与接收
  6. javascript之强制类型转换
  7. DL基础补全计划(一)---线性回归及示例(Pytorch,平方损失)
  8. 易车网实战+【保姆级】:Feapder爬虫框架入门教程
  9. 14、redis安装及数据类型
  10. 9.4、安装zabbix(1)