题目描述
A positive integer XX is said to be a lunlun number if and only if the following condition is satisfied:
- In the base ten representation of XX (without leading zeros), for every pair of two adjacent digits, the absolute difference of those digits is at most 11 .
For example, 12341234 , 11 , and 334334 are lunlun numbers, while none of 3141531415 , 119119 , or 1357913579 is.
You are given a positive integer KK . Find the KK -th smallest lunlun number.
输入格式
Input is given from Standard Input in the following format:
K
输出格式
Print the answer.
题意翻译
当下列条件满足时,一个整数XXX被称为Lunlun number
:
- 在XX的十进制表示中,每相邻的两位的差为0或1。
举些例子来说,12341234,111111,334334都是
Lunlun number
,而3141531415,119119,1357913579都不是。
给定一个整数K(1 <= K <=10^5),输出第KK小的Lunlun number
。
思路:
这个问题可以用队列来解决。
只需要一些模拟加上队列的知识就好了文章来源:https://www.toymoban.com/news/detail-457461.html
AC CODE:文章来源地址https://www.toymoban.com/news/detail-457461.html
#include<bits/stdc++.h>
using namespace std;
long long k,x;
queue<long long> q;
void init(){
q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);q.push(6);q.push(7);q.push(8);q.push(9);//初始化,本蒟蒻写的有亿点长
//一定要按顺序写!(亲身经历)
}
/*
其实也可以这么写:
void init2(){
for(int i=1;i<=9;i++){
q.push(i);
}
}
*/
//define 定义
int main(){
//freopen(,"r",stdin);//备用的freopen
//freopen(,"w",stdout);//备用的freopen
cin>>k;
init();
while(!q.empty()){//判断非空
x=q.front();
q.pop();//pop!注意要加括号!!!本蒟蒻就写错了一次(小声)
k--;//判断条件之一,递减
if(k==0){
cout<<x;//完事就输出
break;
}
for(long long j=(x%10)-1;j<=(x%10)+1;j++){//从x mod 10-1 ~ x mod 10+1 循环 ,因为x会改变,所以并不是只有2次
if(j<0 or j>9)continue;
q.push(x*10+j);//进队
}
}
return 0;
}
到了这里,关于洛谷AT4888 题解-伦伦数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!