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

Kato_Shoko · 2025-08-11 20:23:32 · 题解

题目描述

蓝桥星的有效数字要求其各位从左到右的数字奇偶性必须交替出现。给定正整数 N，请输出序列中第 N 个满足该规则的数字。序列从 10 开始，前几项为 10,12,14,16,18,21,\dots。

思路概览

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

1. 实现函数 count(x) 统计 \leq x 的合法数的个数
2. 二分搜索最小 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）

状态转移：

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

算法流程

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

复杂度分析

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

代码实现

#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;
}