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

_miss_ · 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;
}