0w1

Divide and Conquer

CFR 797 F. Mice and Holes ( DP, Monotonous, Divide and Conquer Optimization, or Deque Optimization )

Problem - F - Codeforces題意: 有 N 隻老鼠,用座標描述。有 M 個洞,用座標和容量描述。一隻位於座標 x 的老鼠進到位於座標 y 的洞裡要花費 abs( x - y )。問最小花費總和為何,才能使所有老鼠進洞。制約: 1 ≤ N, M ≤ 5000 abs( X[ i ] ), abs( P[ i ] )…

CFR 786 C. Till I Collapse ( Math, Sqrt Dcmp, Divide and Conquer )

Problem - C - Codeforces題意: 給一個長度為 N 的陣列,用顏色描述。要求對於所有 K 資料規模: N ≤ 1e5解法: 據說這可以用資料結構 ( 樹狀數組 ) 直接做掉,但我看不懂。 首先答案一定是非嚴格遞減的。 這題的重點在於看透一個結論:「答案的種類大約在 …

CFR 790 B. Bear and Tree Jumps ( Centroid Decomposition, Divide and Conquer )

Problem - B - Codeforces題意: 給一棵邊權為 1 的樹,問所有有序點對的距離總和。資料規模: N ≤ 2e5 K ≤ 5 TL : 2000 ms解法: 考慮樹分治,分治後都是一個子問題。分別結算子樹本身的貢獻後,計算每個需要經過當前這個重心的點對的貢獻,以及以當前這個…

IOI 2016 Messy ( Interactive, Divide and Conquer )

http://ioinformatics.org/locations/ioi16/contest/day2/messy/messy-TWN.pdf 1960 - [IOI 2016] Messy | TIOJ INFOR Online Judge題意: 你可以將任意數量的無號 n 位數丟 ( add_element() )進一個 set 裡面,然後呼叫 compile_set(),這個 set 裡面的所有…

CFR 429 D. Tricky Function ( Divide and Conquer, Closest Pair )

Problem - D - Codeforces題意: 給 A 數列。求 min{ ( j - i )^2 + Sigma( A[ i + 1 .. j ] )^2, 1 ≤ i 資料規模: The first line of input contains a single integer n (2 ≤ n ≤ 100000). Next line contains n integers a[1], a[2], ..., a[n] ( - 1e4 …

CFR 234 G. Practice ( Divide and Conquer )

Problem - 234G - Codeforces題意: 有 N 個人。輸出 N 場以內的遊戲,每一場用其中一隊的所有人的編號描述。必須滿足,經過每場後,每對人都有對局過。資料規模: N ≤ 1000解法: 考慮分治,經由遞迴假設左半和右半以滿足,那只要左邊在形成一對就可以。 如…

CFR 380 C. Sereja and Brackets ( Segment Tree, D&C, Bracket Sequence )

Problem - 380C - Codeforces題意: 給一個括弧序列,和若干筆詢問。詢問給 L, R,問原序列的 [ L, R ] 區間裡最常的合法匹配序列 ( 可間斷 ) 多長 。資料規模: 序列長度 ≤ 1e6 詢問數 ≤ 1e5解法: 考慮基於分治的預處理。如果我們知道一個區間分別的最長合…

CFR 559 B. Equivalent Strings ( D&C )

Problem - 559B - Codeforces題意: 對字串定義一個比較函數: 若 A == B 則 f( A, B ) = 1 若他們的長度相同,且長度為偶數,那麼分成兩半 A[ 0 .. size / 2 ), A[ size / 2, size ) 後,左右兩半對調,若對調後的 f( A', B ) = 1,那麼 f( A, B ) = 1。資…

CFR Unsolved D&C

Problem - 559B - Codeforces 變字典序再比較就好 Problem - 321C - Codeforces Problem - 372B - Codeforces Problem - 459D - Codeforces

CFR 448 C. Painting Fence ( D&C )

Problem - 448C - Codeforces題意: 給不一定同高度的塔一排。油漆可以橫著刷也可以豎著刷,但橫著刷一次的時候,是不能跨過空的欄位。求最少要刷幾次才能刷好所有塔。數據範圍: 塔數 1 ≤ N ≤ 1e5 塔高度 1 ≤ H[ i ] ≤ 1e9解法: 遞迴考慮,最少塗刷次數可…

UVA 1608 Non-boring sequences ( DC )

UVa Online Judge It is obvious that once we find an element that is "non-boring", we can split segment to two sub segments to apply divide and conquer for each. The problem is that if we try to find that "non-boring" element from either si…