采购推荐

大炮打蚊子
套模板

下标默认从0开始
mask 第u位 不符合数字要求 为end由高到低第u位，符合为数位值
end 为数位奇偶最终态，由低到高 奇数位为0，偶数位为1

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

int a, b;
int cache[10][1 << 10];

int f(int x) {
    string s = to_string(x);
    memset(cache, -1, sizeof cache);

    int end = 0;
    for (int i = 1 - s.size() % 2, k = 1; i < s.size(); i++, k++) {
        end <<= 1;
        end |= k % 2;
    }

    function<int(int, int, bool, bool)> dfs = [&](int u, int mask, bool limit, bool num) {
        if (u == s.size()) {
            if (!num) return 0;
            return end == mask ? 1 : 0;
        }
        if (!limit && num && cache[u][mask] != -1) return cache[u][mask];
        int res = 0;
        int up = limit ? s[u] - '0' : 9;
        for (int i = 0; i <= up; i++) {
            int reali = s.size() - u - 1;
            int pmask;
            if (num || i) {
                pmask = mask | ((i % 2) << reali);
            } else {
                pmask = mask | (((reali + 1) % 2) << reali);
            }
            res += dfs(u + 1, pmask, limit && i == up, num || i);
        }
        if (!limit && num) cache[u][mask] = res;
        return res;
    };
    return dfs(0, 0, true, false);
}

int main() {
    cin >> a;
    cout << f(a) << "\n";
    return 0;
}