0w1

CSAcademy

CSAcademy 25. Zone Capture ( BCC )

Round #25 (Div. 2 only)題意: 給一個 01 矩陣 A[ N ][ M ]。你可以選擇一個 0 轉為 1,轉換後,所有不和任意一個邊界的 0 屬於同一個連通塊 ( 上下左右,且兩者皆 0 視為相鄰 ) 的所有 0 都會轉為 1。問最多可以有多少 1。制約: 1 ≤ N, M ≤ 1000解法: 將…

CSAcademy 25. Min Ends Subsequence ( Persistent Segment Tree )

Round #25 (Div. 2 only)題意: 給一個排列 1 ~ N,問最長的一個子序列,滿足:頭尾元素都比所有中間的元素大。輸出長度。制約: 1 ≤ N ≤ 1e5解法: 不失一般性,假設最長的這個子序列的頭 i 和尾 j 滿足:i 枚舉所有 i,令 j 為 i 顯然這個 j 是最優的,而…

CSAcademy 23 E. No Prime Sum ( Bipartite Matching, Minimum Vertex Cover )

Round #23 (Div. 2 only)題意: 給 N 個相異正整數,問最少要移除幾個數字,能使任意兩個數字的和不為質數。輸出方案。限制: 2≤N≤2000 The elements of S are distinct integers between 1 and 10^5解法: 首先顯然偶數+偶數以及奇數+奇數的情形一定不會產…

CSAcademy 23 D. Disk Mechanism ( Greedy )

Round #23 (Div. 2 only)題意: 給若干個中心,現在你要以這些中心擺放圓。有左數起第 i 個圓的半徑可以是 [ L[ i ], R[ i ] ] 中任意整數。兩個相鄰的圓必須相切。問有幾種方案。限制: 2≤N≤1e5 The point coordinates are given in increasing order and t…

CSAcademy 23 C. Permutation Matrix ( Periodic, Union Find )

Round #23 (Div. 2 only)題意: 給一個長度 M 的排列 P,現在要做一個 N * M 的矩陣,第 i 行是 P^i( P )。 問 M 個列分別的數值總和為何。限制: 1 ≤ N, M ≤ 1e5解法: 顯然會形成一些循環,用 dfs 找出這些循環並記錄每個節點在每個循環中哪個位置,預處理…

CSAcademy 23 B. Fast Travel ( Greedy )

Round #23 (Div. 2 only)題意: 有 N 個城市,以座標描述。兩個城市之間的移動的所需時間是曼哈頓距離。有些城市是特別的 ( S = 1 ),特別的城市之間可以花費 T 單位時間進行瞬間移動。Q 筆詢問,每次問兩個城市之間最少需要花費的移動時間。限制: 2≤N≤1000…