题解：P12835 [蓝桥杯 2025 国 B] 蓝桥星数字

cccz · 2025-07-06 19:33:12 · 题解

注意到 N 的范围是很大的，直接模拟显然会超时，又注意到是统计某些特定的数，很容易想到数位 dp。

通过题意很容易就可以找出规律，即除第一个可以填 9 种数字之外，剩余位数都只能填 5 种，可以先把所有位数的情况打个表，再 dfs 判断。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dis[105],ck[105];
ll n,ans;
void dfs(int pos,int last){
    if(pos==0){
        printf("%lld",ans);
        exit(0);//直接结束程序  
        return ;
    }
    int to,i;
    if(last==-1)to=1,i=1;//判断是否为最高位数 
    else{
        to=2;
        if(last%2==0)i=1;
        else i=0;
    }
    for(;i<10;i+=to){
        if(n>ck[pos]){ 
            n-=ck[pos];
            continue;
        }
        ans=ans*10+i;
        dfs(pos-1,i);
    }
}
signed main(){
    dis[1]=9,ck[1]=1;
    for(int i=2;i<=100;i++)dis[i]=dis[i-1]*5,ck[i]=ck[i-1]*5;//打表 
    scanf("%lld",&n);
    int pos=0;
    for(int i=2;i<=100;i++){
        if(n>dis[i])n-=dis[i];
        else{
            pos=i;//找到第N位数的位数 
            break;
        }
    }
    dfs(pos,-1);
    return 0;
}