题目大意：给你一段区间 [Start，Finish] ，在这段区间中有多少个数的二进制表示下，0 的个数 大于等于 1 的个数。
分析：
1、很显然是数位DP，枚举这区间中所有数的二进制位数。由于与 0 的个数有关，故需要用 lead 标记前导零情况。
2、然后就是要处理 1 的个数与 0 的个数，故 dp 的第二维状态即要表示出枚举到当前位 pos 时所拥有的 0 的个数 （或 1）。
但是你会发现，如果当前知道的是 前面几位中 0 的个数，为了满足题意，我还需要知道前面几位中 1 的个数，然后求差值，再到后面 pos 位中找相应的 dp 值。故为了简便，第二维设的应该是当前 1~pos位中，1的个数减去 0 的个数的差值。由于差值可能为负数，且 20亿 最高不会超过 32 位（二进制），故取 32 为中间值，然后根据枚举位上的 1 或 0 来加减。
故 dp[i][j] 表示，在 1~ i 位中，1 与 0 的个数差值为 j （与 32 的差值）。
本题的记忆化搜索： 当从最高位枚举到第 pos 位时，第 1 ~ pos 位上与当前状态对应于 dp[pos][差值] 时满足条件的个数，这个差值来源于 最高位到 pos 位 。比如从最高位的前三位都为 1 ，那么此时从最高位枚举了 3 位，且sum = 32 + 3 = 35 ，那么 dp[pos][sum] 即求在 sum 为 35 的情况下，第 1 ~ pos 位上，能使得最后 sum<=32 的状态个数。
代码如下：
#include<iostream> #include<algorithm> #include<string.h> using namespace std; int dp[35][75],a[35]; int N,M,res; int dfs(int pos,int sum,bool lead,bool limit){ if(pos==0) return sum<=32; if(!limit&&!lead&&dp[pos][sum]!=-1) return dp[pos][sum]; int up=limit?a[pos]:1; int ans=0; for(int i=0;i<=up;i++){ if(lead&&i==0) ans+=dfs(pos-1,sum,lead,limit&&i==a[pos]); else ans+=dfs(pos-1,sum+(i==0?-1:1),false,limit&&i==a[pos]); } if(!limit&&!lead) dp[pos][sum]=ans; return ans; } int solve(int x) { int pos=0; while(x){ a[++pos]=(x&1); x>>=1; } res=pos; return dfs(pos,32,true,true); } int main() { //freopen("test.in","r",stdin); //freopen("test.out","w",stdout); memset(dp,-1,sizeof(dp)); while(~scanf("%d%d",&N,&M)){ printf("%d\n",solve(M)-solve(N-1) ); } }
原文：https://www.cnblogs.com/Absofuckinglutely/p/11413382.html