PAT乙级:1084 外观数列 (20分)
2024-09-08 05:10:37
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;
}
最新文章
- php上传图片文件常用的几个方法
- DateTime还是DateTimeOffset?Now还是UtcNow?
- android夜间模式实现
- linux设备树笔记__dts基本概念及语法【转】
- loadrunner使用system()函数调用Tesseract-OCR识别验证码遇到的问题
- HUST 1601 Shepherd
- java.lang.String 类源码解读
- 音乐API
- UVA12265-Selling Land(细节处理)
- (6).NET CORE微服务 Micro-Service ---- AOP框架
- 281A
- [转载]web安全之token
- javascript 对象克隆
- error_reporting 报错
- 华为console口配置
- Python 读取写入配置文件 ConfigParser
- C#获取mp3文件时长、解决发布到服务器无法使用问题
- BZOJ P2157 旅游
- [APIO / CTSC2007]数据备份 --- 贪心
- HDU4513:吉哥系列故事——完美队形II(Manacher)
热门文章
- 5G和AI机器人平台为工业4.0和无人机提供服务
- httprunner 2.5.7 下.env 文件环境变量的使用及debugtalk的使用,对test的参数化及执行
- 我的N年软件测试感悟
- 性能工具之Jmeter-Dubbo脚本开发
- 整合Spring Cloud Stream Binder与GCP Pubsub进行消息发送与接收
- javascript之强制类型转换
- DL基础补全计划(一)---线性回归及示例(Pytorch,平方损失)
- 易车网实战+【保姆级】:Feapder爬虫框架入门教程
- 14、redis安装及数据类型
- 9.4、安装zabbix(1)