落谷B3703 新年快乐题解
时间: 2023-09-21 18:02:49 浏览: 98
落谷B3703 新年快乐题解
这道题是一道比较简单的数学题,需要我们找到一个数在二进制下的每一位上的数字之和,然后再求和。
我们可以使用循环和位运算来解决这个问题。具体的思路如下:
1. 读入一个整数 n;
2. 定义一个变量 sum,用于记录每个数的二进制每一位上的数字之和;
3. 使用循环遍历 n 的每一位,可以使用位运算来实现;
4. 对每一位进行判断,如果是 1,则将 sum 加上 1,否则不做任何操作;
5. 最后输出 sum。
以下是使用 C++ 语言实现的代码:
```
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int sum = 0;
while (n > 0) {
if (n & 1) {
sum += 1;
}
n >>= 1;
}
cout << sum << endl;
return 0;
}
```
以上就是本题的解答,希望对大家有所帮助,祝大家新年快乐!
相关问题
用c++编写数位dp落谷
数位 DP 是一个非常实用的算法,可以用于求解数字的各种性质。下面以计算 $[1,n]$ 中所有整数中数字 $d$ 出现次数的问题为例,介绍数位 DP 的实现方法。
假设我们要求出数字 $d$ 在 $[1,n]$ 中出现的次数,可以考虑将 $n$ 拆分成若干个数位,然后逐位统计 $d$ 出现的次数。具体地,我们可以使用 $f_{i,j,k}$ 表示考虑前 $i$ 位,当前数值为 $j$,是否达到上界 $k$ 的方案数。然后按照从高到低的顺序逐位进行统计。
状态转移方程为:
$$
f_{i,j,k}=\sum_{p=0}^9 f_{i-1,p,k \ \&\&\ p=j} + [k=1]\times [j=d] \times (\text{数位 DP 的计算结果})
$$
其中 $[x]$ 表示 Iverson 括号,当 $x$ 成立时为 $1$,否则为 $0$。第一项表示上一个数位传递下来的方案数,第二项表示当前数位对答案的贡献。
最终的答案为 $f_{\text{len}(n),0,1}$。
代码实现如下:
```cpp
int f[20][10][2]; // f[i][j][k] 表示考虑到第 i 位,当前数字为 j,是否达到上界的方案数
int digit[20]; // 存储 n 的每一位数字
int dfs(int pos, int pre, bool limit, int d) {
if (pos == -1) return 0;
if (!limit && f[pos][pre][d] != -1) return f[pos][pre][d];
int up = limit ? digit[pos] : 9;
int res = 0;
for (int i = 0; i <= up; i++) {
res += dfs(pos - 1, i, limit && (i == up), d) + (pre == d && i == d && !limit) ;
}
if (!limit) f[pos][pre][d] = res;
return res;
}
int solve(int n, int d) {
memset(f, -1, sizeof(f));
int pos = 0;
while (n) {
digit[pos++] = n % 10;
n /= 10;
}
return dfs(pos - 1, 0, true, d);
}
```