nyoj222 整数中的1 数位DP

       从a枚举到b是一定会超时的。此题应该考虑数位dp，也可以理解为递推，假设给定数n，就能在O(32)复杂度算出所有小于等于n的数中1出现的次数，那么给定区间[a, b]，solve(b) - solve(a - 1)就是答案。

     把n化为二进制考虑，假设当前有k位前缀保持不变，且第k+1位为1，前缀中共有 cnt 个1，除去前k+1位，还剩余x位，那么答案应该增加 cnt * (2 ^ x) + h(x) ，h(x)表示这x位数字1的个数，注意x位中任意一位要么为0要么为1。一直递推即可得到答案，但是没有考虑n本身的1，所以最后把n的1加上就行了。

AC代码：

#include<cstdio>#include<iostream>using namespace std;const int maxn = 35;int w[maxn], h[maxn];void deal(){	h[0] = 0;	w[0] = 1;	w[1] = 2;	h[1] = 1;	for(int i = 2; i < 31; ++i) {		w[i] = w[i - 1] * 2;		h[i] = h[i - 1] + w[i - 1] + h[i - 1];	}}int solve(int n){	if(n == -1) return 0;	int cnt = 0;	int m = n;	while(m > 0){		if(m & 1) cnt++;		m >>= 1;	}	int ans = cnt;	for(int i = 1; n > 0; ++i, n >>= 1){		//cout << i << '/n';				if((n & 1) == 0) continue;		cnt--;		ans += cnt * w[i - 1] + h[i - 1];			}	return ans;}int test(int n){  //测试函数	int ans = 0;	for(int i = 1; i <= n; ++i){		int w = i;		while(w > 0){			if(w & 1) ++ans;			w >>= 1;		}	}	return ans;}int main(){	deal();	int a, b;	while(scanf("%d%d", &a, &b) == 2){		PRintf("%d/n", solve(b) - solve(a - 1));	}	return 0;}如有不当之处欢迎指出！