题目描述
输入一个正整数m,请输出从0到m中每一个数字二进制数中含有1的个数的总和,由于数值较大结果需要模100000.

输入格式
一个m

输出格式
二进制数中含有1的个数的总和s

输入输出样例
输入
2
输出
2
输入
5
输出
7
说明/提示
样例说明
20%的数据 m<=500
50%的数据 m<=1000
70%的数据 m<=50000000
100%的数据 m<=100000000

内存限制500MB

知识点:
统计kk这个数在二进制的表示下有几个1,代码如下:
#include <iostream> using namespace std; int main() { int kk; cin>>kk; int
count= 0; while(kk) { kk = kk & (kk-1);//核心代码 count++; } cout<<count<<endl;
return 0; }
解题思路:
这种解法,有几个1就执行几次。
把一个整数减去1,再与原数字做按位与运算,会把原数二级制位中最右边的1变成0.那么一个整数二进制表示中有几个1,就可以进行几次这样的操作。
0111减去1变成0110,二者进行与运算变成0110,则把原数做右边的1变成0.循环往复直到全为0结束。

代码如下:
#include <iostream> using namespace std; int main() { int m; cin >> m; int
count= 0; for (int i = 0; i <= m; i++) { int c = i; while (c) { c = c & (c - 1);
count++; } count = count % 100000; } cout << count << endl; return 0; }
但是我们会发现,上面的代码在运算过程,会进行很多重复运算,我们明明可以对这些数字进行记忆化,在运算过程中,之前算过的数,我们就不要算了,所以我们可以用dp

代码如下:
#include <iostream> using namespace std; const int N = 100000010; const int MOD
= 100000; int dp[N]; int main() { int sum = 0; int m; cin >> m; dp[0] = 0; for (
int i = 1; i <= m; i++) { dp[i] = dp[i & (i - 1)] + 1; dp[i] %= MOD; sum += dp[i
]; sum %= MOD; } cout << sum << endl; return 0; }

技术
©2019-2020 Toolsou All rights reserved,
css中上下左右居中的几种实现方法[CISCN 2019 初赛]Love Mathc/c++语言实现登陆界面Unity3D 人称设置(第一人称视角、第三人称视角)Fastadmin框架自定义搜索操作流程2021最新Python自动化软件测试笔试题(含答案)黑客帝国装逼的代码雨mysql数据库设置字符集配置修改my.ini文件(windows)python之panda模块1Python学习笔记:基础+进阶10道练习题