上海计算机学会2024年6月月赛C++乙组T1一的数量
发布时间
阅读量：
阅读量
一的数量
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定一个整数 n，请问从 1 开始到 n 结束的所有整数的二进制表示中，共计有多少个 1 ？
输入格式
- 单个整数表示 n
输出格式
- 单个整数表示答案
数据范围
- 30% 的数据，1≤n≤2^10
- 60% 的数据，1≤n≤2^20
- 100% 的数据，1≤n≤2^50
样例数据
输入:
12
输出:
22
解析：模拟法，时间复杂度O(NlogN）可以解决60%的数据，详见代码：
#include <bits/stdc++.h>
using namespace std;
long long n;
long long ans = 0;
int main() {
cin >> n;
for(long long i = 1; i <= n; i++) {
long long t = i;
while(t > 0) {
ans += t % 2;
t /= 2;
}
}
cout << ans;
return 0;
}
AI写代码cpp
正解：
对于二进制的最低位，每两个数有一个1，特别的，如果有余数，那么余数也是1；
对于二进制次低位（倒数第二位），每4个数有两个1，特别的，如果余数是1，也是1，余数是2，有两个1，余数是3，也是两个1，即两个1出现在四个数的前两个数中；
对于倒数第三位，每8个数有4个1，这四个1也出现在前4个数中；
以此类推，则可以依次计算出每一位出现的一的个数，
累加即为答案。
详见代码：
#include <bits/stdc++.h>
using namespace std;
long long n;
long long ans = 0;
int main() {
cin >> n;
for(long long i = 1; i <= n; i *= 2) {
ans += (n - i + 1) / (i * 2) * i + min((n - i + 1) % (i * 2), i);
}
cout << ans;
return 0;
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~