[传智杯 #5 初赛] E-梅莉的市场经济学

题意

给出一个由很多“段”拼起来的无限数列。

第 i 段的内容是：

0, 1, 2, ..., i, i-1, ..., 0, -1, -2, ..., -i, -i+1, ..., 0

现在有 q 次询问，每次给一个 k，要求输出第 k 个位置上的数值。

思路

先看一个更直接的朴素做法：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43#include <bits/stdc++.h>
using namespace std;

int q;

long long segment_len(long long seg) {
    return 4 * seg + 1;
}

long long value_in_segment(long long seg, long long pos) {
    if (pos <= seg + 1) {
        return pos - 1;
    }
    if (pos <= 3 * seg + 1) {
        return 2 * seg + 1 - pos;
    }
    return pos - (4 * seg + 1);
}

// 朴素做法：从第 0 段开始，一段一段减掉长度，
// 直到定位到第 k 个位置属于哪一段。
long long solve_one(long long k) {
    long long seg = 0;
    while (k > segment_len(seg)) {
        k -= segment_len(seg);
        seg++;
    }
    return value_in_segment(seg, k);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> q;
    while (q--) {
        long long k;
        cin >> k;
        cout << solve_one(k) << '\n';
    }

    return 0;
}

brute.cpp 会从第 0 段开始，一段一段减掉长度，直到找到第 k 个位置到底属于哪一段。

这个思路很直观，但当 k 很大时，逐段跳会慢很多。

第一步：先求第 `i` 段长度

第 i 段可以拆成四部分：

0..i：长度 i+1
i-1..0：长度 i
-1..-i：长度 i
-i+1..0：长度 i

所以第 i 段总长度是：

4i + 1

第二步：求前若干段总长度

从第 0 段加到第 i 段：

1 + 5 + 9 + ... + (4i+1)

这是一个等差数列，和为：

(i+1)(2i+1)

这个式子非常关键，因为它让我们能快速判断：

第 k 个数到底落在哪一段

第三步：二分定位段号

设 prefix(i) = (i+1)(2i+1)。

我们要求最小的 seg，满足：

prefix(seg) >= k

这样第 k 个位置就落在第 seg 段里。

再减去前面所有段的总长度，就能得到它在这一段内的相对位置 pos。

第四步：按段内位置直接算值

第 seg 段内部本身是一个分段的“上升-下降-下降-上升”结构：

前 seg+1 个位置：0,1,2,...,seg
接下来到第 3seg+1 个位置：一路下降到 -seg
最后再上升回 0

因此只要根据 pos 落在哪一段，用分段公式直接算就行。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59#include <bits/stdc++.h>
using namespace std;

int q;

// 前 i 段（从第 0 段到第 i 段）的总长度。
// 第 i 段长度是 4*i+1，所以总和为 (i+1)*(2*i+1)。
__int128 prefix_len(long long i) {
    return (__int128)(i + 1) * (2LL * i + 1);
}

// 已知位置落在第 seg 段内，且段内位置是 pos（从 1 开始），求该值。
long long value_in_segment(long long seg, long long pos) {
    if (pos <= seg + 1) {
        return pos - 1;
    }
    if (pos <= 3 * seg + 1) {
        return 2 * seg + 1 - pos;
    }
    return pos - (4 * seg + 1);
}

long long solve_one(long long k) {
    long long l = 0;
    long long r = 2000000000LL;

    // 二分找到最小的 seg，使得前 seg 段总长度 >= k。
    while (l < r) {
        long long mid = (l + r) >> 1;
        if (prefix_len(mid) >= (__int128)k) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    long long seg = l;
    __int128 prev = 0;
    if (seg > 0) {
        prev = prefix_len(seg - 1);
    }

    long long pos = (long long)((__int128)k - prev);
    return value_in_segment(seg, pos);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> q;
    while (q--) {
        long long k;
        cin >> k;
        cout << solve_one(k) << '\n';
    }

    return 0;
}

复杂度

每次询问二分一次段号，时间复杂度 $O(log k)$
总时间复杂度 $O(q log k)$
空间复杂度 $O(1)$

总结

这题最重要的不是模拟段内数值，而是先看出：

第 i 段长度是 4i+1
前缀总长度是 (i+1)(2i+1)

一旦有了这个前缀长度公式，题目就变成“二分找段号 + 段内分段计算”。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。