//GDKOI 2012之前涉及的題目, 由此可見寒假真的什么都沒做
1.25
air[二分圖最大匹配 -> 最大流], 1h
[建圖]
(1) 在飛行員u和外籍飛行員v間增加有向邊(u,v), 同時增加源S到u的邊(S,u), 以及v到匯T的邊(v,T).
(2) 考慮到n<=100, 利用鄰接矩陣存儲, 上文增加邊容量為1, 其余為0, S到T的最大流即為答案.
(3) 直接利用map記錄u和v的對應關系
*數據的方案似乎不是最小字典序, 此外題目中未涉及方案的順序問題, 暫不考慮.
path[最小路徑覆蓋 -> 二分圖最大匹配 -> 最大流], 1h
注意到在路徑覆蓋中, 每個點只能被覆蓋一次.
[建圖]
將每個點拆分, 然后源S和匯T分別連邊, 點間按照題目要求連邊, 求最大流f即可.
顯然如果要增加一個路徑覆蓋, 必須存在某點沒有前驅(或后繼), n-f即為所求.
[輸出方案]
利用flow數組從1開始遍歷, 用vis標記已訪問點即可.
某題 by ftiasch
Given two sorted arrays A, B of size m and n respectively. Find the k-th smallest element in the union of A and B. You can assume that there are no duplicate elements.
http://www.leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html
[O(log(n+m))做法]
你假設求第k大嘛, 肯定是這邊來前i個, 那邊來前j個. 然后二分i, 就有j了. 然后check一下合法否.
1.27
poj 2976[分數規劃 -> 參數搜索]
[定義]一般地, 求max{a(x)/b(x)}, a(x) b(x)是實值函數, 且b(x)>0.
特別地, 如果max{a(x)/b(x)} ∈ (0,1), 稱為0/1分數規劃
[解法]
不妨設lambda即為所求.
顯然滿足 a(x)/b(x) >= lambda (注意大于等于號)
整理可得 a(x) - b(x)*lambda >= 0
顯然存在任意x值滿足lambda即可, 比如在這種情況下可以求函數最大值, 若最大值不滿足, 那么顯然這個lambda不會得到滿足.
設g(lambda) = max{a(x) - lambda*b(x)}
分析可知:
g(λ) > 0 <=> λ' < λ
g(λ) = 0 <=> λ' = λ
g(λ) < 0 <=> λ' > λ
轉換為0/1分數規劃后, lambda ∈ (0, 1), 可以二分lambda, 注意a(x)和b(x)的求法因題目而異.
*比如最優比率生成樹問題
*可以利用qsort直接對double排序, 寫法和int一致, 需要注意排序時return x > 0 ? 1 : -1;不要返回0
*對于浮點誤差, EPS = 1e-8, 越小越好(時間代價?)
1.31
GDKOI 2010分析[未驗證]
30 + 20 + 12 + 12 = 74
30 + 40 + 20 + 12 = 102
考慮到實際情況, 以及對拍時間, 似乎150+并非不可能.
Day1
[1]load
AC, 改變松弛條件的最短路, 可以使用Floyd
[2]goodjob
30%, 裸DFS
AC, 狀壓DP
[3]pizza
30%-50% 亂搞, 利用最大m段和或者分數規劃
AC 利用周期數列的性質?不明.
[4]plan
30% 暴搜?
AC 費用流
Day2
[1]collection
數學題, 通過簡單的變形得到函數, 可以利用三分法或者Cauthy不等式求解
[2]cook
10% 暴搜, 生成全排列
AC 4維DP
[3]table
50% BFS
AC 雙向BFS
[4]push
30% 模擬
AC 利用掃描線思想, 對坐標排序[具體不明...]
GDKOI 2011分析[未驗證]
30 + 20 + 8 + 12 = 70
24 + 20 + 12 + 12 = 68
考慮到考場上可能的問題, 大概能保證100.
Day1
[1]sewer
DFS/BFS/...隨便模擬
*小數據驗證
[2]park
50% 對于每個長方形, 枚舉每棵樹是否在其上, O(NM)
AC 通過某種操作把驗證某個樹在某個矩形上, 由O(N)降至O(logN), 比如平衡樹
*小數據驗證, 如果構造AC算法必須對拍
[3]mission
20% 模擬
AC T_T我不會
[4]move
30% BFS
AC A*/狀壓DP
*小數據驗證
Day2
[1]weight
30% DFS, O(3^N)
AC 分成兩堆, 分別進行DFS, 然后對于每個砝碼組合m, 在另外一堆里找n, 使得m+n滿足題意即可.
*兩種思路對拍
[2]ponytail
50% 簡單分析之后利用整除性和打表暴力
AC 進一步的分析, 利用歐拉函數求解
根據題意
s >= x + y ...(1)
1/x + 1/y = 1/z ...(2)
由(2)可得, x+y | xy ...(*)
設(x, y) = d
可得x = d * x1, y = d * y1
代入(*)可得 x1+y1 | dx1y1
易證x, y分別和x+y互質
令d = t(x1 + y1), 代入即得
s = x + y = t(x1 + y1)^2
令n = x1 + y1, 顯然滿足題意的n的個數為歐拉函數φ(n), 滿足題意的t的個數為[S/n]
綜上可得, Σφ(n)*[S/n]即為所求.
[3]bright
30% 最大流
AC T_T我不會
[4]eight
30% DFS
AC 狀壓DP
=> 導出結論, 主要復習暴搜, 其次復習基本算法, 如圖論若干, ST等.
2.1
rqnoj 70 八數碼難題[BFS+hash], 2h
BFS實現, 利用hash判重(簡單的取余法)
*移動步驟考慮不周, 可以直接利用數組存儲, 四個方向分別為±1或3; 需要注意±1, 即左右移動后, 0必須在同一行
*hash寫錯
雙向廣搜, 擴展完一邊的該層節點, 再擴展另一邊的一層節點, 直到兩邊狀態相遇.
http://longxiaozhi.is-programmer.com/posts/24858.html
實現無能, 遂放棄.