CACC 2025区域赛前两道题回顾

第一题涉及到了多精度数位

第二题涉及二维动态规划

整理了CACC2025区域赛前两道题，包括大整数数位和计算（多精度）以及二维动态规划最大路径和问题。

---

一、大整数相加并求数位和（多精度问题）

1. 题目描述

输入两个非负整数 a 和 b，计算 a + b 的结果，并输出其数位和。

• 数位和：一个整数各位数字之和

• 示例：

  11 + 23 = 34 → 数位和 = 3 + 4 = 7
  

⚠️ 关键限制：

• a 和 b 的范围可达 (10^{20})

---

2. 为什么 C++ 的 long long 不够用？

• long long 的最大范围约为：
  [
  9.22 * 10^18
  ]
• 显然无法容纳 (10^{20}) 级别的整数

因此：

• C++ 需要使用多精度算法（字符串模拟加法）
• 而Python 不需要担心溢出问题，我在考场上也是用Python做的

---

3. Python 解法（天然支持大整数）

Python 的 int 是任意精度整数，底层采用动态数组存储，没有固定上限。

a, b = map(int, input().split())
s = a + b

ans = 0
while s != 0:
    ans += s % 10
    s //= 10

print(ans)

✔ 写法简洁
✔ 无需考虑溢出

---

4. C++ 解法（字符串模拟多精度加法）

核心思想

1. 将输入的两个大整数当作字符串处理
2. 从最低位开始逐位相加，模拟人工加法（考虑进位）
3. 得到 a + b 的字符串结果
4. 对结果字符串逐位求数位和

---

关键知识点：vector::push_back

• 用于向 vector 尾部添加元素

• 示例：

  vector<int> v;
  v.push_back(10);
  

---

C++ 实现代码

这种方法模拟了我们平时计算多位数的数字从后往前进行进位运算的方法

#include <bits/stdc++.h>
using namespace std;

// 将两个非负整数字符串相加，返回结果字符串
string addStrings(const string &A, const string &B) {
    int i = A.size() - 1;
    int j = B.size() - 1;
    int carry = 0;
    string res;

    while (i >= 0 || j >= 0 || carry) {
        int da = (i >= 0) ? (A[i] - '0') : 0;
        int db = (j >= 0) ? (B[j] - '0') : 0;
        int s = da + db + carry;
        res.push_back(char('0' + (s % 10)));
        carry = s / 10;
        --i; --j;
    }

    return res; // 注意：结果是逆序存储的
}

int main() {
    string a, b;
    cin >> a >> b;

    string sum = addStrings(a, b);

    long long digitSum = 0;
    for (char c : sum) {
        digitSum += (c - '0');
    }

    cout << digitSum << endl;
    return 0;
}

📌 注意：

• res 中的结果是逆序的，但不影响数位和计算

---

二、二维动态规划：魔法阵最大路径和

1. 题目描述

原题需要自己为每个格子进行随机数，但是随机数代码给了，核心就是如何进行道路规划，我把核心问题提炼出来了

给定一个 m × n 的二维矩阵，每个格子包含一个魔法值。

• 起点：左下角 (m-1, 0)

• 终点：右上角 (0, n-1)

• 移动规则：
  

  • 只能 向上 或 向右

目标：

找到一条路径，使路径上魔法值之和最大。

---

2. 错误思路：贪心算法（考试易错点）

直觉做法：

• 每一步只比较「左边」或「下边」较大的数
• 选择局部最大的方向前进

我在考试的时候想错了，我想的是到达右上角的格子就必须从左边或者下边到达，所以我就找左边或者下面大的数，一直找到左下角，但其实这种局部最优解贪心的方法是错误的，会错过潜力更大的路径
应该要考虑的是ij这个格子到最后的目标位置右上角的数字和
这道题应该采用动态规划的思想

❌ 问题：

• 局部最优 ≠ 全局最优
• 可能错过后续潜力更大的路径

---

3. 正确思路：动态规划（DP）

状态定义

设二维数组为 a[m][n]

定义：

dp[i][j] = 从 (i, j) 走到右上角 (0, n-1) 能获得的最大路径和

---

状态转移方程

dp[i][j] = a[i][j] + max(dp[i-1][j], dp[i][j+1])

含义：

• 当前格子的值
• 加上「向上」或「向右」中较大的那条路径

思路：
动态规划新建了一个相同大小的二维数组，这个二维数组用于存储这个格子到达右上角目标位置的数字和
ij位置的格子，应该是ij位置的数字，加上右边或者上边比较大的数字，这样才是从ij到达右上角的最大数字和，因为右边或者上边已经标记了它们到右上角的最大数字和
所以动态规划给其实遍历了每个格子，时间O（mn），它不像贪心，它不会错过，因为它找到了每个格子到最后终点的最大数字和
所以结果就是dp[m-1][0]
dp【m-1】【0】记录着左下角到右上角的最大数字和

---

边界条件

• 最上面一行：只能向右走
• 最右边一列：只能向上走

---

4. C++ 实现代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int m, n;
    cin >> m >> n;

    vector<vector<int>> a(m, vector<int>(n));
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            cin >> a[i][j];

    vector<vector<int>> dp(m, vector<int>(n, 0));

    // 右上角
    dp[0][n - 1] = a[0][n - 1];

    // 第一行（只能向右）
    for (int j = n - 2; j >= 0; --j) {
        dp[0][j] = a[0][j] + dp[0][j + 1];
    }

    // 最右列（只能向上）
    for (int i = 1; i < m; ++i) {
        dp[i][n - 1] = a[i][n - 1] + dp[i - 1][n - 1];
    }

    // 其他位置
    for (int i = 1; i < m; ++i) {
        for (int j = n - 2; j >= 0; --j) {
            dp[i][j] = a[i][j] + max(dp[i - 1][j], dp[i][j + 1]);
        }
    }

    cout << "最大路径和: " << dp[m - 1][0] << endl;

    return 0;
}

---

5. 为什么动态规划一定不会错？

• DP 计算了每一个格子到终点的最优解
• 不会因为局部选择而放弃全局最优路径
• 时间复杂度：O(m × n)
• 空间复杂度：O(m × n)

最终答案：

dp[m-1][0]

---

三、总结

• 大整数问题：

  • Python：直接算
  • C++：字符串 + 多精度思想

• 路径最优问题：

  • 贪心容易出错
  • 动态规划是标准解法

这两道题在考试的时候不太会，于是整理出来并分享，希望对大家也有帮助

---

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/tanzitong/article/details/155936647