链接：http://poj.org/problem?id=3252

题意：一个数写成二进制，0不少于1就是round number，求给定区间内round number的个数。

分析：显然第一步转化为0到n的round number个数。。设n写成二进制有len位，第一位取0时，后面只要满足0的个数要求就行了，不用考虑是否比n大。。可以先预处理一下长度不大于len的round number个数，记做t[len]，t[len]=t[len-1]+∑C(len-1  k) , (k=0,1,...,len/2-1)。

然后第一位取1时，往后是0的位只能取0，遇到第一个1时，再分情况考虑这一位为1和为0，然后考虑还需要多少位，往下递归即可。

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 const int maxn=35; 6 int C[maxn][maxn],sum[maxn][maxn][maxn],t[maxn]; 7 int start,finish; 8 void CalC(){ 9     for(int i=1;i
        
         =len)return n+1;34     int t=len-1;35     while(t>=0&&(n&(1<<(t-1)))==0){36         t--;37     }38     return f(n-(1<<(len-1)),c-1,t)+sum[len-1][0][c];39 }40 int solve(int n){41     if(n==0)return 1;42     int k=1<<30,len=31;43     while((k&n)==0){44         k>>=1;len--;45     }46     int l=len-1;47     while(l>=0&&(n&(1<<(l-1)))==0){48         l--;49     }50     return t[len-1]+f(n-(1<<(len-1)),(len-2)/2,l);51 }52 //bool Is_round(int n){53 //    int k=1,a=0,b=0;54 //    while(k<=n){55 //        if(k&n)a++;56 //        else b++;57 //        k<<=1;58 //    }59 //    if(a<=b)return true;60 //    return false;61 //}62 //int test(int n){63 //    int count=0;64 //    for(int i=1;i<=n;i++){65 //        if(Is_round(i))count++;66 //    }67 //    return count+1;68 //}69 int main(){70     CalC();71     CalT();72     int n;73 //    while(cin>>n){74 //        cout<
         
          <<' '<
          
           <
           
            >start>>finish;77 cout<
            
             <