C/C++每日一练17

第一题：小乐乐改数字

题目描述：小乐乐获得了一个数字 n，他想把这个数字改成 m。每次操作可以将数字的某一位加 1 或减 1，求最少操作次数。算法原理：每个数位的修改是独立的，比如个位、十位等，修改某一位不会影响其他位。例如 n=123，m=456，个位 3 到 6 需 + 3，十位 2 到 5 需 + 3，百位 1 到 4 需 + 3，总操作 3+3+3=9 次。因此，直接遍历两个数字的每一位，用绝对值计算差值并累加，结果即为最少操作次数。代码：

cpp

运行

#include <iostream> #include <string> #include <cmath> using namespace std; int main() { string n, m; cin >> n >> m; int res = 0; for (int i = 0; i < n.size(); ++i) { res += abs(n[i] - m[i]); } cout << res << endl; return 0; }

第二题：十字爆破

题目描述：在 n×n 的网格中，每个格子有一个数字。选择一个格子进行 “十字爆破”，会使该格子所在行和列的所有数字变为 0，求爆破后网格中 0 的最大数量。算法原理：对每个格子 (x,y)，计算爆破后 0 的总数。首先统计爆破前该行和该列已有的 0 的数量，注意 (x,y) 若本身是 0，会被重复统计，需减 1。爆破后新增的 0 数量为 “行长度 + 列长度 - 1”，加上原有 0 的数量就是总 0 数。遍历所有格子取最大值，且结果不能超过网格总格子数 n×n。代码：

cpp

运行

#include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<vector<int>> grid(n, vector<int>(n)); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cin >> grid[i][j]; } } int max_zero = 0; for (int x = 0; x < n; ++x) { for (int y = 0; y < n; ++y) { int cnt = 0; for (int i = 0; i < n; ++i) { if (grid[i][y] == 0) cnt++; } for (int j = 0; j < n; ++j) { if (grid[x][j] == 0) cnt++; } if (grid[x][y] == 0) cnt--; int total = cnt + (n + n - 1); if (total > max_zero) max_zero = total; } } cout << min(max_zero, n * n) << endl; return 0; }

第三题：比那名居的桃子

题目描述：树上有 n 个桃子，每次可以摘 1 个或 2 个，求有多少种不同的摘法。算法原理：这是斐波那契数列问题。设 f (n) 为摘 n 个桃子的方法数，最后一次摘 1 个时，前面 n-1 个有 f (n-1) 种方法；最后一次摘 2 个时，前面 n-2 个有 f (n-2) 种方法，故递推公式 f (n)=f (n-1)+f (n-2)。边界条件：n=1 时 f (1)=1，n=2 时 f (2)=2。用迭代法计算 f (n)，时间复杂度 O (n)，空间复杂度 O (1)。代码：

cpp

运行

#include <iostream> using namespace std; int main() { int n; cin >> n; if (n == 1) { cout << 1 << endl; return 0; } int a = 1, b = 2; for (int i = 3; i <= n; ++i) { int c = a + b; a = b; b = c; } cout << b << endl; return 0; }