题解：SP10606 BALNUM - Balanced Numbers

· · 题解

分析：

修改了一处笔误，望管理通过。

考虑用数位 dp 计算个数。当我们每次选择了一个数时，考虑将选择的数记录下来，发现最多只有 10 个数会被选择，考虑状态压缩简便写法。

每次记录一个二进制 st 每一位表示当前数字的奇偶性，但我们发现没有出现有可能也被表示为偶数，所以再用一个变量记录是否出现。

其他内容就正常写，维护限制和前导零，然后记忆化，每次到边界时，判断合法性。

最后一个小技巧：直接将两个二进制数记忆化空间较大，可以考虑用 map 或数组给每一次不同的二进制数编号，只用记忆化编号即可。

代码如下：

#include<bits/stdc++.h>
#define ll long long
#define N 1500001
#define M 1025 
using namespace std; 
ll l,r;
int a[20],T,cnt,top;
ll dp[20][N];
unordered_map<int,int> m[M];//优化空间 
bool check(int x,int y){
    for(int i=0;i<=9;i++){
        if(y&(1<<i)){//表示有这个数 
            if(!(i&1) and !(x&(1<<i))) return 0;//表示偶数出现偶数次 
            if((i&1) and (x&(1<<i))) return 0;//表示奇数出现奇数次 
        }
    }
    return 1;
}
ll dfs(int x,int S,int T,bool lim,bool fz){
    //S 表示某数奇偶性  T 表示某数是否出现 
    if(x==0) return check(S,T);//检查当前合法性 
    if(!lim and !fz and dp[x][m[S][T]]!=-1) return dp[x][m[S][T]];
    int maxn=lim?a[x]:9;
    ll ret=0;
    for(int i=0;i<=maxn;i++){
        bool ok=(fz&(!i));
        ret+=dfs(x-1,ok?S:S^(1<<i),ok?T:T|(1<<i),lim&(i==maxn),ok);
    }
    if(!lim and !fz) m[S][T]=++top,dp[x][m[S][T]]=ret;
    return ret;
}
ll solve(ll x){
    cnt=0;
    while(x) a[++cnt]=x%10,x/=10;
    return dfs(cnt,0,0,1,1);
}
int main(){
    memset(dp,-1,sizeof dp);
    cin>>T;
    while(T--){
        cin>>l>>r;
        cout<<solve(r)-solve(l-1)<<'\n';//前缀处理 
    } 
    return 0;
}