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

CPP

#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;
}

题解：B4102 [CSP-X2023 山东] 克隆机

文章操作