AT_arc153_a AABCDDEFE 题解

chlchl · 2023-01-31 10:10:03 · 题解

做法与所有题解不一致，望通过。

作为签到题，肯定没什么思维难度。

Solution

如果枚举所有九位数，时间复杂度会非常紧（虽然有卡常过的）。

但换个角度想，第 n 小的数，其实可以转化为统计数量的问题。

由此，赛时想到二分，然后对 mid 跑数位 DP，看看 [10^8,mid] 中有没有这么多美丽的正整数。

至于数位 DP 怎么写，看看题目限制：

综上，记录前导 0、前两位数字是多少、万年不变的当前位数和是否达到最高位 op 即可完成本题。

#include<bits/stdc++.h>
using namespace std;

const int N = 10 + 5;
int n, dgt[N], f[N][2][N][N];

int dp(int len, int op, int lst1, int lst2){//一个比较简单的数位 DP
    if(!len)
        return 1;
    if(~f[len][op][lst1][lst2])
        return f[len][op][lst1][lst2];
    int k = (op ? dgt[len] : 9);
    int cnt = 0;
    for(int d=0;d<=k;d++){
        if(len == 9 && d == 0)
            continue;
        if(len == 8 && d != lst1)
            continue;
        if(len == 4 && d != lst1)
            continue;
        if(len == 1 && d != lst2)
            continue;
        cnt += dp(len - 1, op & (d == k), d, lst1);
    }
    return f[len][op][lst1][lst2] = cnt;
}

int solve(int x){
    memset(f, -1, sizeof(f));
    int len = 0;
    do
        dgt[++len] = x % 10;//第 9 位开始枚举（最高位） 
    while(x /= 10);
    return dp(len, 1, 10, 10);
}

bool check(int x){
    return solve(x) >= n;
}

int main(){
    scanf("%d", &n);
    int l = 100000000, r = 999999999;//二分边界记得设
    while(l <= r){
        int mid = (l + r) >> 1;
        if(check(mid))
            r = mid - 1;
        else
            l = mid + 1;
    }
    printf("%d\n", l);
    return 0;
}

这个做法的优越性在于：

• 思维难度低，不需要观察任何性质。
• 工程量小，比打表省事多了。
• 效率高，不开 O2 跑进最优解第一页。

So，数位 DP 香不香 qwq？