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

/**
 * 题目：破译遗传密码 (Deciphering the Genetic Code)
 * 算法：字符串扫描 / 模运算 (String Scan / Modulo)
 * 难度：GESP 5级 / CSP-J T2
 */

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

using namespace std;

// 辅助函数：判断是否为终止密码子
bool is_stop(const string& codon) {
    return codon == "UAA" || codon == "UGA" || codon == "UAG";
}

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

    int N;
    if (!(cin >> N)) return 0;
    
    string S;
    cin >> S;

    int max_amino_acids = 0;

    // 2. 分三种阅读框 (Frame) 进行扫描
    // frame = 0, 1, 2
    for (int frame = 0; frame < 3; ++frame) {
        
        int start_index = -1; // -1 表示当前还没有开始翻译

        // 每次跳 3 个字符
        for (int i = frame; i + 2 < N; i += 3) {
            // 提取当前密码子 (3个字符)
            // S.substr(i, 3) 会产生新字符串，稍微慢一点点，但对于 N=10^6 也可以接受
            // 为了追求极致性能，可以直接判断字符
            string codon = S.substr(i, 3);

            if (start_index == -1) {
                // 状态：寻找 AUG
                if (codon == "AUG") {
                    start_index = i;
                }
            } else {
                // 状态：正在翻译中，寻找终止密码子
                if (is_stop(codon)) {
                    // 找到终止，计算长度
                    // 距离 = 当前终止的位置 - 起始位置
                    // 氨基酸数量 = 距离 / 3
                    int length = (i - start_index) / 3;
                    if (length > max_amino_acids) {
                        max_amino_acids = length;
                    }
                    
                    // 生物学逻辑：一条mRNA上可能有多个ORF
                    // 结束当前链后，重置状态，继续寻找下一个可能的 AUG
                    start_index = -1; 
                }
                // 如果是普通密码子，或者是中间遇到的 AUG，都继续，不做操作
            }
        }
    }

    cout << max_amino_acids << endl;

    return 0;
}

时间与空间复杂度分析

• 时间复杂度：
  • 外层循环 3 次。
  • 内层循环每次约 $N/3$ 次。
  • 总共遍历次数 $\approx N$。
  • 字符串截取 substr 和比较是常数时间 $O(1)$（因为长度固定为3）。
  • 总复杂度 $O(N)$。
• 空间复杂度：
  • 只存储了输入字符串 $S$ 和几个变量。
  • $O(N)$。

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

这是一个用来生成 1.in ~ 10.in 和对应 1.out ~ 10.out 的工具。

/**
 * 题目：破译遗传密码
 * 数据生成器
 */

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

using namespace std;

mt19937 rng(time(0));
const char BASES[] = {'A', 'U', 'C', 'G'};

// 辅助函数
bool is_stop(const string& s) {
    return s == "UAA" || s == "UGA" || s == "UAG";
}

int solve(int N, string S) {
    int max_len = 0;
    for (int frame = 0; frame < 3; ++frame) {
        int start = -1;
        for (int i = frame; i + 2 < N; i += 3) {
            string codon = S.substr(i, 3);
            if (start == -1) {
                if (codon == "AUG") start = i;
            } else {
                if (is_stop(codon)) {
                    int len = (i - start) / 3;
                    if (len > max_len) max_len = len;
                    start = -1;
                }
            }
        }
    }
    return max_len;
}

// 生成随机RNA
string rand_rna(int n) {
    string s = "";
    s.resize(n);
    for(int i=0; i<n; ++i) s[i] = BASES[rng() % 4];
    return s;
}

// 埋入答案：在随机位置插入 Start + N个Codon + Stop
void inject_gene(string &s, int target_len) {
    int n = s.length();
    // 找一个随机位置，且保证空间足够
    // 需要长度: 3 (AUG) + target_len*3 + 3 (Stop)
    int total_chars = 3 + target_len * 3 + 3;
    if (total_chars > n) return; // 容错

    int pos = rng() % (n - total_chars + 1);
    
    // 插入 AUG
    s[pos] = 'A'; s[pos+1] = 'U'; s[pos+2] = 'G';
    pos += 3;
    
    // 插入氨基酸 (避免 Stop)
    for(int i=0; i<target_len; ++i) {
        // 随机生成一个非Stop的密码子
        while(true) {
            char a = BASES[rng()%4];
            char b = BASES[rng()%4];
            char c = BASES[rng()%4];
            string t = ""; t+=a; t+=b; t+=c;
            if(!is_stop(t)) {
                s[pos] = a; s[pos+1] = b; s[pos+2] = c;
                break;
            }
        }
        pos += 3;
    }
    
    // 插入 Stop (UAA)
    s[pos] = 'U'; s[pos+1] = 'A'; s[pos+2] = 'A';
}

void make_case(int id) {
    int N;
    string S;

    switch(id) {
        case 1: // 修正后的样例
            N = 13; S = "CAUGUUUUUUUAG";
            break;
        case 2: // 无解
            N = 50; S = rand_rna(N);
            // 概率上很难随机出完整的 ORF，或者很短
            break;
        case 3: // 只有AUG没有Stop
            N = 100; S = rand_rna(N);
            inject_gene(S, 10);
            // 把最后的Stop破坏掉
            for(int i=0; i<N-2; ++i) {
                if(is_stop(S.substr(i,3))) S[i] = 'C'; 
            }
            break;
        case 4: // 只有Stop没有AUG
            N = 100; S = rand_rna(N);
            for(int i=0; i<N-2; ++i) {
                if(S.substr(i,3) == "AUG") S[i] = 'C';
            }
            break;
        case 5: // 简单的短基因
            N = 100; S = rand_rna(N);
            inject_gene(S, 5);
            break;
        case 6: // 中等长度
            N = 1000; S = rand_rna(N);
            inject_gene(S, 50);
            break;
        case 7: // 两个基因，后面的更长
            N = 2000; S = rand_rna(N);
            inject_gene(S, 10); // 前面短
            // 后面长，稍微偏移一点位置
            {
                string temp = rand_rna(N);
                inject_gene(temp, 100);
                // 简单的合并策略：取temp的后半段覆盖S
                for(int i=N/2; i<N; ++i) S[i] = temp[i];
            }
            break;
        case 8: // 不同Frame重叠 (干扰测试)
            N = 1000; S = rand_rna(N);
            // 这里随机生成即可，依靠算法去解
            inject_gene(S, 20);
            break;
        case 9: // 大数据 N=10^5
            N = 100000; S = rand_rna(N);
            inject_gene(S, 500);
            break;
        case 10: // 极限数据 N=10^6
            N = 1000000; S = rand_rna(N);
            inject_gene(S, 10000); // 埋一个超长的
            break;
    }

    string in_file = to_string(id) + ".in";
    ofstream fout_in(in_file);
    fout_in << N << "\n" << S << "\n";
    fout_in.close();

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

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

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