{"problem":{"name":"「HOI R1」杂交选种","description":{"content":"#### 【形式化题意】 **这是一道交互题。** 定义 **基因** 为一个字符，其内容为 $\\verb!A!$ 或 $\\verb!a!$。定义 **基因型** 为由两个基因组成，且大写字母在小写字母之前的字符串。也即 $\\{\\verb!aa!,\\verb!Aa!,\\verb!AA!\\}$ 中的一种。一个基因型的 **表现** 如下： - 若基因型中含有 $\\verb!A!$，则表现为 $","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10384"},"statements":[{"statement_type":"Markdown","content":"#### 【形式化题意】\n\n**这是一道交互题。**\n\n定义 **基因** 为一个字符，其内容为 $\\verb!A!$ 或 $\\verb!a!$。定义 **基因型** 为由两个基因组成，且大写字母在小写字母之前的字符串。也即 $\\{\\verb!aa!,\\verb!Aa!,\\verb!AA!\\}$ 中的一种。一个基因型的 **表现** 如下：\n\n- 若基因型中含有 $\\verb!A!$，则表现为 $\\verb!A!$。\n- 否则，表现为 $\\verb!a!$。\n\n两个基因型可以相互 **杂交**，其定义如下：\n\n- 在两个基因型中各均匀随机取一个基因，并将两个基因组合成基因型作为结果输出。\n\n小 $\\iiint$ 有 $n$ 个基因型，编号为 $1,2,\\cdots,n$。每次询问可以给交互库两个不同的编号 $i,j$。若当前是第 $k$ 次杂交，交互库会新建一个编号为 $n+k$ 的基因型，其基因型为 $i,j$ 杂交后的结果。\n\n你可以在时限范围内任意次查询编号为 $x$ 的种子的表现。你需要在 $4.5\\times10^5$ 次杂交内，求出初始给定的 $n$ 个基因型。\n\n### 实现细节\n\n**你不需要，也不应该实现主函数。** 你需要实现下面的函数：\n\n```cpp\nvector<string> guess(int n)\n```\n\n- $n$ 表示初始基因型个数。\n- 该函数应当返回一个长度恰好为 $n$ 的数组，数组中的每一个元素是一个长度为二的字符串，表示你所求出的基因型。**你需要保证大写字母在小写字母的前面**。\n- 对于每个测试点，该函数被恰好调用一次。\n\n该函数可调用以下函数：\n\n```cpp\nchar query(int k)\n```\n\n- $k$ 表示你要查询的基因型的编号。**你需要保证这个编号对应的基因型存在**。\n- 该函数将返回该基因型的表现。\n- 该函数可以在时限内被调用任意次。\n\n```cpp\nvoid cross(int i, int j)\n```\n\n- $i,j$ 代表你要杂交的两个基因的编号。**你需要保证 $i\\not=j$ 且对应的基因型存在**。\n- 若是第 $k$ 次调用该函数，该函数会新建一个编号为 $n+k$ 的基因型，其基因型为 $i,j$ 杂交后的结果。保证杂交过程为均匀随机。\n- 你最多可以调用该函数 $4.5\\times10^5$ 次。\n- 评测程序不是适应性的。也就是说，所有初始元素的基因型在 `guess` 函数被调用前已经确定。\n\n## Background\n\n$\\clubsuit$ 星球盛产“代马”，其优越的速度与耗能使得它风靡整个银河系。可小 $\\iiint$ 并不满足于此，他想培育出更好的“代马”，并取代掉还在用传统能源的落后四足兽。于是，他开始研究基因技术……\n\n**本题仅支持 C++ 语言提交。**\n\n**由于技术限制，请勿使用 C++14 (GCC 9) 语言提交，否则将会得到 Compile Error 的结果。**\n\n你的代码中需如下进行 `query` 和 `cross` 函数的声明：\n\n```cpp\nchar query(int k);\nvoid cross(int i, int j);\n```\n\n调用 $10^6$ 次 `query` 与 `cross` 函数的时间不超过 50 毫秒，除这两个函数所占用的时间外，交互库运行所占用的时间不超过 100 毫秒。\n\n[samples]\n\n## Note\n\n#### 【交互示例】\n\n以下为 $n=2$，基因型为 $\\{\\verb!Aa!,\\verb!AA!\\}$ 时一种可能的交互过程。\n\n|选手程序|交互库|\n|:-:|:-:|\n||`guess(2)`|\n|`cross(1,2)`||\n||$\\{\\verb!Aa!,\\verb!AA!,\\verb!Aa!\\}$|\n|`cross(1,3)`||\n||$\\{\\verb!Aa!,\\verb!AA!,\\verb!Aa!,\\verb!aa!\\}$|\n|`query(4)`||\n||$\\verb!a!$|\n|$\\{\\verb!Aa!,\\verb!AA!\\}$||\n||`Ok,accepted.`|\n\n#### 【约束条件】\n\n+ $2\\le n\\le 2\\times10^4$，$n$ 为偶数。\n+ 每次程序运行时将恰好调用一次 `guess()` 函数。\n+ 保证交互库是非自适应性的，即所有初始元素的基因型不在交互过程中发生改变。\n\n#### 【子任务】\n\n|Subtask|分值|$n\\le$|特殊性质|\n|:-:|:-:|:-:|:-:|\n|$0$|$0$|$2$|无|\n|$1$|$5$|$2\\times10^4$|保证不存在 $\\verb!Aa!$|\n|$2$|$15$|$500$|无|\n|$3$|$20$|$2\\times10^4$|保证至少存在一个 $\\verb!aa!$|\n|$4$|$25$|$5\\times10^3$|无|\n|$5$|$35$|$2\\times10^4$|无|\n\n对于所有数据，$2\\le n\\le 2\\times10^4$，保证 $n$ 为偶数。\n\n由于本题涉及概率与期望，如果你确定你的算法无误，可以尝试多交几发。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10384","tags":["2024","交互题","Special Judge","概率论","洛谷比赛"],"sample_group":[],"created_at":"2026-03-03 11:09:25"}}