题解 | #讨厌鬼的数组构造#

题目描述

给定一个长度为 $n$ 的序列 $a$ ，请你构造一个序列 $b$ ，序列 $b$ 满足以下条件:

序列 $b$ 的长度为 $n$ 。
对于任意 $i \in [1, n]$ ，满足 $(a_i + b_i) \pmod i = 0$ 。
对于任意 $i \in [1, n]$ ，满足 $1 \le b_i \le 10^9$ 。
对于任意 $1 \le i < j \le n$ ，满足 $b_i \neq b_j$ （即 $b$ 中所有元素需互不相同）。

若有多个不同的答案, 输出任意一个即可。

解题思路

这是一个构造性问题。我们需要为序列 $a$ 中的每个元素 $a_i$ 找到一个对应的 $b_i$ ，满足一系列条件，其中最核心的是取模和唯一性约束。

1. 分析核心约束

条件 (a[i] + b[i]) mod i = 0 意味着 a[i] + b[i] 必须是 i 的一个倍数。换句话说，b[i] 必须满足 b[i] ≡ -a[i] (mod i)。

对于每一个 $i$ ，都存在一个最小的正整数 b[i] 满足这个同余关系。我们把这个最小的可能值称为基础值，记作 $b_{i, \text{base}}$ 。

令 rem = a[i] % i。
如果 rem == 0，则 $a_i$ 本身就是 $i$ 的倍数，那么 $b_i$ 也必须是 $i$ 的倍数。最小的正数 $b_i$ 就是 $i$ 。
如果 rem != 0，那么为了让 a[i] + b[i] 凑成 $i$ 的倍数，我们需要 $b_i$ 来补足 rem 到 $i$ 的差距，即 $b_i = i - \text{rem}$ 。

因此，任何满足条件的 $b_i$ 都必须具有以下形式： $b_i = b_{i, \text{base}} + k \cdot i$ ，其中 $k$ 是任意非负整数。

2. 贪心构造策略

现在的问题转化为：为每个 $i$ 选择一个合适的 $k_i \ge 0$ ，使得所有最终的 $b_i = b_{i, \text{base}} + k_i \cdot i$ 互不相同。

既然题目允许输出任意解，我们可以采用贪心策略来构造。

分组：首先，我们计算出所有 $i \in [1, n]$ 的基础值 $b_{i, \text{base}}$ 。然后，我们将所有索引 $i$ 按照它们的 $b_{i, \text{base}}$ 值进行分组。例如，如果 $b_{2, \text{base}} = 5$ 且 $b_{7, \text{base}} = 5$ ，那么索引 2 和 7 就在同一组。
解决冲突：显然，同一组内的索引，它们的 $b$ 值初始候选项是相同的，必然会产生冲突。我们需要逐个为它们重新赋值。
- 我们维护一个全局的哈希集合 used_b_values，用来存放所有已经分配出去的 $b$ 值。
- 我们遍历每个分组。对于分组内的每一个索引 idx：
  - 我们从它的基础值 current_b = b_{idx, base} 开始检查。
  - 循环检查：如果 current_b 已经存在于 used_b_values 中，说明这个值已经被占用了，我们就尝试下一个可能的值，即 current_b = current_b + idx。
  - 我们重复这个过程，直到找到一个没有被占用的 current_b。
  - 将这个找到的 current_b 作为 $b_{idx}$ 的最终值，并将其添加到 used_b_values 集合中。

通过这种方式，我们为每个索引 i 都找到了一个满足条件的、且与之前所有值都不同的 $b_i$ ，从而成功构造出整个序列 $b$ 。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <map>
#include <set>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    map<int, vector<int>> groups;
    for (int i = 1; i <= n; ++i) {
        int rem = a[i - 1] % i;
        int b_base = (rem == 0) ? i : i - rem;
        groups[b_base].push_back(i);
    }

    set<long long> used_b_values;
    vector<long long> b(n + 1);

    for (auto const& [b_base, indices] : groups) {
        for (int idx : indices) {
            long long current_b = b_base;
            while (used_b_values.count(current_b)) {
                current_b += idx;
            }
            b[idx] = current_b;
            used_b_values.insert(current_b);
        }
    }

    for (int i = 1; i <= n; ++i) {
        cout << b[i] << (i == n ? "" : " ");
    }
    cout << endl;

    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        Map<Integer, List<Integer>> groups = new TreeMap<>();
        for (int i = 1; i <= n; i++) {
            int rem = a[i - 1] % i;
            int b_base = (rem == 0) ? i : i - rem;
            groups.computeIfAbsent(b_base, k -> new ArrayList<>()).add(i);
        }

        Set<Long> usedBValues = new HashSet<>();
        long[] b = new long[n + 1];

        for (Map.Entry<Integer, List<Integer>> entry : groups.entrySet()) {
            int b_base = entry.getKey();
            List<Integer> indices = entry.getValue();
            for (int idx : indices) {
                long currentB = b_base;
                while (usedBValues.contains(currentB)) {
                    currentB += idx;
                }
                b[idx] = currentB;
                usedBValues.add(currentB);
            }
        }

        for (int i = 1; i <= n; i++) {
            System.out.print(b[i] + (i == n ? "" : " "));
        }
        System.out.println();
    }
}

import sys
from collections import defaultdict

def solve():
    try:
        n = int(sys.stdin.readline())
        a = list(map(int, sys.stdin.readline().split()))
    except (IOError, ValueError):
        return

    groups = defaultdict(list)
    for i in range(1, n + 1):
        rem = a[i - 1] % i
        b_base = i if rem == 0 else i - rem
        groups[b_base].append(i)

    used_b_values = set()
    b = [0] * (n + 1)

    # Sorting keys is not necessary for correctness but makes behavior deterministic
    for b_base in sorted(groups.keys()):
        indices = groups[b_base]
        for idx in indices:
            current_b = b_base
            while current_b in used_b_values:
                current_b += idx
            b[idx] = current_b
            used_b_values.add(current_b)

    print(*b[1:])

solve()

算法及复杂度

算法：贪心构造
时间复杂度： $O(N \log N + P \log N)$ ，其中 $N$ 是序列的长度， $P$ 是解决所有冲突所需的总探测（增加）次数。
- $O(N \log N)$ 的部分来自于将 $N$ 个索引分组（使用 std::map）和向 std::set 中插入 $N$ 个最终值。
- $P \log N$ 来自于在 while 循环中检查哈希集合的开销。在大多数情况下， $P$ 的值不会太大，使得该算法能够高效运行。
空间复杂度： $O(N)$ 。
- 需要 $O(N)$ 的空间来存储分组信息、已使用的 $b$ 值集合以及最终的结果数组 $b$ 。