2024-2025 CTU Open Contest

連結：https://codeforces.com/gym/105442
時間：2024 Nov 1, 14:44-19:45
團隊：NYCU_MyGO!!! (SorahISA, ub33, nella17)
成績：9 / 12, Penalty 803, dirt 30% ( A B C D E F G H I J K L )

A. Flag Bearer

Tags: `implementation`

水題，跳過

B. Cowpproximation

Tags: `geometry`, `binary search`

給 $n$ 個圓 $Circle (x_{i}, y_{i}, r_{i})$ ，求最小的 $t$ 使得 $i = 1 ⋂ n Circle (x_{i}, y_{i}, r_{i} + t)$ 非空。

$n \leq 1000$ 、 $∣ x_{i} ∣, ∣ y_{i} ∣ \leq 1000$ 、 $r_{i} \leq 1000$ 、誤差 $1 0^{- 5}$ 以內。

經典題，對 $t$ 二分搜之後檢查每個圓的圓周上是否存在一點在所有圓內。

兩圓交點弄出了一堆 bug，現在還沒 AC。

待補

C. Reptile Eggs

待補

D. Fishception

Tags: N/A

一開始平面上有 $4$ 個點形成了一個矩形（邊不用平行座標軸），接著有 $n - 1$ 次操作，每次會加入 $4$ 個點，這四個點會形成一個新的矩形，且新矩形嚴格包含了其他矩形們。

給 $4 n$ 個平面上的點，代表所有操作後的點，求原本的矩形的面積。

$n \leq 50000$ 、 $∣ x_{i} ∣, ∣ y_{i} ∣ \leq 1 0^{9}$

每次拔掉凸包上的點， $n - 1$ 次之後就會剩下原本的四個點。

Case 1: 最外面的矩形不平行座標軸
- 那 $x$ 、 $y$ 座標最大、最小的點各不相同且必定在凸包上。
Case 2: 最外面的矩形平行座標軸
- 那 $x$ 、 $y$ 座標最大、最小的點各有兩個，但容易看出這些點的集合只有四個點且必定在凸包上。

用兩個陣列維護按照 $x$ 、 $y$ 座標排序的 ID，剩下的用 while 迴圈就很好做。

E. Pigpartite Giraffe

待補

F. Hamster

Tags: N/A

水題，跳過

G. Pray Mink

Tags: `dp`

待補

範圍夠小，對效率沒有特別要求時用遞迴解會比較好做。

H. Ornithology

Tags: N/A

水題，跳過

求逆序數對可以用以下 code 搭配 BIT 來計算

int ans = 0;
for (int x : arr | views::reverse) {
    ans += bit.ask(x-1), bit.add(x, 1);
}

I. P||k Cutting

Tags: `binary search`, `sparse table`

給定非負整數 $a_{1}, a_{2}, \dots, a_{n}$ 以及非負整數 $k$ ，求有多少個 subarray $1 \leq ℓ \leq r \leq n$ 滿足

$(a_{ℓ} ∣ a_{ℓ + 1} ∣ \dots ∣ a_{r}) = k$

$n \leq 400000$ 、 $0 \leq k \leq 1 0^{9}$ 、 $0 \leq a_{i} \leq 1 0^{9}$

OR 只會越變越大，可以以每個位置當左界做二分搜。

先用 sparse table 預處理區間 OR 就能做到 $O (n lo g n)$ 。

J. Rabid Rabbit

Tags: `sweep line`

給定正整數 $a_{1}, a_{2}, \dots, a_{n}$ 以及 $q$ 次詢問 $(ℓ, r)$ ，求

$∣{a_{i} + a_{j} : ℓ \leq i < j \leq r} \cap {F_{i} : i \geq 1}∣$

其中 $F_{0} = F_{1} = 1$ ， $F_{k_{(\geq 2)}} = F_{k - 1} + F_{k - 2}$ 是費氏數列。

$n \leq 1 0^{5}$ 、 $q \leq 1 0^{5}$ 、 $1 \leq a_{i} \leq 1 0^{9}$

嘗試對每個 $F_{k} \leq 2 C$ 回答所有詢問。

令 $(i, j)$ $i < j$ 滿足 $a_{i} + a_{j} = F_{k}$ ，如果把 $(i, j)$ 打到二維平面上，那麼一個詢問 $(ℓ, r)$ 相當於是詢問存不存在 $(i, j)$ 滿足 $i \geq ℓ$ 且 $j \leq r$ 。

所有有意義的 $(i, j)$ 可以用 map 對每個 $j$ 找前面最後一個 $F_{k} - a_{j}$ 的出現位置來求出。

把詢問跟 pair 依照左界（ $x$ 座標）由大到小排序，只需要維護前綴 pair 的最小 $y$ 座標即可 $O (1)$ 求解。

整體複雜度是 $O (n lo g n lo g C + q lo g C)$ 。

K. Fellow Sheep

Tags: N/A

有一個長度 $n$ 的以下這種圖，給定 $(A_{i}, B_{i}, C_{i}, D_{i}, E_{i})$ ，求左端點到右端點的最大流。

$n \leq 100000$ 、 $1 \leq$ 值域 $\leq 1 0^{8}$

有四種不同路徑

$A \to B$
$D \to E$
$A \to C \to E$
$D \to C \to B$

對每塊取這四個 $min$ 的 $max$ 加起來就是答案。

L. Watchdogs

Tags: `lca`, `minimum vertex cover`

給一棵 $n$ 個點的樹，有 $k$ 隻老鼠在樹上，每隻老鼠只能在 $u_{i} ⇝ v_{i}$ 路徑的重心（可能有一個或兩個）被抓到。

求最少需要在多少個點放置捕鼠器才能抓到所有老鼠。

$n \leq 100000$ 、 $0 \leq k \leq 100000$

求路徑中點就是經典 LCA 題。

每隻老鼠能被抓到的位置要嘛是一個點（可以看成自環），要嘛是樹上的一條邊連接著的兩個點。所以問題就變成要在樹上的某個子圖做點覆蓋。

可以樹 DP 就好，也可以直接砸 Dinic。以下是最大流的做法：

因為樹是二分圖（考慮深度奇偶性），所以可以建如下的圖：
- 源點連到深度為奇數的點
- 深度為偶數的點連到匯點
- 對老鼠能被抓到的邊，將深度為奇數的點連到深度為偶數的點
- 對老鼠能被抓到的點，因為他一定要被選到，於是就新增一個虛點，並看奇偶決定怎麼連邊
- 每條邊的流量皆為 $1$

SorahISA's Contest Logs