题解 P4282 【[AHOI2008]计算器】

· · 题解

题目链接

题意概述

现在有两个 n 位数，每一位的进制不同，第 i 位为 x_i 进制，要求他们两个的和或差。

题目分析

一看这道题，大家应该就会想到高精度，首先我们把它分为两种情况，第一种情况是计算和，第二种情况为计算差。

我们通过高精度，模拟题意，分别计算出和与差，最后输出，输出时要注意，最后一个数字后面没有空格。

那么我们如何计算和与差呢？

和：首先，我们先计算出每一位的和，然后，我们进行进位操作。

差：与和一样，先计算出差后，如果小于零，便不断地向高位借位，直到得到的数大于等于零为止。

注意：我们输入的时候是从高位开始的，所以，我们进行操作的时候要倒着循环。

详细解释请看代码：

代码

#include <bits/stdc++.h> // 万能头 
using namespace std;
int n;
int x[100005], a[100005], b[100005], sum[100005]; // x 为进制，a 和 b 为两个变进制数，sum 记录和与差
/* ---------------------------------------------- */ 
void he() {
    for (int i = n; i >= 1; i--) { // 注意要倒序
        sum[i] += a[i] + b[i]; // 算和 
        a[i - 1] += sum[i] / x[i]; // 让下一位加上这一位多的数
        // 注意：我们这里是倒序的，因此，上一位应是 i - 1，下面的减法也一样
        sum[i] %= x[i]; // 当前这一位的和对进制取模
        // 进位 
    }
} // 计算加法 
void cha() {
    for (int i = n; i >= 1; i--) {
        sum[i] = a[i] - b[i]; // 算差 
        while (sum[i] < 0) { // 如果求出的差为负就不断借，直到大于零为止
        // 注意：这里一定要用循环，不能只用一个 if，因为你只借一次可能不够用
            a[i - 1]--; // 让上一位减一
            sum[i] += x[i]; // 当前这一位加上借的这一位，借的数就是上一位的进制
        } // 向高位借位 
    }
} // 计算减法 
    // 核心部分
/* ---------------------------------------------- */
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    char c;
    cin >> c;
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    // 输入
/* ---------------------------------------------- */
    if (c == '+') {
        he();
    } else {
        cha();
    }
/* ---------------------------------------------- */
    for (int i = 1; i < n; i++) {
        cout << sum[i] << ' ';
    } // 这里正序输出就可以了
    cout << sum[n] << endl; // 注意：这里最后一个数的后面不能有空格
    // 输出
    return 0; // return 是个好习惯
} // ~ 完美结束！~

AC 记录 （别忘了开 O2）

于是，有的大佬就要问了，题目不是让你对 M + 1 取模吗？

其实是不用的，X 进制的最大值是 M ，那么 M\ mod\ (M + 1) 是不是还是 M 呢？同样，所有比 M + 1 小的数对它取模都等于本身。

题目推荐

https://www.luogu.com.cn/problem/P1601

https://www.luogu.com.cn/problem/P1303

https://www.luogu.com.cn/problem/P1255

https://www.luogu.com.cn/problem/P1009

https://www.luogu.com.cn/problem/P1480

本蒟蒻第一次写题解，希望对大家有帮助！

最后再说一句，大家不要抄袭哦！