PAT-B 1048. 数字加密、 1049 数列的片段和

B1048：实现一个数字加密方法，测试点2、测试点5有点小坑。

B1049：求一个数列和，推导出公式计算。

B1048

原题

本题要求实现一种数字加密方法。首先固定一个加密用正整数A，对任一正整数B，将其每1位数字与A的对应位置上的数字进行以下运算：对奇数位，对应位的数字相加后对13取余——这里用J代表10、Q代表11、K代表12；对偶数位，用B的数字减去A的数字，若结果为负数，则再加10。这里令个位为第1位。

输入格式：

输入在一行中依次给出A和B，均为不超过100位的正整数，其间以空格分隔。

输出格式：

在一行中输出加密后的结果。

输入样例：

1234567 368782971

输出样例：

3695Q8118

题目大意

输入两个整数，然后按末位对齐，从末位开始分奇数位和偶数位，使用不同的方法分别处理数字得出答案。

开始的思路是利用C++的string类记录整数A和B，然后使用string类的length方法获得A的长度alen和B的长度blen。blen减alen得到两个字符串长度的差值diff，利用diff实现末位对齐，设i = blen - 1此时B的末位是B[i]，A的末位是A[i - diff]，计算得出答案，第一版代码：

char L[13] = { '0','1','2','3','4','5','6','7','8','9','J','Q','K' };

int main() {
    string A, B;
    cin >> A >> B;
    int alen, blen, diff;
    alen = A.length();
    blen = B.length();
    diff = blen - alen;
    char C[109];
    C[blen] = '\0'; \\ C存储答案，方便最后输出先令'\0'为字符串结尾
    for (int i = blen - 1; i >= 0; i--) {
        if ((i - diff) < 0) {
            C[i] = B[i];
            continue;
        }
        int a, b;
        b = int(B[i] - 48);
        a = int(A[i - diff] - 48);
        if ((blen + i) % 2 == 1) {
            C[i] = L[(a + b) % 13];
        }
        else {
            C[i] = char((b - a) < 0 ? (b - a + 10 + 48) : (b - a + 48));
        }
    }
    cout << C;
    return 0;
}

提交之后发现测试点2和测试点5不通过，排查了很久之后发现问题在于这个算法只考虑了B比A长的情况，当A比B长时会把A长的部分忽略。而题目中的输入样例也只给出了B比A长的情况。实际上当A比B长时，B不足的部分需要补零。这样就需要加一个判断条件，最后的AC代码是

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
char L[13] = { '0','1','2','3','4','5','6','7','8','9','J','Q','K' };

int main() {
    string A, B;
    cin >> A >> B;
    int alen, blen, diff;
    alen = A.length();
    blen = B.length();
    diff = blen - alen;
    char C[110];

    C[alen > blen? alen : blen] = '\0';
    if (blen >= alen) {
        for (int i = blen - 1; i >= 0; i--) {
            if ((i - diff) < 0) {
                C[i] = B[i];
                continue;
            }
            int a, b;
            b = int(B[i] - 48);
            a = int(A[i - diff] - 48);
            if ((blen + i) % 2 == 1) {
                C[i] = L[(a + b) % 13];
            }
            else {
                C[i] = char((b - a) < 0 ? (b - a + 10 + 48) : (b - a + 48));
            }
        }
    }
    else {
        for (int i = alen - 1; i >= 0; i--) {
            int a, b;
            a = int(A[i] - 48);
            if ((i + diff) < 0) {
                b = 0;
            }
            else {
                b = int(B[i + diff] - 48);
            }

            if ((alen + i) % 2 == 1) {
                C[i] = L[(a + b) % 13];
            }
            else {
                C[i] = char((b - a) < 0 ? (b - a + 10 + 48) : (b - a + 48));
            }
        }
    }
    cout << C;
    system("pause");
    return 0;
}

因为有分支处理所以最后的代码很长。这个时候更好的做法是先统一对齐两个字符串，然后再进行处理。

《算法笔记》的思路是：对两个字符串A、B进行反转，然后字符串的第一位就是原整数的各个位。

注意点

当输入整数长度不相等时，不足的需要补零
输出的结果保证不会出现前导零的情况，不需要另外考虑。

B1049

原题

PAT (Basic Level) - 1049. 数列的片段和

给定一个正数数列，我们可以从中截取任意的连续的几个数，称为片段。例如，给定数列{0.1, 0.2, 0.3, 0.4}，我们有(0.1) (0.1, 0.2) (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4) (0.2) (0.2, 0.3) (0.2, 0.3, 0.4) (0.3) (0.3, 0.4) (0.4) 这10个片段。

给定正整数数列，求出全部片段包含的所有的数之和。如本例中10个片段总和是0.1 + 0.3 + 0.6 + 1.0 + 0.2 + 0.5 + 0.9 + 0.3 + 0.7 + 0.4 = 5.0。

输入格式：

输入第一行给出一个不超过105的正整数N，表示数列中数的个数，第二行给出N个不超过1.0的正数，是数列中的数，其间以空格分隔。

输出格式：

在一行中输出该序列所有片段包含的数之和，精确到小数点后2位。

输入样例：

4
0.1 0.2 0.3 0.4

输出样例：

5.00

简单地推导一下，发现对于输入数列L的第i项L[i]，L[i]在所有片段中出现的次数为L[i] * (N - i) * (i + 1.0);，AC代码：

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    int N;
    cin >> N;
    double L[100010];
    for (int i = 0; i < N; i++) {
        cin >> L[i];
    }
    double sum = 0;
    for (int i = 0; i < N; i++) {
        sum += L[i] * ((double)N - (double)i) * ((double)i + 1.0);
    }

    printf("%0.2f", sum);
    system("pause");
    return 0;
}

注意点

用单精度float会导致答案错误，所以需要用双精度，并且使用强制类型转换。