POJ 1019 Number Sequence：數位分組定位第 k 個數字

題目大意

構造無限序列：S₁S₂...Sₖ...，其中 Sₖ = "123...k" (1 到 k 連寫)。
序列前 80 位：11212312341234512345612345671234567812345678912345678910123456789101112345678910...
給定位置 i (1 ≤ i ≤ 2,147,483,647)，求該位置的數字。多測試用例。

結構分析：分組長度遞推

設 len(k) 為第 k 組 Sₖ 的長度。
len(1) = 1
len(k) = len(k-1) + digits(k)，其中 digits(k) 為 k 的十進制位數。

累積長度 sum(k) = Σ_{j=1}^k len(j) 為前 k 組總長度。
目標位置 i 所在組 k 滿足 sum(k-1) < i ≤ sum(k)。

預計算策略

1. 預計算 len[k] 和 sum[k] 直到覆蓋 2.1×10⁹
2. 預計算「展開後的數字序列」digits[]：將所有 Sₖ 依次攤平存入數組
3. 查詢時：二分 sum[] 找組別 k，組內偏移 pos = i - sum[k-1]，輸出 digits[pos]

關鍵參數估算

• digits(k)：1-9 為 1 位，10-99 為 2 位，100-999 為 3 位... 可用 log10 或循環計算
• len(k) 約為 k log k 量級
• sum(k) 約為 k² log k，k ≈ 30000 時 sum 超 2.1×10⁹

完整代碼

#include <bits/stdc++.h>
using namespace std;

const int MAXK = 32000; // 足夠覆蓋 2.1e9
int len[MAXK + 1];      // len[k] = S_k 長度
long long sum[MAXK + 1]; // sum[k] = 前 k 組總長度
int digitsArr[1000000];  // 攤平後的數字序列 (足夠大)
int digitsLen = 0;

int numDigits(int x) {
    int d = 0;
    while (x) { ++d; x /= 10; }
    return d;
}

void precompute() {
    len[0] = 0; sum[0] = 0;
    for (int k = 1; k <= MAXK; ++k) {
        len[k] = len[k-1] + numDigits(k);
        sum[k] = sum[k-1] + len[k];
        // 構建 S_k 的數字並追加到 digitsArr
        int t = k;
        int buf[10], cnt = 0;
        while (t) { buf[cnt++] = t % 10; t /= 10; }
        while (cnt--) digitsArr[digitsLen++] = buf[cnt];
    }
}

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

    int T; cin >> T;
    while (T--) {
        long long pos; cin >> pos;
        // 二分找組別
        int k = lower_bound(sum + 1, sum + MAXK + 1, pos) - sum;
        long long offset = pos - sum[k-1]; // 1-based 組內偏移
        cout << digitsArr[offset - 1] << '\n'; // digitsArr 0-based
    }
    return 0;
}

優化：無需存儲 digitsArr

組內偏移 offset 對應 Sₖ 的第 offset 個數字。可直接計算：

1. 在 1..k 中找包含第 offset 位的數字 x
2. x 的第幾位

int findDigitInGroup(int k, long long offset) {
    for (int x = 1; x <= k; ++x) {
        int d = numDigits(x);
        if (offset <= d) {
            // x 的第 offset 位 (從高位算)
            int divisor = 1;
            for (int i = 0; i < d - offset; ++i) divisor *= 10;
            return (x / divisor) % 10;
        }
        offset -= d;
    }
    return -1; // 不會到達
}

複雜度分析

• 預計算：O(MAXK × log MAXK) ≈ 3×10⁴ × 5，極快
• 查詢：二分 O(log MAXK) + 組內線性 O(k) 或 O(log k)
• 空間：O(MAXK + 總數字長度) ≈ 數 MB

總結

本題核心是序列分層結構識別：大組 Sₖ → 組內數字 1..k → 數字內部位。通過預計算累積長度 sum[k] 快速定位大組，再在組內線性/二分定位具體數字和位。預計算 + 二分 + 組內計算是處理「無限序列第 k 位」問題的標準範式。