上海计算机学会2024年1月月赛C++丙组T4守序数
发布时间
阅读量：
阅读量
守序数
内存限制: 256 Mb时间限制: 1000 ms
题目描述
如果一个十进制正整数的任意两个相邻的数字之差均不超过 1，则称该数字为守序数。
1 是第一个守序数，给定 n 请求出第 n 个守序数。
输入格式
- 单个整数表示 n
输出格式
- 单个整数表示答案
数据范围
- 30% 的数据，1≤n≤100
- 60% 的数据，1≤n≤10000
- 100% 的数据，1≤n≤1,000,000
样例数据
输入:
13
输出:
21
解析：枚举算法，枚举从1开始的整数，判断是不是守序数，找到第n个守序数，可以解决60%的数据，详见代码：
#include<bits/stdc++.h>
using namespace std;
int n;
bool f(int x){//判断x是否为守序数
int y=0;
bool flag=0;
while (x>0){
if (flag!=0&&abs(y-x%10)>1){
return false;
}
y=x%10;
flag=1;
x/=10;
}
return true;
}
int main() {
cin>>n;
int i=0;
while (1){
i++;
if (f(i)==true){
n--;
if (n==0){
cout<<i;
return 0;
}
}
}
return 0;
}
正解：类似于宽度优先搜索；
前9个数是1,2,3,4,5,6,7,8,9,从第10个数开始由第一个数生成，在其后边加上符合有序数条件的数，即由1生成10,11,12，由2生成21,22,23。。。以此类推，可以实现用O(N）的时间复杂度完成，详见代码：
#include<bits/stdc++.h>
using namespace std;
int n;
long long a[1000005];//保存有序数
int main() {
cin>>n;
for(int i=1;i<=9;i++){//初始化前9个数
a[i]=i;
}
int p=10;//从第10个数开始递推
for(int i=1;p<=n;i++){//由第一个数开始生成后续的有序数
int x=a[i]%10;//取末位
if (x!=0){//末位等于0的不能减1
a[p]=a[i]*10+x-1;
p++;
}
a[p]=a[i]*10+x;
p++;
if (x!=9){//末位等于9的不能加1
a[p]=a[i]*10+x+1;
p++;
}
}
cout<<a[n];//输出答案
return 0;
}
利用递推式找出第i位有序数以j开头的有序数数量，然后枚举其各个数位上的数，时间复杂度O(logN）详见代码：
#include<bits/stdc++.h>
using namespace std;
int n;
int a[105][10];//a[i][j]表示i位有序数中以j开头的数字有几个
int b[105];//b[i]表示i位的有序数有几个
int w;
int main() {
cin >> n;
for(int i = 1; i <= 100; i++) {//计算i位的有序数
for(int j = 0; j < 10; j++) {//以j开头的
if (i == 1) {//第一位都是1个
a[i][j] = 1;
} else {
//从第二位开始，以j开头的有序数是
//上一位j-1，j，j+1开头的有序数的和
a[i][j] += a[i - 1][j];
if (j != 9) {//除9外，都有j+1
a[i][j] += a[i - 1][j + 1];
}
if (j != 0) {//除0外都有j-1
a[i][j] += a[i - 1][j - 1];
}
}
if (j != 0) {//第i位除0开头的总数就是i位有序数的个数
b[i] += a[i][j];
}
}
if (b[i] - 1 >= n) {//超过n后边的就可以不计算了
w = i;//计算到第w位
break;
}
}
for(int i = 1; i <= w; i++) {//枚举第n个有序数是几位数
if (n > b[i]) {
n -= b[i];
} else {
w = i;//第n个有序数为w位数
break;
}
}
int k = 1;
for(int j = 1; j <= 9; j++) {//枚举首位
if (n > a[w][j]) {
n -= a[w][j];
} else {
cout << j;
k = j;//首位为k
break;
}
}
for(int i = w - 1; i >= 1; i--) {//枚举第2位到最后一位
for(int j = max(0, k - 1); j <= min(k + 1, 9); j++) {
if (n > a[i][j]) {
n -= a[i][j];
} else {
cout << j;
k = j;//第i位为j
break;
}
}
}
return 0;
}
全部评论 (0)
还没有任何评论哟~