[数位dp] kuangbinoj 1012 bin巨的数

题意：

作为ACM史上年度重量级人物，bin巨目前已经掌握了史上最NB的数，群巨快来仰慕！！我们定义这样一个数，它里面的每一个数字都是成双成对出现 的，but，如果这个数里面存在0那么这也是NB的数，比如11，，122122，12035，当然，需要剔除那些首位是0的数。我们的目标就是计算一个区 间内bin巨有多少NB数！

思路：

简单的数位dp，需要考虑每个数字出现的次数（0,1），是否有前导0，是否出现了0.

这里需要注意的就是0不是一个bin巨数。

#include"cstdlib"#include"cstdio"#include"cstring"#include"cmath"#include"queue"#include"algorithm"#include"iostream"#include"map"#define ll long longusing namespace std;ll dp[22][2025][2][2];int num[22];int fun(int x){for(int i=1;i<=9;i++) if(x&(1<<i)) return 0;return 1;}ll dfs(int site,int ok,int zero,int kx,int f){if(site==0){if(zero==0) return 0;if(kx) return 1;return fun(ok);}if(!f && dp[site][ok][zero][kx]!=-1) return dp[site][ok][zero][kx];int len=f?num[site]:9;ll ans=0;for(int i=0; i<=len; i++){if(zero==0 && i==0) ans+=dfs(site-1,ok,0,0,f&&i==len);else if(kx) ans+=dfs(site-1,0,1,1,f&&i==len);else{if(i==0) ans+=dfs(site-1,0,1,1,f&&i==len);else{int tep=ok;if(tep&(1<<i))tep-=(1<<i);else tep|=(1<<i);ans+=dfs(site-1,tep,1,0,f&&i==len);}}}if(!f) dp[site][ok][zero][kx]=ans;return ans;}ll solve(ll x){if(x<0) return 0;int cnt=0;while(x){num[++cnt]=x%10;x/=10;}return dfs(cnt,0,0,0,1);}int main(){int t;memset(dp,-1,sizeof(dp));cin>>t;while(t–){ll a,b;scanf("%lld%lld",&a,&b);if(a>b) swap(a,b);printf("%lld\n",solve(b)-solve(a-1));}return 0;}

获致幸福的不二法门是珍视你所拥有的遗忘你所没有的。