五、 标准题解代码 (C++14)

/**
 * 题目：蛋白质的质量计算 (Protein Mass Calculator)
 * 算法：模拟 / 数组映射 (Simulation / Array Mapping)
 * 难度：GESP 4级 / CSP-J T1
 */

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 用数组做简单的映射表
// 大写字母的 ASCII 码在 65-90 之间，开 128 足够
int weights[128];

int main() {
    // 1. I/O 加速
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int K, N;
    if (!(cin >> K >> N)) return 0;

    // 2. 读取氨基酸质量表
    for (int i = 0; i < K; ++i) {
        char type;
        int w;
        cin >> type >> w;
        // 直接用字符作为下标存储
        weights[type] = w;
    }

    // 3. 读取肽链序列
    string s;
    cin >> s;

    // 4. 计算氨基酸总质量
    int total_mass = 0;
    for (int i = 0; i < N; ++i) {
        char aa = s[i];
        // 查表累加
        total_mass += weights[aa];
    }

    // 5. 减去水的质量
    // 如果有 N 个氨基酸，形成 N-1 个肽键，脱去 N-1 个水
    // 每个水分子质量 18
    if (N > 1) {
        int water_removed = (N - 1) * 18;
        total_mass -= water_removed;
    }

    cout << total_mass << endl;

    return 0;
}

时间与空间复杂度分析

• 时间复杂度：
  • 建立映射表：$O(K)$（常数级，最多26）。
  • 遍历字符串：$O(N)$。
  • 总时间：$O(N)$。
• 空间复杂度：
  • 映射数组 weights 大小固定 128，$O(1)$。

六、 数据生成器 (Generator.cpp)

/**
 * 题目：蛋白质的质量计算
 * 数据生成器
 */

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <random>
#include <ctime>
#include <set>

using namespace std;

mt19937 rng(time(0));

// 随机生成 K 个不同的氨基酸及其质量
pair<vector<pair<char, int>>, vector<char>> gen_table(int K) {
    vector<pair<char, int>> table;
    vector<char> available_chars;
    
    set<char> used;
    while(used.size() < K) {
        char c = 'A' + rng() % 26;
        if(used.find(c) == used.end()) {
            used.insert(c);
            int w = 50 + rng() % 251; // 质量 50-300
            table.push_back({c, w});
            available_chars.push_back(c);
        }
    }
    return {table, available_chars};
}

int solve(int K, int N, const vector<pair<char, int>>& table, string S) {
    int w[128] = {0};
    for(auto p : table) w[p.first] = p.second;
    
    int total = 0;
    for(char c : S) total += w[c];
    
    if(N > 1) total -= (N - 1) * 18;
    return total;
}

void make_case(int id) {
    int K, N;
    vector<pair<char, int>> table;
    vector<char> chars;
    string S = "";

    switch(id) {
        case 1: // 样例
            K = 3; N = 5;
            table = {{'A', 89}, {'G', 75}, {'L', 131}};
            chars = {'A', 'G', 'L'};
            S = "AGLLA";
            break;
        case 2: // N=1 (无脱水)
            K = 5; N = 1;
            tie(table, chars) = gen_table(K);
            S += chars[0];
            break;
        case 3: // 只有一种氨基酸
            K = 1; N = 100;
            table = {{'X', 100}};
            chars = {'X'};
            for(int i=0; i<N; ++i) S += 'X';
            break;
        case 4: // 小数据随机
            K = 5; N = 20;
            tie(table, chars) = gen_table(K);
            for(int i=0; i<N; ++i) S += chars[rng()%K];
            break;
        case 5: // 中等数据
            K = 10; N = 100;
            tie(table, chars) = gen_table(K);
            for(int i=0; i<N; ++i) S += chars[rng()%K];
            break;
        case 6: // 质量较小
            K = 26; N = 500;
            tie(table, chars) = gen_table(K);
            for(int i=0; i<N; ++i) S += chars[rng()%K];
            break;
        case 7: // 最大 N
            K = 20; N = 1000;
            tie(table, chars) = gen_table(K);
            for(int i=0; i<N; ++i) S += chars[rng()%K];
            break;
        case 8: // 满字符集
            K = 26; N = 1000;
            tie(table, chars) = gen_table(K);
            for(int i=0; i<N; ++i) S += chars[rng()%K];
            break;
        case 9: // 质量很大
            K = 5; N = 1000;
            tie(table, chars) = gen_table(K);
            for(auto &p : table) p.second = 300; // 强制最大质量
            for(int i=0; i<N; ++i) S += chars[rng()%K];
            break;
        case 10: // 结果可能为负? (不可能, 因为氨基酸最小质量>18)
            // 正常大随机
            K = 15; N = 888;
            tie(table, chars) = gen_table(K);
            for(int i=0; i<N; ++i) S += chars[rng()%K];
            break;
    }

    string in_file = to_string(id) + ".in";
    ofstream fout_in(in_file);
    fout_in << K << " " << N << "\n";
    for(auto p : table) fout_in << p.first << " " << p.second << "\n";
    fout_in << S << "\n";
    fout_in.close();

    string out_file = to_string(id) + ".out";
    ofstream fout_out(out_file);
    fout_out << solve(K, N, table, S) << "\n";
    fout_out.close();

    cout << "Generated Case " << id << endl;
}

int main() {
    for(int i=1; i<=10; ++i) make_case(i);
    return 0;
}

这道题难度适中（GESP 4级），将生物学中的“脱水缩合”概念与编程中的“数组映射求和”完美结合，既考察了信息学基础，又巩固了生物学知识。