题解

· · 题解

题目大意

A 题 链接

C 题 链接

在本比赛 A 题的基础上，查找第 n 个符合要求的数。

模拟

根据题目我们可以找到一个暴力方法就是从头开始枚举，直到找到 n 个（这样肯定会超时）。

例如 977654321 这个数一定是不符合要求的，但是此时如果从个位一点点加起会稍好很多时间。所以可以看到在这个数的第二位开始就已经能判断出它不符合要求，所以我们可以用一个数组按位存储要判断的数，然后找到第一个不合法的位数，从那一位开始修改。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[15];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    int cnt=1;
    a[1]=1;
    int sum=0;
    while(sum<n){
        int flag=0;
        for(int i=1;i<cnt;i++){
            if(a[i]>=a[i+1]) {
                flag=i;
                break;
            }
        }
        if(flag) {
            a[flag]++;
            for(int i=1;i<flag;i++) a[i]=0;
            while(a[flag]>=10) {
                a[flag]-=10;
                a[++flag]++;
                cnt=max(cnt,flag);
            }
            continue;
        }
        else {
            sum++;
            if(sum==n) break;
            flag=1;
            a[1]++;
            while(a[flag]>=10) {
                a[flag]-=10;
                a[++flag]++;
                cnt=max(cnt,flag);
            }
        }
    }
    for(int i=cnt;i>=1;i--) cout<<a[i];
    return 0;
}

AC截图