题解 | 小苯的数位MEX

一道经典的数位 MEX 问题，结合了状态压缩与数位 DP的思想。

题目核心分析

1. 操作限制：给定 和 ，你可以将 变为 范围内的任意整数。
2. 目标：寻找该范围内最大的 MEX 值，并统计有多少个数字达到了这个最大 MEX。

解题思路

1. 贪心与枚举

由于 MEX 的最大可能值只有 （即数字中包含了 所有的数），这个范围非常小。因此，我们可以从大到小枚举 MEX 的值（从 到 ）。

• 一旦我们在区间 中找到了至少一个数满足当前枚举的 MEX，那么这个值就是我们要找的最大 MEX。
• 此时，在该区间内满足该 MEX 的数字个数即为所求答案。

2. 数位 DP 状态设计

为了统计区间 内满足特定 MEX 条件的数字个数，我们使用数位 DP，利用前缀和思想：。

• 状态表示：dp[pos][mask][is_leading_zero]
• pos: 当前处理到的数位（从高到低）。
• mask: 当前已出现的数字集合（状态压缩，共 种状态）。
• is_leading_zero: 前导零标记。由于 的处理比较特殊（前导零不计入 MEX 计算），需要单独标记。
• 转移逻辑：
• 如果 is_leading_zero 为真且当前位选 ，则 mask 不更新。
• 否则，将当前位数字 加入 mask：mask | (1 << i)。
• 终点判断：当 pos < 1 时，计算 mask 的 MEX。如果等于目标 Mex，则返回 ，否则返回 。

3. 效率优化

• 时间戳优化：由于我们要多次执行不同 MEX 的查询，使用 tim[pos][mask][lea] 记录当前状态属于哪一次查询（idx），避免重复初始化数组带来的 开销。

代码逻辑实现

mex(s) 函数通过位运算快速查找第一个未出现的位：

int mex(ll s) {
    int num = 0;
    for(int i = 0; i < 10; i++) {
        if(s >> i & 1) ++num;
        else return num;
    }
    return num;
}

使用__builtin_ctz优化版本：

int mex(ll s){
    return __builtin_ctz(~s);
}

在 solve 函数中，倒序枚举 Mex 并调用 calc：保证第一个找到的mex是最大合法的

for(Mex = 10; Mex >= 0; Mex--) {
    int cnt = calc(n + k) - calc(n - 1);
    if(cnt > 0) {
        cout << Mex << ' ' << cnt << endl;
        return;
    }
}

复杂度分析

• 状态数： 种状态。
• 单次查询：每个状态转移 次数字。

总结与技巧

• 前导零的处理：这是本题的坑点。如果一个数是 ，它的数位集合是 ，不包含 ，所以 MEX 是 。在 DP 时，只有非前导零的 才能被计入 mask。
• 从最大Mex开始贪心枚举：最大可达成的 MEX 显然是最优情况，通过数位 dp 计数判断其个数是否为 0 判断是否合法。

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=11;
int dig[N];
ll dp[N][1<<N][2];
int tim[N][1<<N][2];
int Mex;
int idx;//记录时间戳信息
int mex(ll s){
    return __builtin_ctz(~s);
}
ll dfs(int pos,ll s,bool lea,bool up){
    if(pos<1) {
        if(lea) return Mex==1;
        return Mex==mex(s);
    }
    if(!up&&tim[pos][s][lea]==idx) return dp[pos][s][lea];
    int mx=(up?dig[pos]:9);
    ll res=0;
    for(int i=0;i<=mx;i++){
        if(lea&&i==0) res+=dfs(pos-1,0,true,up&(i==mx));
        else res+=dfs(pos-1,s|(1<<i),false,up&(i==mx));
    }
    if(!up){
        tim[pos][s][lea]=idx;
        dp[pos][s][lea]=res;
    }
    return res;
}
int calc(int x){
    ++idx;//更新时间戳
    if(x<0) return 0;
    int len=0;
    while(x>0){
        dig[++len]=x%10;
        x/=10;
    }
    return dfs(len,0LL,true,true);
}
void solve(){
    int n,k;
    cin>>n>>k;
    int len1=0,len2=0;
    for(Mex=10;Mex>=0;Mex--){
        int cnt=calc(n+k)-calc(n-1);
        if(cnt>0){
            cout<<Mex<<' '<<cnt<<endl;
            return;
        }
    }
    cout<<-1<<endl;
}
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    int T=1;cin>>T;
    while(T--) solve();
    return 0;
}