数据生成器 (Generator)

此生成器已修正，Case 1 将严格按照题目描述中的样例输入生成，确保测试无误。

请保存为 gen_gamete_fixed.cpp 并运行。

/**
 * Project: Mendel's Gamete Code (Fixed Generator)
 * Author: Isaac Asimov (AI)
 * Fix: Sample 1 input hardcoded to match the problem description.
 */

#include <iostream>
#include <fstream>
#include <random>
#include <string>
#include <vector>
#include <cmath>
#include <cctype>

using namespace std;

// ==========================================
// Part 1: 标准解答逻辑
// ==========================================
class Solution {
public:
    void solve(string in_file, string out_file) {
        ifstream cin(in_file);
        ofstream cout(out_file);
        if (!cin.is_open()) return;

        int n, m; cin >> n >> m;
        string s; cin >> s;

        int must_one = 0;
        int must_zero = 0;
        int hetero_cnt = 0;

        for (int i = 0; i < n; i++) {
            int bit_pos = n - 1 - i;
            char g1 = s[2*i];
            char g2 = s[2*i+1];
            if (isupper(g1) && isupper(g2)) must_one |= (1 << bit_pos);
            else if (islower(g1) && islower(g2)) must_zero |= (1 << bit_pos);
            else hetero_cnt++;
        }

        cout << (1LL << hetero_cnt) << endl;

        for(int i=0; i<m; i++){
            int x; cin >> x;
            bool c1 = (x & must_one) == must_one;
            bool c2 = (x & must_zero) == 0;
            if(c1 && c2) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
        
        cin.close();
        cout.close();
        cout << "Generated: " << out_file << endl;
    }
};

// ==========================================
// Part 2: 数据生成逻辑
// ==========================================
mt19937 rng(2025);

int rand_int(int min, int max) {
    uniform_int_distribution<int> dist(min, max);
    return dist(rng);
}

string get_gene(int type, char base) {
    string res = "";
    if (type == 0) { res += tolower(base); res += tolower(base); } // aa
    else if (type == 2) { res += toupper(base); res += toupper(base); } // AA
    else { res += toupper(base); res += tolower(base); } // Aa
    return res;
}

void generate_input(int case_id) {
    string filename = to_string(case_id) + ".in";
    ofstream fout(filename);

    // 1. 强制样例复现
    if (case_id == 1) {
        fout << "3 4" << endl;
        fout << "AaBBcc" << endl;
        fout << "6" << endl;
        fout << "2" << endl;
        fout << "4" << endl;
        fout << "7" << endl;
        fout.close();
        return;
    }

    int n, m;
    
    // 规模控制
    if (case_id <= 5) { n = 10; m = 20; }
    else { n = 20; m = 1000; } 

    // 生成基因型
    string s = "";
    vector<int> gene_types(n); 

    for (int i = 0; i < n; i++) {
        char base = 'A' + (i % 26);
        int type = rand_int(0, 2); // 0:aa, 1:Aa, 2:AA
        // 注意：第 i 对基因（从左到右），对应的是高位 (n-1-i)
        // 但我们在生成 query 时，只要知道第 k 位是啥类型就行
        // 所以我们存入 gene_types 时，存入它在二进制中的位权下标
        gene_types[n - 1 - i] = type; 
        s += get_gene(type, base);
    }

    fout << n << " " << m << endl;
    fout << s << endl;

    // 生成 Query
    for (int i = 0; i < m; i++) {
        int x = 0;
        // 0: 合法, 1: 违反AA, 2: 违反aa
        int type = rand_int(0, 2); 

        for (int bit = 0; bit < n; bit++) {
            int current_bit = 0;
            
            if (type == 0) { // 生成合法的
                if (gene_types[bit] == 0) current_bit = 0; // aa -> 0
                else if (gene_types[bit] == 2) current_bit = 1; // AA -> 1
                else current_bit = rand_int(0, 1); // Aa -> 0/1
            }
            else if (type == 1) { // 尝试违反显性
                if (gene_types[bit] == 2) {
                    // 本该是1，可能随机变0
                    if (rand_int(0, 1)) current_bit = 0; else current_bit = 1;
                } else {
                    if (gene_types[bit] == 0) current_bit = 0;
                    else current_bit = rand_int(0, 1);
                }
            }
            else { // 尝试违反隐性
                if (gene_types[bit] == 0) {
                    // 本该是0，可能随机变1
                    if (rand_int(0, 1)) current_bit = 1; else current_bit = 0;
                } else {
                    if (gene_types[bit] == 2) current_bit = 1;
                    else current_bit = rand_int(0, 1);
                }
            }
            
            if (current_bit) x |= (1 << bit);
        }
        fout << x << endl;
    }

    fout.close();
}

int main() {
    ios_base::sync_with_stdio(false);
    cout << "--- Generating Mendel Data (Fixed) ---" << endl;
    
    Solution solver;
    for (int i = 1; i <= 10; i++) {
        generate_input(i);
        string in = to_string(i) + ".in";
        string out = to_string(i) + ".out";
        solver.solve(in, out);
    }
    cout << "--- Done! ---" << endl;
    return 0;
}

阿西莫夫的解题指南

这道题考察了 位掩码（Bitmask） 的使用。如果 $N=30$，遍历所有可能的配子是不现实的，我们需要 $O(1)$ 的判断方法。

1. 预处理：构建掩码

我们需要两个特殊的二进制数来描述亲本的“硬性限制”：

• must_one (必须为1)：如果某对基因是显性纯合子（如 AA），那么配子对应的位必须是 1。
• must_zero (必须为0)：如果某对基因是隐性纯合子（如 aa），那么配子对应的位必须是 0。
• 对于杂合子（Aa），它既不强制为 1，也不强制为 0，给配子提供了自由度。

2. 验证逻辑

对于一个查询 $X$：

1. 检查显性限制：$X$ 中所有对应 AA 的位必须是 1。
   • 位运算：(X & must_one) == must_one
2. 检查隐性限制：$X$ 中所有对应 aa 的位必须是 0。
   • 位运算：(X & must_zero) == 0

只有同时满足这两个条件，输出 Yes。

3. 组合计数

亲本能产生的不同配子数量 = $2^k$，其中 $k$ 是杂合子（Aa 型）的对数。

C++ 标准解答 (NOIP C++14)

/**
 * 题目: 孟德尔的“配子”密码 (Mendel's Gamete Code)
 * 作者: Isaac Asimov (AI)
 * 知识点: 位运算 (Bitmask), 排列组合
 */

#include <iostream>
#include <string>
#include <cmath>
#include <cctype>

using namespace std;

int main() {
    // IO 优化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    string s;
    cin >> s;

    // 1. 预处理掩码和计数
    // must_one: 对应 AA 的位置，这些位必须是 1
    // must_zero: 对应 aa 的位置，这些位必须是 0
    int must_one = 0;
    int must_zero = 0;
    int hetero_count = 0; // 杂合子数量

    // 字符串 s 从左到右对应二进制的高位到低位 (N-1 到 0)
    for (int i = 0; i < n; i++) {
        // 当前处理的是第 (n - 1 - i) 位
        int bit_pos = n - 1 - i;
        
        char g1 = s[2 * i];
        char g2 = s[2 * i + 1];

        // 判断基因型
        if (isupper(g1) && isupper(g2)) {
            // 显性纯合子 (AA): 对应位必须为 1
            must_one |= (1 << bit_pos);
        }
        else if (islower(g1) && islower(g2)) {
            // 隐性纯合子 (aa): 对应位必须为 0
            must_zero |= (1 << bit_pos);
        }
        else {
            // 杂合子 (Aa): 自由组合
            hetero_count++;
        }
    }

    // 2. 输出配子总数: 2^k
    cout << (1LL << hetero_count) << endl;

    // 3. 处理询问
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;

        // 验证逻辑：
        // 1. 必须为1的位，X中必须是1 -> (x & must_one) == must_one
        // 2. 必须为0的位，X中必须是0 -> (x & must_zero) == 0
        //    或者用掩码思维: X 里的位不能出现在 must_zero 里 -> (x & must_zero) == 0
        
        bool cond1 = (x & must_one) == must_one;
        bool cond2 = (x & must_zero) == 0;

        if (cond1 && cond2) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }

    return 0;
}

阿西莫夫的点评

1. 位运算的魔力： 在 $N$ 较大的时候，如果用字符串或者数组来一位位比对，效率是线性的。而位运算的 & 操作是 CPU 指令级的并行，速度极快。这就像是生物学中的“基因芯片”，一次性检测成千上万个位点。
2. 组合数学： $2^k$ 这个公式看似简单，但它揭示了有性生殖产生巨大多样性的数学原理。如果人类有 23 对染色体，即使不考虑交换，仅自由组合就能产生 $2^{23}$ (800多万) 种配子。

希望这道题能让学生们在敲击键盘时，感受到生命遗传机制的精妙与数学的简洁。