学步园

题意：问你l---r(2*1e9)之间有多少个数转化成二进制数后0的位数 >= 1的位数 的 数有几个。

数位DP

#include <cstdio>
#include <cstring>
int dp[33][33][33], a[33];
int dfs(int len, int one, int zero, bool lim) {
	if(!len) return zero >= one;
	if(!lim && ~dp[len][one][zero]) return dp[len][one][zero];
	int m = lim ? a[len] : 1;
	int ret = 0;
	for(int i = 0; i <= m; i++)
		ret += dfs(len-1, one+(i==1), zero+(!i), lim&&i==m);
	if(!lim) dp[len][one][zero] = ret;
	return ret;
}
int gao(int n) {
	int len = 0;
	while(n) {
		a[++len] = n&1;
		n >>= 1;
	}
	int ret = 1;
	for(int i = 0; i < len; i++)
		ret += dfs(i, 1, 0, i ==len-1);
	return ret;
}
int main() {
	int l, r;
	memset(dp, -1, sizeof(dp));
	while(~scanf("%d%d", &l, &r))
		printf("%d\n", gao(r) - gao(l-1));
	return 0;
}