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