題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟢 ABC434E Distribute Bunnies

Problem Statement

題目簡述

數線上有 $N$ 隻兔子，第 $i$ 隻初始在座標 $X_i$ ，其跳躍能力為 $R_i$ 。
每隻兔子必須恰好跳躍一次，它可以選擇跳到 $X_i - R_i$ 或 $X_i + R_i$ 。
請求出所有兔子跳躍後，最多能在幾個不同的座標上存在兔子。

Constraints

約束條件

$1 \leq N \leq 2 \times 10^5$
$-10^9 \leq X_i \leq 10^9$
$1 \leq R_i \leq 10^9$
輸入皆為整數

思路：圖論建圖與並查集 (Graph Modeling)

這是一個非常經典的「二選一」模型，可以用圖論的角度來重新審視問題。

1. 核心轉換：將兔子視為邊

每隻兔子 $i$ 最終的落點只有兩種選擇： $X_i - R_i$ 或 $X_i + R_i$ 。
如果我們將所有可能的落點座標視為圖上的節點 (Nodes)，那麼每隻兔子 $i$ 就相當於連接 $X_i - R_i$ 與 $X_i + R_i$ 的一條無向邊 (Edge)。

兔子的跳躍決策，就等同於在每條邊上「選取」其中一個端點（代表兔子最終跳到該點）。
我們的目標是使「被選取到的不同節點數量」最大化。

觀察

每條邊只能為它的兩個端點其中之一做出貢獻。也就是說，圖中的 $E$ 條邊，最多只能選出 $E$ 個不同的節點。

2. 連通分量分析

由於圖形的各個連通分量彼此獨立，我們可以分開計算每個連通分量的貢獻。
假設某個連通分量有 $V$ 個節點與 $E$ 條邊：

當 $E = V - 1$ （這是一棵樹）：
一棵無環的樹擁有 $V - 1$ 條邊。因為每條邊最多只能選取一個節點，所以整棵樹最多也只能選出 $V - 1$ 個不同的節點。事實上，我們總是可以選定任意一個節點為根，然後在剩下的每條邊上都「選取離根較遠的那個端點」，從而選中除了根節點以外的所有點（共 $V - 1$ 個）。
當 $E \ge V$ （存在至少一個環的圖）：
此時邊數充足。我們可以沿著環的方向尋訪，讓環上的每條邊都選取其前方的端點，這樣能確保環上所有節點都被選中；接著讓環外的分支也依循遠離環的方向，選取向外延伸的端點。如此一來即可保證這整個連通分量上的 $V$ 個節點都能被選取。

結論

對於任意擁有 $V$ 個節點與 $E$ 條邊的連通分量，我們最多能選出 $\min(V, E)$ 個不同的節點。
整張圖被選取的最大節點數量即為所有連通分量貢獻的加總： $\sum \min(V_k, E_k)$ 。

3. 實作細節

座標離散化：因為座標範圍高達 $\pm 10^9$ ，我們不能直接以此作為陣列索引，必須將所有出現過的目標座標蒐集起來，排序並進行去重與離散化映射。
並查集維護 (Union-Find)：建立一個並查集來維護連通性與連通塊資訊。除了維護連通塊內的點數 (sz) 外，我們還需要在操作中同步維護邊數。
- 每次針對一隻兔子，在其對應的兩個落點座標建邊：利用並查集進行 union 合併。
- 在此並查集實作中，即使即將合併的點早已同屬一個集合 (fx == fy)，我們也必須記錄這是一條新的邊（self.cnt[fx] += 1）。

複雜度分析

時間複雜度： $\mathcal{O}(N \log N)$ $O (N lo g N)$
- 收集所有落點並進行排序去重的時間為 $\mathcal{O}(N \log N)$ 。
- 將 $N$ 隻兔子的選項加入並查集的時間為 $\mathcal{O}(N \alpha(N))$ 。
空間複雜度： $\mathcal{O}(N)$ $O (N)$
- 儲存離散化的座標點與並查集數組所需的記憶體為 $\mathcal{O}(N)$ 。

Code

class UnionFind:
    __slots__ = ["n", "pa", "sz", "cnt"]

    def __init__(self, n: int):
        self.n = n
        self.pa = list(range(n))  # 父節點
        self.sz = [1] * n  # 連通分量包含的點數
        self.cnt = [0] * n  # 連通分量包含的邊數

    def find(self, x: int) -> int:
        while self.pa[x] != x:
            self.pa[x] = self.pa[self.pa[x]]
            x = self.pa[x]
        return x

    def union(self, x: int, y: int) -> None:
        fx, fy = self.find(x), self.find(y)
        self.cnt[fx] += 1
        if fx == fy:
            return
        if self.sz[fx] < self.sz[fy]:
            fx, fy = fy, fx
        self.pa[fy] = fx
        self.sz[fx] += self.sz[fy]
        self.cnt[fx] += self.cnt[fy]


def solve():
    N = int(input())
    rabbits = [tuple(map(int, input().split())) for _ in range(N)]

    Xs = set()
    for x, r in rabbits:
        Xs.add(x - r)
        Xs.add(x + r)
    Xs = sorted(list(Xs))
    mp = {x: i for i, x in enumerate(Xs)}

    uf = UnionFind(len(Xs))
    for x, r in rabbits:
        uf.union(mp[x - r], mp[x + r])

    ans = 0
    for u in range(len(Xs)):
        if uf.find(u) == u:
            ans += min(uf.sz[u], uf.cnt[u])
    print(ans)


if __name__ == "__main__":
    solve()

寫在最後

Cover Image Credit

The cover image was created by @floomf. All rights belong to the original artist.

It is used here only as a non-commercial cover illustration for this note. I do not claim ownership of the artwork.

If you are the copyright holder and believe this usage is inappropriate, please contact me by email or leave a comment. I will remove the image promptly.