從a枚舉到b是一定會(huì)超時(shí)的。此題應(yīng)該考慮數(shù)位dp，也可以理解為遞推，假設(shè)給定數(shù)n，就能在O(32)復(fù)雜度算出所有小于等于n的數(shù)中1出現(xiàn)的次數(shù)，那么給定區(qū)間[a, b]，solve(b) - solve(a - 1)就是答案。

     把n化為二進(jìn)制考慮，假設(shè)當(dāng)前有k位前綴保持不變，且第k+1位為1，前綴中共有 cnt 個(gè)1，除去前k+1位，還剩余x位，那么答案應(yīng)該增加 cnt * (2 ^ x) + h(x) ，h(x)表示這x位數(shù)字1的個(gè)數(shù)，注意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){  //測試函數(shù)	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;}如有不當(dāng)之處歡迎指出！