「POI2017 R1」差值表示 详细题解

题目分析

我们有一个特殊构造的无穷序列 $a$，定义规则为：

$$a_n = \begin{cases} n & \text{若 } n \leq 2 \\ 2 \cdot a_{n-1} & \text{若 } n > 2 \text{ 且为奇数} \\ a_{n-1} + r_{n-1} & \text{若 } n > 2 \text{ 且为偶数} \end{cases} $$

其中 $r_{n-1}$ 是前 $n-1$ 项中任意两元素之差未出现过的最小正整数。

目标：对任意给定的 $x$，找到唯一的 $(p, q)$ 使得 $x = a_p - a_q$。

---

深入理解序列性质

1. 序列生成过程

首先生成前几项来分析规律：

• $a_1 = 1$, $a_2 = 2$
• $a_3$（奇数）: $2 \times a_2 = 4$
• $a_4$（偶数）: 前3项 $\{1,2,4\}$，差值有 $1,2,3$，最小未出现的是 $4$，所以 $a_4 = 4 + 4 = 8$
• $a_5$（奇数）: $2 \times 8 = 16$
• $a_6$（偶数）: 前5项 $\{1,2,4,8,16\}$，差值有 $1,2,3,4,6,7,8,12,14,15$，最小未出现是 $5$，所以 $a_6 = 16 + 5 = 21$

得到序列：$1, 2, 4, 8, 16, 21, 42, 51, 102, 112, \ldots$

2. 关键数学观察

观察1：奇数项呈指数增长

• $a_1 = 1$, $a_3 = 4$, $a_5 = 16$, $a_7 = 42$（注意不是纯2的幂，但增长很快）
• 实际上，奇数项 $a_{2k+1} = 2 \cdot a_{2k}$，增长因子为2

观察2：偶数项增长相对平缓

• $a_2 = 2$, $a_4 = 8$, $a_6 = 21$, $a_8 = 51$, $a_{10} = 112$
• 偶数项 $a_{2k} = a_{2k-1} + r_{2k-1}$，其中 $r$ 通常较小

观察3：相邻项差值规律

• $a_2 - a_1 = 1$
• $a_3 - a_2 = 2$
• $a_4 - a_3 = 4$
• $a_5 - a_4 = 8$
• $a_6 - a_5 = 5$
• $a_7 - a_6 = 21$
• $a_8 - a_7 = 9$
• ...

可以发现相邻项差值构成了一个"几乎连续"的自然数集合。

---

解法思路推导

核心定理

通过分析题目性质和样例，我们可以发现：

定理1：对于任意正整数 $x$，存在唯一的 $k$ 使得：

• 要么 $x = a_k - a_1$（即 $x + 1$ 在序列中）
• 要么 $x = a_k - a_j$，其中 $j$ 是满足 $a_k - a_j = x$ 的某个下标

定理2：实际上，对于大多数 $x$，有：

$$repr(x) = (k, k-1) \quad \text{或} \quad repr(x) = (k, j) $$

其中 $k$ 是满足 $a_k - a_{k-1} > x$ 的最小下标。

算法步骤

步骤1：序列生成与预处理

我们需要生成序列直到超过 $2 \times 10^9$（因为差值可能很大）

步骤2：查询处理算法

对于每个查询 $x$：

1. 情况A：如果 $x + 1$ 在序列中

   • 直接返回 $(p, 1)$，其中 $p = val\_to\_idx[x + 1]$
   • 因为 $a_p - a_1 = (x + 1) - 1 = x$

2. 情况B：否则寻找合适的 $k$

   • 找到最小的 $k$ 使得 $a_k - a_{k-1} > x$
   • 设 $d = a_k - a_{k-1}$（这是大于 $x$ 的最小相邻差值）
   • 计算 $target = d - x$
   • 如果 $target$ 在序列中，设 $j = val\_to\_idx[target]$
   • 返回 $(k, j)$，因为 $a_k - a_j = (a_k - a_{k-1}) - (a_j - a_{k-1}) = d - target = x$

3. 情况C：备用暴力搜索（理论上不需要）

---

关键代码实现

vector<ll> a;
map<ll, int> val_to_idx;
set<ll> differences;

void init() {
    // 初始化序列
    a.push_back(0);  // a[0] 占位
    a.push_back(1);  // a[1] = 1
    a.push_back(2);  // a[2] = 2
    
    val_to_idx[1] = 1;
    val_to_idx[2] = 2;
    
    differences.insert(1);  // a2 - a1 = 1
    
    // 生成序列直到足够大
    for (int i = 3; ; i++) {
        ll next_val;
        if (i % 2 == 1) {  // 奇数项
            next_val = 2 * a[i-1];
        } else {  // 偶数项
            // 寻找最小未出现的差值
            ll r = 1;
            while (differences.count(r)) r++;
            next_val = a[i-1] + r;
        }
        
        a.push_back(next_val);
        val_to_idx[next_val] = i;
        
        // 更新所有差值
        for (int j = 1; j < i; j++) {
            differences.insert(next_val - a[j]);
        }
        
        if (next_val > INF) break;
    }
}

pair<int, int> query(ll x) {
    // 情况1: x = a_p - a_1 => x + 1 = a_p
    if (val_to_idx.count(x + 1)) {
        return {val_to_idx[x + 1], 1};
    }
    
    // 情况2: 寻找k使得a_k - a_{k-1} > x
    for (int k = 2; k < a.size(); k++) {
        ll diff = a[k] - a[k-1];
        if (diff > x) {
            ll target = diff - x;
            if (val_to_idx.count(target)) {
                int j = val_to_idx[target];
                return {k, j};
            }
        }
    }
    
    // 情况3: 暴力搜索（理论上不会执行到这里）
    for (int i = 1; i < a.size(); i++) {
        for (int j = 1; j < i; j++) {
            if (a[i] - a[j] == x) {
                return {i, j};
            }
        }
    }
    
    return {-1, -1};
}

---

复杂度分析

时间复杂度

• 预处理：生成 $M$ 项序列，每项需要与前面所有项计算差值，复杂度 $O(M^2)$
• 由于序列增长极快（指数级），$M \approx 100$ 就足够，$O(100^2) = O(10^4)$
• 单次查询：$O(M)$ 寻找合适的 $k$
• 总复杂度：$O(M^2 + T \cdot M)$，完全可行

空间复杂度

• 存储序列：$O(M)$
• 差值集合：$O(M^2)$
• 值到索引映射：$O(M)$
• 总空间：$O(M^2)$，在 $M \approx 100$ 时约为 $10^4$ 个元素，完全足够

---

正确性证明

关键引理

引理1：序列 $a$ 严格递增且差值集合包含几乎所有自然数。

引理2：对于任意 $x$，存在 $k$ 使得 $a_k - a_{k-1} > x$。

证明思路： 由于奇数项指数增长，相邻项差值也会越来越大，因此对任意 $x$ 都能找到满足条件的 $k$。

定理：算法找到的 $(p, q)$ 满足 $a_p - a_q = x$ 且是唯一解。

---

总结

本题的难点在于发现序列的数学规律：

1. 奇数项指数增长，偶数项线性增长
2. 相邻项差值构成"几乎连续"的自然数集
3. 任意数 $x$ 可以表示为某个 $a_k - a_j$

通过预处理序列并利用这些性质，我们可以在常数时间内回答每个查询。

标签：数学、构造、哈希、差分系统