Round Numbers

如你所知，奶牛没有手指，所以他们不能用石头剪刀布去做例如谁先去挤奶之类的游戏，他们甚至不能投硬币因为用蹄子投硬币太难了。
因此，他们把目光投向了整数，两只奶牛各自选取一个两亿之内的整数，如果这两个整数都是“Round Number”，那么第一个奶牛获得胜利，否则第二只奶牛胜利。
一个正整数n被称作一个“Round Number”，当且仅当这个数的二进制零的个数比一的个数多，或者一样多。例如9是“Round Number”，因为9的二进制是1001；而26不是，因为26的二进制是11010。
显然，奶牛需要花很多时间去做进制转换取决定赢家。贝茜想要作弊，她确信如果她知道一段区间内“Round Number”的个数就能作弊。
请告诉她在给定的闭区间[l,r]内有多少个数是“Round Number”。

输入描述:

两个由空格分割的整数，表示区间的l,r端点。1<=l,r<=2x10^9。

输出描述:

一个整数代表给定区间内的“Round Number”数量。

示例1
输入

2 12

输出

6

roundnumber.cppview raw

#include<stdio.h>
#include<string.h>
#include<iostream>
#define LL long long
using namespace std;
int dp[35][2][70];
int num[40],len;
int Abs(int x){ return x>0?x:-x; }
int dfs(int pos,bool lead0,int cha,bool limit){
    if(pos==0)return cha>=0;
    if(!limit&&~dp[pos][lead0][cha+35])return dp[pos][lead0][cha+35];
    int up=limit?num[pos]:1;
    int cnt=0;
    for(int i=0;i<=up;i++){
        if(lead0){
            if(i==0)cnt+=dfs(pos-1,1,cha,limit&&i==up);
            else cnt+=dfs(pos-1,0,cha-1,limit&&i==up);
        }else{
            int k=(i==0)?1:-1;
            cnt+=dfs(pos-1,0,cha+k,limit&&i==up);
        }
    }
    return limit?cnt:dp[pos][lead0][cha+35]=cnt;
}
int solve(int n){
    len=0;
    while(n){
        num[++len]=n%2;
        n/=2;
    }
    memset(dp,-1,sizeof(dp));
    return dfs(len,1,0,1);
}
int main(){
    int a,b;
    scanf("%d %d",&a,&b);
    printf("%d\n",solve(b)-solve(a-1));
    return 0;
}