题解 SP10606 【BALNUM - Balanced Numbers】

· · 题解

题目传送门

算法：数位 dp

不熟悉数位 dp 的同学可以看一下洛谷日报第 84 期

“求出在给定区间 [A,B] 内，符合条件 f(i) 的数 i 的个数。条件 f(i) 一般与数的大小无关，而与数的组成有关。”根据日报中给出的数位 dp 的基本模板，容易想到这是一道数位 dp 。

根据题意，要记录当前某一个数码是否出现过，以及出现次数。

由于只关心出现次数的奇偶性，可以使用压缩的一个二进制数 sta （ state 的缩写）表示，某一位上的 1 表示出现了奇数次，0 表示出现了偶数次。但这里存在一个问题，0 既可以表示出现了偶数次，也可以表示没有出现 （0 也是偶数（雾）） ，为了解决这个问题，可以再开一个变量 apr （ appear 的缩写）表示某一个数码是否出现过，同理，1 表示出现过，0 表示没出现过。

由于数字 0 的特殊性，我们还要开一个变量，标记当前的 0 是不是前导 0 。如果是前导 0 ,那么是不需要统计到出现的 0 的个数的，否则需要统计。如果上一位是前导 0，并且这一位也是 0，那么还是前导 0，否则是数字中间的 0，需要记录。

上代码 （详细见代码）

#include<bits/stdc++.h>
#define int long long//懒惰做法 
#define F(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
const int N=1.5e6;
int T,l,r,f[50];
int dp[30][N],num;
map<pair<int,int>,int> mp;//记录当前状态{sta,apr}是否出现过（用数组也可以） 
bool check(int sta,int apr) {
    F(i,0,9){
        if(apr&1<<i){//数码 i 出现过 
            if((i&1) and (sta&1<<i))return false;
            //i 是 奇数，且出现了奇数次 
            if(!(i&1) and !(sta&1<<i))return false;
            //i 是偶数，且出现了偶数次 
        }
    }
    return true;
}
int dfs(int pos,int sta,int apr,bool lim,bool pre) {
    //pos:当前dp从高到低第pos位数字 
    //lim：是不是存在最高位的限制
    //pre：判断上一位是不是前导0 
    if(!pos)return check(sta,apr);
    if(!lim and !pre and dp[pos][mp[{sta,apr}]]!=-1)return dp[pos][mp[{sta,apr}]];
    int s=0;
    for(int i=0; i<=(lim?f[pos]:9); i++) {
        bool ok=pre&&(!i);
        s+=dfs(pos-1,ok?sta:sta^(1<<i),ok?apr:apr|(1<<i),lim and i==f[pos],ok);
        //不是前导0时，sta中第i位要 ^1 （1变0,0变1），apr中记录数码i出现过 
    }
    if(!lim and !pre)mp[{sta,apr}]=++num,dp[pos][num]=s;
    return s;
}
int solve(int x) {//板子 
    int cnt=0;
    while(x)f[++cnt]=x%10,x/=10;
    return dfs(cnt,0,0,1,1);
}
signed main() {//用 signed 可以使define int long long不会爆掉
    memset(dp,-1,sizeof(dp));//初始化 -1 代表没搜过 
    scanf("%lld",&T);
    while(T--) {
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",solve(r)-solve(l-1));
    }
    return 0;
}

感谢观看