HOJ13030 数位dp

本文主要是介绍HOJ13030 数位dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://acm.hnu.cn/online/?action=problem&type=show&id=13030

题目意思：给你A B问A -- B之间的二进制表示中1的个数，包括A B本身。

规模：  1 ≤ A ≤ B ≤ 10¹⁶

^{数位dp，第一次深入理解数位dp的含义，总的来说，更具题目意思总结规律。}

我们用dp(x)表示1-x的二进制表示1的个数。那么解就等于dp(B)-dp(A-1);

1     1

2    10

3    11

4   100

5   101

6   110

7   111

8 1000

9 1001

我们看，假设求dp(9)，那么，找到小于9的最大2的幂的整数，是m=8，那么 dp(9) = dp(8-1)+tmp;

那么tmp等于多少呢？？观察，8-9前面多了2个1，为9-（8-1）得到，这是因为离m最近，且大了多少个1，这是肯定的。

其次，9-8=1,9比8大1，因此，dp(1)就是后面那部分多的1的个数了。

最后 dp(n) = n-(m-1) + dp(m-1) +dp(n-m);

#include<iostream>
#include<cstdio>
#include<map>
#define LL long long
#define rt return
using namespace std;
map <LL,LL> mapt;
LL dp(LL x){if(mapt.find(x)!=mapt.end())rt mapt[x];if(x<=0)rt 0;LL cnt=0,n=x;while(x){x/=2;cnt++;}cnt--;LL m=1;while(cnt--)m*=2;LL a=n-(m-1);LL b=dp(m-1);mapt[m-1]=b;LL c=dp(n-m);rt a+b+c;
}
int main(){LL x,y;while(~scanf("%I64d%I64d",&x,&y)){printf("%I64d\n",dp(y)-dp(x-1));}return 0;
}

这篇关于HOJ13030 数位dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---