POJ3252 Round Numbers

题目描述

求L,R之间满足如下条件的数的个数：二进制下0的个数比1的个数多，1≤L≤R≤2e9

题解

题目要求是二进制，所以在数位DP时，按二进制DP，在计算0,1个数时由于前导零的影响，所以记录了0的个数和1的个数。

这道题说明数位DP不只是十进制

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int l,r;
int f[35][35][35][2];
int len,num[35];

int dfs(int s,int sum0,int sum1,int lim,bool qdl){
    if(!s) return sum0>=sum1;
    if(!lim&&f[s][sum0][sum1][qdl]!=-1) return f[s][sum0][sum1][qdl];
    int mx= lim ? num[s] : 1 ;
    int ret=0;
    for(int i=0;i<=mx;i++)
     ret+=dfs(s-1,!qdl&&!i ? sum0+1 : sum0,i ? sum1+1 : sum1,lim&&i==mx,qdl&&!i);
    if(!lim) f[s][sum0][sum1][qdl]=ret;
    return ret;
}

int cx(int x){
    len=0;
    while(x){
        num[++len]=x&1;
        x>>=1;
    }
    return dfs(len,0,0,true,true);
}

int main(){
    memset(f,-1,sizeof(f));
    scanf("%d%d",&l,&r);
    printf("%d",cx(r)-cx(l-1));
}

View Code

好像可以用组合数，不过我不会