题目描述

蓝桥星的有效数字要求其各位从左到右的数字奇偶性必须交替出现。给定正整数

N

，请输出序列中第

N

个满足该规则的数字。序列从 10 开始，前几项为

10,12,14,16,18,21,\dots

。

思路概览

要找第

N

个满足"相邻位奇偶交替"的数，可将问题拆解为：

实现函数 $count(x)$ 统计 $\leq x$ 的合法数的个数
二分搜索最小 $x$ 满足 $count(x)-count(9) \geq N$ （ $count(9)$ 用于排除一位数）

统计

count(x)

使用数位 DP 实现，维护三个关键状态：

是否已开始（非前导零）
当前是否仍满足奇偶交替
上一位数字的值

状态定义与转移

定义数位 DP 状态：
dfs(pos, limt, st, ok, last)

pos：当前处理位（从低位开始索引）
limt：是否受数位限制
st：是否已开始（非前导零）
ok：当前前缀是否仍满足奇偶交替
last：上一位数字的值（未开始时为 0）

状态转移：

CPP

for (当前位 d 从 0 到上限):
    new_st = st || (d != 0)  // 遇到非零即开始
    new_ok = ok  // 初始保持当前状态
    if (st) {    // 已开始时需检查奇偶交替
        if ((last & 1) == (d & 1)) 
            new_ok = false;  // 奇偶相同则非法
    }
    递归处理下一位

算法流程

预处理：将数字分解为各位数组
记忆化搜索：
- 终止条件：位索引为负时，返回 st && ok
- 状态转移：枚举当前位，更新状态递归
- 记忆化：仅缓存无限制状态
二分查找：
- 左边界 $L=10$ ，右边界 $R=2\times 10^{18}$
- 找到最小 $x$ 满足 $[10, x]$ 区间包含至少 $N$ 个合法数

复杂度分析

时间复杂度： $800 \times 10 \times \log_2(10^{18}) \approx 5 \times 10^5$

代码实现

CPP

#include <bits/stdc++.h>
#define il inline

using namespace std;
using ll = long long;
using ull = unsigned long long;
using int128=__int128_t;

const ll N = 3e5 + 5, mod = 998244353, inf = 2e18;
const double esp=1e-3;
double PI=3.1415926;

ll a[20],dp[20][2][2][10];

il ll dfs(int pos,bool limt,bool st,bool ok,int last){
    //pos:位置,
    //limt:有没有被数位限制当前位置的最大值
    //st:当前是不是一个有效数字(有无前导零)
    //ok:题目要求的东西，是否满足
    if(pos<0){
        return st&&ok;
    }
    if(!limt&&dp[pos][st][ok][last]!=-1){
        return dp[pos][st][ok][last];
    }
    int up=limt?a[pos]:9;
    ll ans=0;
    for(int i=0;i<=up;i++){
        bool new_ok=ok,new_st=st||i;
        if(st){
            if((last&1)==(i&1)){
                new_ok=false;
            }
        }
        ans+=dfs(pos-1,limt&&(i==up),new_st,new_ok,i);
    }
    return !limt?dp[pos][st][ok][last]=ans:ans;
}

il ll query(ll n){
    int pos=0;
    while(n){
        a[pos++]=n%10;
        n/=10;
    }
    return dfs(pos-1,true,false,true,0);
}
il void solve(){
    memset(dp,-1,sizeof(dp));
    ll n;
    cin>>n;
    ll l=0,r=inf,ans=0;
    ll L=10;
    while(l<=r){
        ll mid=l+r>>1;
        //区间[L,mid]里面有多少个这种数
        if(query(mid)-query(L-1)>=n){
            ans=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    cout<<ans;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); 
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

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

文章操作

题目描述

思路概览

状态定义与转移

算法流程

复杂度分析

代码实现

相关推荐

评论

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