题目大意：求区间[l,r]之间的数字的二进制形式中0的个数大于等于1 的数字的个数。
题目思路：比较特殊二进制的第一位必须是1，所有需要一个记录一下第一位是否被填过。剩下的就是一般的数位DP了
#include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<stdio.h> #include<stdlib.h> #include<queue> #include<math.h> #include<map> #define INF 0x3f3f3f3f #define MAX 1000005 #define Temp 1000000000 #define mod 2520 #define LL long long using namespace std; int bit[MAX]; LL dp[100][100][100]; LL dfs(int pos,int sum0,int sum1,int limit,int fst) { if(pos<0) { if(fst)return 1;//若第一位始终没有被填过，那么这个数是0, else { if(sum0 >= sum1)return 1; return 0; } } if(!limit && dp[pos][sum0][sum1]!=-1 && !fst) return dp[pos][sum0][sum1]; int len=limit?bit[pos]:1; LL ans=0; for(int i=0;i<=len;i++) { if(fst) { if(i==0) ans+=dfs(pos-1,0,0,limit&&i==len,1);//若第一位没被填过，继续向下寻找 else ans+=dfs(pos-1,sum0,sum1+1,limit&&i==len,0); } else { if(i==0) ans+=dfs(pos-1,sum0+1,sum1,limit&&i==len,0); else ans+=dfs(pos-1,sum0,sum1+1,limit&&i==len,0); } } if(!limit && !fst) dp[pos][sum0][sum1]=ans; return ans; } LL solve(int k) { memset(bit,0,sizeof(bit)); memset(dp,-1,sizeof(dp)); int len=0; while(k) { bit[len++]=k%2; k/=2; } return dfs(len-1,0,0,1,1); } int main() { int a,b; while(scanf("%d%d",&a,&b)!=EOF) { LL ans1=solve(a-1); LL ans2=solve(b); LL ans=ans2-ans1; printf("%lld ",ans); } return 0; }