自动搬运

查看原文

来自洛谷，原作者为

	lam_dyr 少年曾许凌云志，誓做天下第一流

搬运于2025-08-24 21:17:07，当前版本为作者最后更新于2024-12-27 08:03:11，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

B4102 [CSP-X2023 山东] 克隆机

Solution

题目理解

有一个克隆过程，初始时有 $k$ 种种子，每种 $1$ 粒，按字母顺序排列。每次从队头取出一粒种子进行克隆，克隆后的两粒种子放到队尾。目标是找出第 $n$ 粒被克隆的种子是什么。

核心思路

初始情况： 如果 $n \le k$，那么第 $n$ 粒被克隆的种子就是第 $n$ 个字母，可以直接输出。

模拟过程： 如果 $n > k$，就需要模拟克隆过程。但如果直接模拟，当 $n$ 很大时会超时。因此，需要寻找规律。

规律发现： 假设当前队列长度为 $len$，在进行一轮克隆后，队列长度会变为 $len + k$。

每一轮克隆，都会把前 $k$ 个种子克隆一次，并且把这 $k$ 个种子放到队尾。

关键在于，第 $n$ 个被克隆的种子，实际上是第 $n$ 个被取出的种子。

当 $n > k$ 时，我们实际上可以倒推：

• 如果 $n$ 是在第一轮克隆中被取出的，那么 $n$ 肯定是在前 $k$ 个位置。
• 如果 $n$ 不是在第一轮克隆中被取出的，那么它一定是在第一轮克隆后新加入的队列中。
• 假设第一轮克隆后，队列长度变为 $2k$，那么第一轮克隆后，新加入的队列的前 $k$ 个元素，就是第一轮克隆的种子，也就是前 $k$ 个种子。
• 那么，第 $n$ 个被克隆的种子，实际上是第 $(n - k - 1) \div 2$ 个被克隆的种子，因为前 $k$ 个种子被克隆了，并且放到了队尾，所以第 $n$ 个被克隆的种子，实际上是第 $(n-k)$ 个种子，而这 $(n-k)$ 个种子，实际上是前 $(n-k)\div2$ 个种子被克隆出来的。

也就是说，我们可以把 $n$ 减去 $k$，然后除以 $2$，得到新的 $n$，直到 $n$ 小于等于 $k$。

具体实现：可以使用递归或迭代的方式倒推，直到 $n \le k$。

Code

#include <iostream>
using namespace std;
long long k, n;
int main() {
	cin >> k >> n;
	if (n <= k) 
		cout << char('A' + n - 1);
	else {
		n--;
		while (n >= k) 
			n = (n - k) / 2;
		cout << char('A' + n);
	}
	return 0;
}