题意：给定一个区间，求出区间内二进制中0的个数大于等于1的个数的数字有多少个。

　　题解：（学长说这道题是开胃菜。。。我不会写。。。）

　　据说这是一道数位dp题，我觉得写成记忆化搜索的模式更容易被理解。于是我们先把原区间边界分别转为二进制，并将每一位放入dig数组中，我们设计dfs函数：

　　正如大多数数位dp一样，我们需要一个类似光标的东西来记录当前决策到了第多少位，于是出现了len，表示当前是决策的是从左往右数第多少位。

　　如果想统计方案的话，我们首先需要满足题目要求，于是出现了num0和num1，表示0,1,各已出现多少次。其次还要符合我们区间的限制，就是我们统计的任何一个答案都不能超过区间的上界，所以出现了变量flag表示从第一位开始到这一位是否都在上界；还有，如果一个数的二进制位是000000001010111，这个数一定不能算是符合要求，所以我们要记录在这位之前是否已经出现了1，说正式一点就是处理前导零问题，但是为了方便，这里如果出现了我们是用0来表示的，否则是1，之后就可以设计函数了。

　　递归的边界肯定是将一共len位都处理完了，这样的话就返回当前所决策的数是否符合要求，是返回1，否则返回零。然后判断当前状态是否被记忆过，如果是，并且当前没有达到右边界上限，那就直接返回（要是达到上界了也直接返回说不定会返回超过上界的答案，因为状态数组记录的是一个，宽泛的值域，限于决策到这位，也就是说这位以后的位上任何一种情况都记录了，肯定会有超过上界的情况出现）；然后要判断当前是否为上界来决定这位的情况是什么，并且递归搜索，最后记忆化。这题就做完了；

　　下面上代码！

 

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 const int MAXN=50; 8 int f[MAXN][MAXN][MAXN]; 9 int dig[MAXN],n,m,k;10 int dfs(int len,int num0,int num1,bool flag,bool first){11     if(len<0) return num0>=num1;12     if(!flag&&~f[len][num0][num1]) return f[len][num0][num1];13     int ans=0;int end=flag?dig[len]:1;14     for(int i=0;i<=end;i++){15         bool t=first&&(i==0);16         ans+=dfs(len-1,t?0:num0+(i==0),t?0:num1+(i==1),flag&&i==end,t);17     } if(flag==0) f[len][num0][num1]=ans;return ans;18 }19 int solve(int x){20     int len=0;21     while(x){22         dig[len++]=x%2;x>>=1;23     } return dfs(len-1,0,0,1,1);24 }25 int main(){26     while(~scanf("%d%d",&n,&m)){27         memset(f,-1,sizeof(f));28         printf("%d\n",solve(m)-solve(n-1));29     } return 0;30 }