The cows, as you know, have no fingers or thumbs and thus are unable to play Scissors, Paper, Stone' (also known as 'Rock, Paper, Scissors', 'Ro, Sham, Bo', and a host of other names ) in order to make arbitrary decisions such as who gets to be milked first. They can't even flip a coin because it's so hard to toss using hooves.
They have thus resorted to "round number" matching. The first cow picks an integer less than two billion. The second cow does the same. If the numbers are both "round numbers", the first cow wins,
otherwise the second cow wins.
A positive integer N is said to be a "round number" if the binary representation of N has as many or more zeroes than it has ones. For example, the integer 9, when written in binary form, is 1001. 1001 has two zeroes and two ones; thus, 9 is a round number. The integer 26 is 11010 in binary; since it has two zeroes and three ones, it is not a round number.
Obviously, it takes cows a while to convert numbers to binary, so the winner takes a while to determine. Bessie wants to cheat and thinks she can do that if she knows how many "round numbers" are in a given range.
Help her by writing a program that tells how many round numbers appear in the inclusive range given by the input (1 ≤ Start < Finish ≤ 2,000,000,000).
Input
Output
Sample Input
2 12
Sample Output
6
题意：要求给定的区间里面有多少个数的二进制里面的0的个数>=1的个数
思路：因为说的是在一个区间内计数，我们就可以看出这是个数位DP，然后因为我们十进制去枚举统计我们不好统计二进制0 1的个数
所以我们灵活的用二进制形式枚举，然后0，1的个数的话我们去记录他的差值，是0就减1，是1就加1，如果最后的答案是<=0的话就
满足要求，这个题有一个坑的地方就是，你用二进制枚举会出现前导0的情况，前导0对我们这题又有影响，所以需要用个参数记录下来
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<iostream> using namespace std; typedef long long ll; ll a[50]; ll dp[50][200]; ll w[50]; ll dfs(ll ans,ll c,bool vis,bool flag) { if(ans==-1) { if(vis) return 1; return c<=0;//c代表0个数和1个数的差值，所以我们判断c<=0 } if(!flag&&!vis&&dp[ans][c+100]!=-1) return dp[ans][c+100];/因为我们纪录的差值，所以我们数组记录的时候会出现负数，所以我们+100来避免 ll up=flag?a[ans]:1; ll tmp=0; for(int i=0;i<=up;i++) { if(vis) { if(i==0) tmp+=dfs(ans-1,0,1,flag&&a[ans]==i);//如果上一位有前导0，这一次也是前导0的话就延续下去 else tmp+=dfs(ans-1,c+1,0,flag&&a[ans]==i);//上一次是前导0，这一次出现了1就代表没有前导0了 } else { if(i==0) tmp+=dfs(ans-1,c-1,0,flag&&a[ans]==i);//因为前面已经出现1了，后面出现的0都没有关系 else tmp+=dfs(ans-1,c+1,0,flag&&a[ans]==i); } } if(!flag&&!vis) dp[ans][c+100]=tmp; return tmp; } ll suan(ll x) { ll ans=0; while(x) { a[ans++]=x%2; x/=2; } return dfs(ans-1,0,1,1); } int main() { ll l,r; memset(dp,-1,sizeof(dp)); while(cin>>l>>r) { cout<<suan(r)-suan(l-1)<<endl; } }