题解：集合 $S$ 的第 $N$ 个元素

解题思路

题目要求我们生成一个集合 $S$，集合中的元素按照以下规则生成：

1. 初始元素是 $1$。
2. 如果 $x$ 在 $S$ 中，那么 $2x + 1$ 和 $3x + 1$ 也在 $S$ 中。
3. 集合 $S$ 中的元素按递增顺序排列，需要找到第 $N$ 个元素。

这个问题类似于生成一个有序序列，其中每个新元素都是由已有元素通过两种规则生成的。为了高效生成这个序列，可以采用类似“归并排序”的方法，动态维护两个指针，分别指向当前可以通过 $2x + 1$ 和 $3x + 1$ 生成最小候选值的位置。

分析

1. 序列生成规则：

   • 初始时，序列的第一个元素是 $1$。
   • 后续的每个元素都是通过已有元素的 $2x + 1$ 或 $3x + 1$ 生成的。
   • 为了保证序列有序，每次选择最小的候选值加入序列。

2. 动态维护候选值：

   • 用两个指针 $mul2$ 和 $mul3$ 分别指向当前可以通过 $2x + 1$ 和 $3x + 1$ 生成最小候选值的位置。
   • 每次比较 $d[mul2] \times 2 + 1$ 和 $d[mul3] \times 3 + 1$，选择较小的加入序列，并移动对应的指针。

3. 避免重复：

   • 如果两个候选值相等，需要同时移动两个指针，以避免重复元素。

4. 预计算：

   • 由于 $N$ 的最大值是 $10,000,000$，可以预先计算前 $10,000,000$ 个元素，然后直接查询。

实现步骤

1. 初始化：

   • 定义数组 $d$ 存储序列，初始时 $d[1] = 1$。
   • 初始化指针 $mul2 = 1$ 和 $mul3 = 1$。

2. 生成序列：

   • 从 $i = 2$ 开始遍历到 $i = 10,000,000$：
     • 计算候选值 $candidate2 = d[mul2] \times 2 + 1$ 和 $candidate3 = d[mul3] \times 3 + 1$。
     • 选择较小的候选值作为 $d[i]$。
     • 如果 $d[i] = candidate2$，则移动 $mul2$。
     • 如果 $d[i] = candidate3$，则移动 $mul3$。

3. 处理查询：

   • 对于每个输入的 $N$，直接输出 $d[N]$。

代码

#include <iostream>
#include <algorithm>

int d[10000005];  // 存储有序集合元素
int main() {
    d[1] = 1;      // 初始化第一个元素
    int mul2 = 1;   // 指向下一个可通过2x+1生成的元素位置
    int mul3 = 1;   // 指向下一个可通过3x+1生成的元素位置

    for (int i = 2; i <= 10000000; ++i) {
        // 计算两个候选值
        int candidate2 = d[mul2] * 2 + 1;
        int candidate3 = d[mul3] * 3 + 1;

        // 选择较小的作为当前元素
        d[i] = std::min(candidate2, candidate3);

        // 移动生成当前元素的指针
        if (d[i] == candidate3) ++mul3;
        if (d[i] == candidate2) ++mul2;
    }

    // 处理查询
    int n;
    while (std::cin >> n) {
        std::cout << d[n] << std::endl;
    }
    return 0;
}

复杂度分析

• 时间复杂度：
  • 预计算前 $10,000,000$ 个元素的时间复杂度是 $O(N)$，其中 $N = 10,000,000$。
  • 查询的时间复杂度是 $O(1)$。
• 空间复杂度：
  • 需要 $O(N)$ 的空间存储序列，其中 $N = 10,000,000$。

这种方法通过预计算和动态维护指针，高效地生成了有序序列，适用于大规模查询。