题解：P10384 「HOI R1」杂交选种

· · 题解

Solution

这道题有点水啊，我没有做任何分析随便写了一个过程交上去 \rm Accepted 了。

在高中生物学中，隐性个体必然为纯合子，因此如果有某匹马的表型为 \texttt a 那么一定为隐性纯合子。

对于显性个体是纯合子还是杂合子，最好的判断方法是测交。将个体与 \texttt {aa} 进行杂交，如果个体的基因型为 \text {Aa}，则每次都有 \dfrac{1}{2} 的概率产生隐性个体。差不多 22 次之后误判的概率低至 2^{-22} < 10^{-6}，可以忽略不计。

因此，首先特判有个体的表型是隐性性状的情况。

vector<string> check(int flg) { 
    ffor(i,1,n) if(i!=flg&&op[i]==1) {
        ffor(k,1,22) {
            ++cnt,cross(flg,i);
            if(query(cnt)=='a') {gene[i]=1;break;}
        }
        if(gene[i]!=1) gene[i]=2;
    }
    vector<string> ans;
    ffor(i,1,n) if(gene[i]==0) ans.push_back("aa");
    else if(gene[i]==1) ans.push_back("Aa");
    else ans.push_back("AA");
    return ans;
}

如果所有个体都是显性性状，那么它不是 \texttt{AA} 就是 \texttt{Aa}。考虑先用 100 次操作确定第一匹马是不是杂合子。

我们将采取这样的流程：对于个体 \mathcal X，先让它和个体 \mathcal Y 杂交，产生子一代个体 \mathcal Z。每次让 \mathcal X \times \mathcal Z（注意到马没有伦理道德，这样是合法的），得到新的子代 \mathcal Z'，并且 \mathcal Z \leftarrow \mathcal Z'。打表得知，如果 \mathcal X 是杂合子，那么在进行 100 次交配之后只有 5 \times 10^{-13} 的概率无法判断出来，远小于古今中外所有人中选一个选中你的概率。

生物学的基本知识：如果两个显性个体杂交得到隐性个体，这两个显性个体都是杂合子。

在对第 2 匹到第 n 匹马判断的过程中，如果我们之前产生了一只隐性个体，直接测交；否则，之前所有马都是纯合子，随便拉一匹出来进行杂交，并且执行上述流程即可。

（执行 22 次该流程的错误率是 3 \%\%，但是注意到一旦成功就会产生隐性个体，所以总的错误率还是 3 \%\%）。

交了四五发，没有一发 \rm Wrong \ Answer。这就是二十一世纪科学的魅力 /se

代码：

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=5e5+10;
int cnt,flg,n,op[MAXN],gene[MAXN];
char query(int k);
void cross(int i,int j);
vector<string> check(int flg) { 
    ffor(i,1,n) if(i!=flg&&op[i]==1) {
        ffor(k,1,22) {
            ++cnt,cross(flg,i);
            if(query(cnt)=='a') gene[i]=1;
        }
        if(gene[i]!=1) gene[i]=2;
    }
    vector<string> ans;
    ffor(i,1,n) if(gene[i]==0) ans.push_back("aa");
    else if(gene[i]==1) ans.push_back("Aa");
    else ans.push_back("AA");
    return ans;
}
vector<string> guess(int N) {
    n=N,cnt=n;  
    ffor(i,1,n) op[i]=(query(i)=='A');
    ffor(i,1,n) if(op[i]==0) flg=i;
    if(flg) return check(flg);
    cross(1,2),++cnt;
    if(query(cnt)=='a') return check(cnt);
    ffor(i,1,99) {
        cross(1,n+i),++cnt;
        if(query(cnt)=='a') return check(cnt);
    }
    //这时候一号是 AA
    vector<string> ans;
    ans.push_back("AA");
    int aid=0;
    ffor(i,2,n) {
        int flg=0;
        if(aid==0) {
            cross(1,i),++cnt;
            if(query(cnt)=='a') aid=cnt,flg=1;
            ffor(j,1,21) {
                cross(i,cnt),++cnt;
                if(query(cnt)=='a') {aid=cnt,flg=1;break;}
            }
            if(flg==0) ans.push_back("AA");
            else ans.push_back("Aa");
        }
        else {
            ffor(j,1,22) {
                cross(aid,i),++cnt;
                if(query(cnt)=='a') {flg=1;break ;}
            }
            if(flg==0) ans.push_back("AA");
            else ans.push_back("Aa");
        }
    }
  return ans;
}

PS：稍微思考了一下，好像把第一匹马和其他马分开考虑是没有必要的。懒得改代码了。