临沂网站建设培训学校,河北衡水网站建设,山东免费网络推广工具,河北新闻最新消息10条题目描述 输入一个正整数m,请输出从0到m中每一个数字二进制数中含有1的个数的总和,由于数值较大结果需要模100000.
输入格式 一个m
输出格式 二进制数中含有1的个数的总和s
输入输出样例 输入 2 输出 2 输入 5 输出 7 说明/提示 样例说明 20%的数据 m500 50%的数据 m500 50%的数据 m1000 70%的数据 m50000000 100%的数据 m100000000
内存限制500MB
知识点 统计kk这个数在二进制的表示下有几个1代码如下
#include iostream
using namespace std;int main()
{int kk;cinkk;int count 0;while(kk){kk kk (kk-1);//核心代码count;}coutcountendl;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;
}
