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

/**
 * 题目：成熟的信使 (The Mature Messenger)
 * 算法：标记法 / 线性扫描 (Flagging / Linear Scan)
 * 难度：GESP 5级 / CSP-J T2
 */

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

using namespace std;

// 全局变量定义在堆区，防止栈溢出（当N很大时）
// 1000005 略大于 10^6，防止越界
bool is_intron[1000005]; 

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

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

    string S;
    cin >> S;

    // 2. 处理内含子区间标记
    // 虽然题目说区间不重叠，但即使重叠，标记法也是正确的
    for (int i = 0; i < K; ++i) {
        int l, r;
        cin >> l >> r;
        // 题目下标从1开始，转换为0开始的下标方便字符串操作
        // 区间是 [l, r]，对应下标 [l-1, r-1]
        for (int j = l - 1; j <= r - 1; ++j) {
            is_intron[j] = true;
        }
    }

    // 3. 线性扫描输出
    // 准备一个 string buffer 或者直接输出均可
    // 直接输出可以省去拼接字符串的内存开销
    for (int i = 0; i < N; ++i) {
        // 如果不是内含子（即外显子，需要保留）
        if (!is_intron[i]) {
            if (S[i] == 'T') {
                cout << 'U';
            } else {
                cout << S[i];
            }
        }
    }
    cout << endl;

    return 0;
}

时间复杂度分析

• 标记过程：我们需要遍历所有的内含子区间。虽然看起来是两层循环，但注意到题目保证区间不重叠。所以每个位置最多被标记一次。总操作次数不超过 $N$。复杂度 $O(N)$。
• 输出过程：遍历整个字符串一次，复杂度 $O(N)$。
• 总复杂度：$O(N)$。对于 $N=10^6$，完全可以在 1秒内完成。

空间复杂度分析

• 需要一个长度为 $N$ 的 bool 数组，约占 1MB 内存。
• 需要存储字符串 $S$，约占 1MB 内存。
• 总空间：$O(N)$，非常安全。

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

这是一个用来生成 OJ 测试数据的程序。它会生成 10 组数据，覆盖了各种边界情况。

/**
 * 题目：成熟的信使 (The Mature Messenger)
 * 数据生成器
 */

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

using namespace std;

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

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

// 核心解法 (用于生成 .out)
string solve(int N, int K, string S, const vector<pair<int,int>>& intervals) {
    vector<bool> remove(N, false);
    for(auto p : intervals) {
        for(int j = p.first - 1; j <= p.second - 1; ++j) {
            remove[j] = true;
        }
    }
    string res = "";
    for(int i=0; i<N; ++i) {
        if(!remove[i]) {
            if(S[i] == 'T') res += 'U';
            else res += S[i];
        }
    }
    return res;
}

void make_case(int id) {
    int N, K;
    string S;
    vector<pair<int,int>> intervals;

    // 根据测试点定制
    switch(id) {
        case 1: // 样例
            N = 15; K = 2; S = "ATGCGTATCCGTACT";
            intervals = {{2,4}, {10,12}};
            break;
        case 2: // 无内含子
            N = 100; K = 0; S = generate_dna(N);
            break;
        case 3: // 只有1个内含子
            N = 1000; K = 1; S = generate_dna(N);
            intervals.push_back({10, 500});
            break;
        case 4: // 全部被切掉
            N = 100; K = 1; S = generate_dna(N);
            intervals.push_back({1, 100});
            break;
        case 5: // 许多小片段，稀疏
            N = 10000; K = 100; S = generate_dna(N);
            {
                int current = 1;
                while(current < N && intervals.size() < K) {
                    if(current + 10 < N) {
                        intervals.push_back({current, current+5});
                        current += 100; // 间隔开
                    } else break;
                }
                K = intervals.size();
            }
            break;
        case 6: // 密集切割
            N = 10000; K = 2000; S = generate_dna(N);
            {
                int current = 1;
                while(current < N - 5) {
                    intervals.push_back({current, current+2});
                    current += 4; 
                }
                K = intervals.size();
            }
            break;
        case 7: // T替换测试 (全T)
            N = 1000; K = 0; 
            S = string(N, 'T');
            break;
        case 8: // 大数据 N=10^5
            N = 100000; K = 1000; S = generate_dna(N);
            {
                int cur = 1;
                for(int i=0; i<K; ++i) {
                    if(cur + 50 < N) {
                        intervals.push_back({cur, cur+20});
                        cur += 80;
                    }
                }
                K = intervals.size();
            }
            break;
        case 9: // 大数据 N=10^6
            N = 1000000; K = 5000; S = generate_dna(N);
            {
                int cur = 1;
                for(int i=0; i<K; ++i) {
                    if(cur + 100 < N) {
                        intervals.push_back({cur, cur+50});
                        cur += 150;
                    }
                }
                K = intervals.size();
            }
            break;
        case 10: // 大数据 N=10^6，只有首尾保留
            N = 1000000; K = 1; S = generate_dna(N);
            intervals.push_back({2, N-1});
            break;
    }

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

    // 写入 .out
    string out_file = to_string(id) + ".out";
    ofstream fout_out(out_file);
    fout_out << solve(N, K, S, intervals) << "\n";
    fout_out.close();
    
    cout << "Generated Case " << id << endl;
}

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