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

· · 题解

第十六届蓝桥杯CB国赛 F-蓝桥星数字

当 n 很小时没啥说的，直接模拟即可，但需要注意的是，经笔者在赛场上的测试，本题 20\% 的分数纯靠模拟疑似是拿不到满分的，也就是说 n=10^5 这个量级的时候，一两秒钟已经跑不出来答案了，因此本题直接模拟的分数应该是小于 20\% 的，具体拿多少和数据有关。

（我猜可能甚至 0 分，因为我猜蓝桥杯的出题人为了偷懒，这一段部分分显然没有认真思考确定应该给到多大的范围，因此造数据的时候他大概率只是在 [1,10^5] 这个区间内随机了几组数据，而直接随机的话大概率是更偏向 10^5 的，也就是大概率一秒钟跑不出来的）。

（蓝桥杯并不是第一次干这种事情了）

模拟代码：
bool good(int x) {
    string s = to_string(x);
    bool f = (s[0] - '0') & 1;
    for(int i = 1; i < s.size(); i++) {
        int u = (s[i] - '0') & 1;
        if(f ^ u) {
            f ^= 1;
        } else {
            return 0;
        }
    }
    return 1;
}
int ans = 0;
for(int i = 10; ; i++) {
    if(good(i)) {
        ans++;
    }
    if(ans == x) {
        ans = i;
        break;
    }
}
cout << ans << endl;
正解（前置知识：数位 dp。）

本题应该是有很智慧的递推做法的，但笔者在赛场上没想到，于是想到了一个无脑但稳对的做法。

像这种：求第 k 个合法的数字，然后 "合法" 的定义和数字的数位有一定关系的题，我们都可以去考虑：

二分答案+数位 dp 的做法。

我们二分答案，假设题目求的第 n 大 "蓝桥星数字" 是 k（也就是答案），那么我们的问题就转化成了，求 [1,k] 有多少个正整数是 "蓝桥星数字"，只要这个个数不小于 n，就说明答案可能可以缩小 (\rm r=mid)，否则答案肯定更大 (\rm l=mid+1)。

而数位 dp 我们需要记录什么信息，首先因为要考虑每一位是否奇偶交替，因此我们必须记录上一位填的数的奇偶性，同时注意到 "蓝桥星数字" 至少是两位数，因此我们还得记录一个当前数字的数位个数，但这里我们只需要把数位个数和 2 取一个 \min 即可。

因此我们的 dp 可以设计成：dp_{i,lst,cnt} 表示当前填到第 i 位，上一位填的奇偶性是 lst，目前填了 cnt 个数位的总数字个数。（cnt 要和 2 取 \min，因为只要 cnt \geq 2 就是合法的。）

最后需要注意的是，二分的下界要设为 10，而上界最好直接设置为 4\times 10^{18}，dp 也稍微开大点。

笔者赛时的代码：
int x;
string s;
int dp[22][2][3];

int dfs(int u, int lst, int cnt, bool limit, bool lead0) {
    if(u == s.size()) {
        if(!lead0 && cnt > 1) {
            return 1;
        }
        return 0;
    }
    if(!lead0 && !limit && dp[u][lst][cnt] != -1) {
        return dp[u][lst][cnt];
    }

    int ans = 0;
    int up = (limit ? s[u] - '0' : 9);
    for(int i = 0; i <= up; i++) {
        int now = i & 1;
        if(lst == -1 || (now ^ lst)) {
            if(lead0 && (i == 0)) {
                ans += dfs(u + 1, -1, cnt, limit & (i == up), 1);
            } else {
                ans += dfs(u + 1, now, min(2LL, cnt + 1), limit & (i == up), lead0 & (i == 0));
            }
        }
    }

    return dp[u][lst][cnt] = ans;
}

bool check(int r) {
    s = to_string(r);
    memset(dp, -1, sizeof dp);
    return dfs(0, -1, 0, 1, 1) >= x;
}

void solve() {
    cin >> x;
    int l = 10, r = 4e18; // r 可以调整为 10^18，赛时的笔者稳妥起见直接取到能取的最大值了
    while(l < r) {
        int mid = (l + r) / 2;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << l << endl;
}

时间复杂度：O(\log(X) \times \log(X) \times 10 \times 2 \times 3)。（其中 X=10^{18}，第一个 \log 来源于二分答案，第二个来源于数位 dp 的第一维状态，10 来源于数位 dp 转移时枚举填的数字有 10 个，2 和 3 是数位 dp 的 lst 和 cnt 的值域。）