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

/**
 * 题目：小麦的株高 (Height of Wheat)
 * 算法：桶计数 + 前缀和 (Bucket Count + Prefix Sum)
 * 难度：GESP 5级 / CSP-J T2
 */

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

using namespace std;

// 最大可能的显性基因数量：2 * K <= 100
// 开稍微大一点，防止溢出
const int MAX_VAL = 205;

// cnt[x] 存储显性基因数量恰好为 x 的小麦有多少株
int cnt[MAX_VAL];
// sum[x] 存储显性基因数量在 [0, x] 范围内的小麦总数
int sum[MAX_VAL];

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

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

    // 2. 读取 N 株小麦并进行统计
    for (int i = 0; i < N; ++i) {
        string s;
        cin >> s;
        
        // 计算当前字符串中大写字母的个数
        int dominant_count = 0;
        for (char c : s) {
            if (c >= 'A' && c <= 'Z') {
                dominant_count++;
            }
        }
        
        // 放入对应的桶中
        cnt[dominant_count]++;
    }

    // 3. 构建前缀和数组
    // 显性基因数量范围是 0 到 2*K
    int max_score = 2 * K;
    
    // 初始化 sum[0]
    sum[0] = cnt[0];
    
    // 递推计算 sum
    for (int i = 1; i <= max_score; ++i) {
        sum[i] = sum[i-1] + cnt[i];
    }

    // 4. 处理 M 次查询
    for (int i = 0; i < M; ++i) {
        int L, R;
        cin >> L >> R;
        
        // 边界保护：虽然题目保证 L, R 合法，但在实战中为了健壮性可以处理一下
        if (L > max_score) L = max_score + 1;
        if (R > max_score) R = max_score;
        
        // 如果区间不合法
        if (L > R) {
            cout << 0 << "\n";
            continue;
        }

        // 区间和公式：sum[R] - sum[L-1]
        int ans = 0;
        if (L == 0) {
            ans = sum[R];
        } else {
            ans = sum[R] - sum[L-1];
        }
        
        cout << ans << "\n";
    }

    return 0;
}

时间与空间复杂度分析

• 时间复杂度：
  • 预处理：遍历所有字符，约 $N \times 2K$。
  • 前缀和计算：约 $2K$。
  • 查询：$M \times O(1)$。
  • 总时间：$O(NK + M)$。代入数据 $10^5 \times 100 + 10^5 \approx 10^7$，非常稳。
• 空间复杂度：
  • 只需要两个大小为 200 的数组 cnt 和 sum。
  • $O(K)$。极小空间占用。

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

/**
 * 题目：小麦的株高
 * 数据生成器
 */

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

using namespace std;

mt19937 rng(time(0));

// 生成随机基因型
string generate_gene(int k) {
    string s = "";
    for(int i=0; i<k; ++i) {
        // 随机选择 Aa, AA, aa
        int type = rng() % 3;
        if (type == 0) { s += "Aa"; } // 1个显性
        else if (type == 1) { s += "AA"; } // 2个显性
        else { s += "aa"; } // 0个显性
    }
    return s;
}

// 核心解法
int solve_query(int L, int R, const vector<int>& counts) {
    int ans = 0;
    for (int val : counts) {
        if (val >= L && val <= R) ans++;
    }
    return ans;
}

void make_case(int id) {
    int N, M, K;
    
    // 定制数据规模
    switch(id) {
        case 1: N = 5; M = 3; K = 3; break; // 样例规模
        case 2: N = 10; M = 10; K = 1; break; // 极简，K=1
        case 3: N = 100; M = 100; K = 50; break; // K最大
        case 4: N = 1000; M = 1000; K = 5; break; // N,M中等
        case 5: N = 1000; M = 1000; K = 10; break;
        case 6: N = 10000; M = 10000; K = 20; break;
        case 7: N = 50000; M = 50000; K = 50; break;
        case 8: N = 100000; M = 100000; K = 5; break; // N,M最大，K小
        case 9: N = 100000; M = 100000; K = 25; break;
        case 10: N = 100000; M = 100000; K = 50; break; // 满级数据
    }

    vector<string> genes;
    vector<int> counts;
    for(int i=0; i<N; ++i) {
        string s = generate_gene(K);
        genes.push_back(s);
        int c = 0;
        for(char x : s) if(x>='A' && x<='Z') c++;
        counts.push_back(c);
    }

    // 写入 .in
    string in_file = to_string(id) + ".in";
    ofstream fout_in(in_file);
    fout_in << N << " " << M << " " << K << "\n";
    for(const string& s : genes) fout_in << s << "\n";
    
    // 生成查询并写入，同时计算答案写入 .out
    string out_file = to_string(id) + ".out";
    ofstream fout_out(out_file);
    
    for(int i=0; i<M; ++i) {
        int max_val = 2 * K;
        int L = rng() % (max_val + 1);
        int R = rng() % (max_val + 1);
        if(L > R) swap(L, R);
        
        fout_in << L << " " << R << "\n";
        fout_out << solve_query(L, R, counts) << "\n";
    }
    
    fout_in.close();
    fout_out.close();
    
    cout << "Generated Case " << id << endl;
}

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

这道题以多基因遗传的累加效应为背景，实际上考察了算法中非常重要的优化思想——预处理（桶+前缀和）。希望对你的教学有帮助！