洛谷 P6218 [USACO06NOV] Round Numbers S

题目传送门

数位dp

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int l,r,s[101],len;
int f[100][2][2][100][100];

inline void fenjie(int x) {
    memset(s,-1,sizeof(s));
    len = 0;
    while(x != 1) {
        s[++len] = x % 2;
        x /= 2;
    }
    s[++len] = x;
}

inline int dfs(int d,bool li,bool qd,int z,int o) {
    int p = 0;
    if(d == 0) return z >= o;
    if(f[d][li][qd][z][o] != -1) return f[d][li][qd][z][o];
    int res = li ? s[d] : 1;
    for(int i = 0;i <= res; i++)
        p += dfs(d - 1,li && (i == res),qd && (i == 0),z + (!qd && i == 0),o + (i == 1));
    f[d][li][qd][z][o] = p;
    return p;
}

int main() {
    scanf("%d%d",&l,&r);
    memset(f,-1,sizeof(f));
    if(l - 1 != 0) fenjie(l - 1);
    int ans1 = !(l - 1) ? 1 : dfs(len,1,1,0,0);
    memset(f,-1,sizeof(f));
    fenjie(r);
    int ans2 = dfs(len,1,1,0,0);
    printf("%d",ans2 - ans1);
    return 0;
}