Skip to content

倍增

把線性查詢的時間複雜度優化到對數等級。

步驟

假設序列長度 ， 代表 經過 轉換的結果。第一維大小 ，第二維大小 。

  • 初始化：算出所有 。
  • 動態規劃：算出所有 。
  • 二分搜查詢：利用 的結果算出答案。

AtCoder Regular Contest 060 C

AtCoder Regular Contest 060 C - Tak and Hotels

號旅館位置為 ，，一天可以走 單位，問從 號旅館走到 號旅館要幾天。

令 從旅館 走 天最遠可以走到幾號旅館，先用二分搜求出從每家旅館走 天最遠可以走到幾號旅館，接著用動態規劃算出其他答案，在查詢的時候，二分搜找到 最多走幾天依然不會到 ，這樣比起直接找 走到 要花幾天比較容易，最後把結果 就是答案。

 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
const int LOG = 20;

int main()
{
    int n, L, q;
    cin >> n;
    vector<int> a(n);
    vector<vector<int>> dp(n, vector<int>(LOG));
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    cin >> L >> q;
    for (int i = 0; i < n; ++i)
    {
        dp[i][0] = lower_bound(a.begin(), a.end(), a[i] + L) - a.begin();
        if (dp[i][0] == n || a[i] + L < a[dp[i][0]])
            dp[i][0] -= 1;
    }
    for (int i = 1; i < LOG; ++i)
        for (int j = 0; j < n; ++j)
            dp[j][i] = dp[dp[j][i - 1]][i - 1];
    while (q--)
    {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        if (a > b)
            swap(a, b);
        int ans = 0;
        for (int i = LOG - 1; i >= 0; --i)
            if (dp[a][i] < b)
            {
                ans += (1 << i);
                a = dp[a][i];
            }
        cout << ans + 1 << '\n';
    }
}

Codeforces 1175E

Codeforces 1175E - Minimal Segment Cover

給定 個區間 和 筆詢問，詢問至少要多少區間才能覆蓋 。

令 ：從 開始經過幾個 區間能抵達的最大右界， 為包含 的所有區間最大的右界，在實作上會分成左界 和左界 分開處裡，先處理左界 的情況：；再處理左界 的情況，也就是 ，這裡用到前綴的技巧：。

二分搜的部分會搜尋 最多經過幾個區間依然不會到達 。

應用

  • 最近更新:
  • 本文貢獻者: allem40306,