自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 22:57:27，当前版本为作者最后更新于2024-04-29 20:48:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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：稍微思考了一下，好像把第一匹马和其他马分开考虑是没有必要的。懒得改代码了。