8.6
poj 1731[全排列生成]
參照白書上的做法, 關(guān)鍵在于
(1)遞歸的邊界條件cur == n
(2)遞歸調(diào)用的條件c1(在生成序列中出現(xiàn)次數(shù)) < c2(在原序列中出現(xiàn)次數(shù))
(3)!i || P[i-1] != P[i]判重
*需要注意, qsort可以直接對char排序
RQNOJ四周年模擬賽 -> 據(jù)說是NOIp難度 -> 審題壓力很大
[七顆果子]給出一個數(shù)開七次方
30%的做法是直接開七次方
AC算法, 注意到輸入不超過777位, 所以答案不超過[lg(10^(777/7))]+1 = 112位, 二分次數(shù)不超過log{2}{10^112} = 372.很明顯對于每一個輸入我們可以得到答案的位數(shù), 先利用位數(shù)確定范圍, 然后壓位高精乘.
[七夕星夜]
此題無思路..只會模擬. 猜測標(biāo)準(zhǔn)算法是DP+優(yōu)化
[七色彩虹]
將起點和終點各看做一朵云彩, 題目可以看作規(guī)定起點和終點的DAG最長路問題. 方程f(i, j) = min(f(k, j-1) + w(i, k)), 時間復(fù)雜度是O(N^7).由于每個點經(jīng)過不止一次, 不能利用vis.想不到什么優(yōu)化.
[七夕的禮物]
模擬或者利用公式[usaco friday涉及的蔡勒公式]
[估計]理論得分190, 實際上120左右, 還不一定調(diào)的出來. 去年做的話, 應(yīng)該能90左右.
8.7
checker[DFS]
思路和昨天的生成全排列如出一轍, 可行性剪枝都在擴(kuò)展節(jié)點的時候, 不同的是此題利用vis避免了循環(huán)檢查.
*把vis數(shù)組利用位運(yùn)算實現(xiàn), 速度提升不大, 從0.73s到0.7s而已.
*M67給出的位運(yùn)算做法只需要0.135s, 測試后發(fā)現(xiàn)兩程序遞歸次數(shù)一樣. 主要差別應(yīng)該是在循環(huán)擴(kuò)展節(jié)點.
*vis下標(biāo)打反一次, 沒有看對稱性剪枝.
*發(fā)現(xiàn)一個驚人事實, USACO服務(wù)器計算能力加強(qiáng)了, NOCOW上據(jù)說0.9X的程序, 現(xiàn)在提交0.6X.
poj 1049[DFS], 1h, 3WA
直接套用生成全排列, 不同的是遞歸邊界條件不是l而是c, 擴(kuò)展節(jié)點注意滿足A[i-1] < A[i]
*萬般無奈找std對拍, 復(fù)習(xí)了隨機(jī)數(shù)和bat的寫法, 再次提示, 注意靜態(tài)查錯!!!
fence8
全排列生成+可行性剪枝, 時間復(fù)雜度O(K!), 只過了一個測試點 -_-
poj 3050[DFS], 50min
學(xué)習(xí)DFS-ID, 突然發(fā)現(xiàn)我昨天寫的事實上就是DFS-ID. 不同的是, DFS-ID將深度逐漸遞增, 進(jìn)行多次搜索. 也就是說會存在一些冗余, 但是鑒于解答樹的節(jié)點主要集中在最后兩層, 所以前面的狀態(tài)量并不大. 事實上DFS-ID結(jié)合了BFS處理距離節(jié)點最近的問題, 以及DFS的空間復(fù)雜度優(yōu)勢.
*調(diào)試了20min, 原因是因為對狀態(tài)編碼的一個循環(huán)寫錯了. -> 如果涉及多組易混變量的話, 一定要重點檢查.
*Hash表的MaxState如何確定?
[Training關(guān)于BFS\DFS\DFS-ID的介紹]http://www.oiers.cn/usaco%20training/11-401.asp.htm
8.8
fence8[高仿dd_engi牛的程序]
枚舉每一個board可以切成那些rail, 分析各種剪枝的動機(jī).
優(yōu)化:
1.排序后計算Σrail[1..i]>Σboard[1..N]的R=i的最小值 => 縮小R的可能性
2.二分[如何處理邊界???] => 減少DFS-ID的枚舉量
*關(guān)于邊界處理的動機(jī) by gXX
因為唯一的問題就是出現(xiàn)在[i, i + 1]這種區(qū)間, 你總是要調(diào)整mider的取法, 使得每次至少能夠刪掉一個元素。
(1)如果mider成功調(diào)整為[left, mider]否則是[mider + 1, right]
那么你需要寫一個mider = (left + right + 1) / 2;
(2)如果mider成功調(diào)整為[mider, right]否則是[left, mider - 1]
那你就要寫mider = (left + right) / 2
(3)在區(qū)間長度小于2的時候進(jìn)行特判
3. rail[i] == rail[i-1] -> 這一個能切出來, 下一個直接試能不能切一個同樣的
4. board[i] == board[i-1] -> 相等的情況下, 這個能切出來, 下一個顯然也能切出來
[關(guān)于剪枝3和4]
如果有兩個欄桿的長度相同，那么這兩個欄桿從哪兩塊木板或者從一塊木板中切出對最終結(jié)果是沒有影響的，所以在遍歷木板的時候，可以按照木板的順序進(jìn)行切割。比如規(guī)定一種次序，編號靠前的木板優(yōu)先切割相同欄桿的第一個，以此類推，那么當(dāng)rail[i]==rail[i+1]時,現(xiàn)在用第k塊木板切出欄桿i，則欄桿i+1就從第k塊或者更后面的木板進(jìn)行切割，而不必再從頭開始，因為i+1在i前面的情況已經(jīng)搜索過了，其實將i+1與i的位置互換一下就是了；同理，如果兩個木板相同，那么也規(guī)定靠前的優(yōu)先切割欄桿；
[剪枝動機(jī)] by wh
這個剪枝主要是充分利用數(shù)據(jù)性質(zhì)進(jìn)行不等式控制，和生日蛋糕有點類似之處。所以說對于“切割”類的搜索題，通常他的“剩余部分”往往隱含著一些限制，可以作為剪枝的突破口
另外這個剪枝有個使用前提，就是要先轉(zhuǎn)化成判定性問題，因此這也是我們必須id-dfs的原因
rqnoj 350[查找第k大]
這題對于類似快排來說數(shù)據(jù)比較強(qiáng), Hoare劃分法的時間常數(shù)比Lomuto劃分法時間常數(shù)少一些, 平均復(fù)雜度O(N), 最差的話O(N^2). 真正意義上的O(N)算法似乎是非常麻煩的分治. 在本題中復(fù)雜度為O(MN). 使用平衡樹的話可以做到O(MlogN).
*需要注意的是, 算法中存在swap操作, 故而如果求區(qū)間最值的話需要重新賦值
*Hoare的話實際上就是左右開弓..
*Lomuto的話實際上就是折騰序列最后一個數(shù), 所以會多了很多不必要的swap
*這個隨手寫的例子不錯
7 7
5 1 3 2 6 8 7
tyvj 1001[查找第k大/小 + 素數(shù)判斷]
練習(xí)Lomuto劃分法查找第k大
*查找第k大算法O(N)較直接排序O(NlogN)的差別不大, 而且更大的數(shù)據(jù)范圍需要更高級的數(shù)據(jù)結(jié)構(gòu), 總的來說用處不大.
buylow[LIS+高精], 3h+1.5h.
方程考慮不周1h, 調(diào)試高精2h, 理解算法1h.
對于第二問, 注意到對于f[i] = f[j] + 1(j < i), 存在A[j] <= A[i](因為題目要求最長不下降子序列). 因而可以記錄prev[i]表示f[i]的上一個f[j]的值, 注意f[i] > f[j]+1和f[i] == f[j+1]都要更新.然后會在第5個點掛掉.
即使是相同的A[j], 它們所對應(yīng)的g[j]不同, 按照題意應(yīng)取最大的. 故而prev[i]需要記錄上一個j的下標(biāo).
f[i] = max(f[j]+1);
prev[i] = j(f[i] >= f[j]+1)
g[i] = Σmax(g[prev[i]]) (每個不同的A[j]對應(yīng)的最大g[j]) -> 這里需要不斷更新, 因而需要高精減
為了簡化, 在序列末尾增加元素0, 故而f[n], g[n]即為答案.
*對于方程2, 可以用next[i]記錄與A[i]相同且最近的值的下標(biāo), 計算方案時若next[i] && next[i]<i直接跳過. by BYVoid
->同樣的A[i], 最后一個的g[i]最大. 假設(shè)A[j]==A[i], 存在g[j]<=g[i], 若區(qū)間(j, i)不存在A[k]>A[i]等號不成立.
*對于雙目運(yùn)算符, 函數(shù)()后要加const, 函數(shù)參數(shù)要加const和&, 注意利用初始化結(jié)合題目要求.
*第一版程序+=函數(shù)出現(xiàn)前導(dǎo)零
*對于每一道相似的題目, 要著重思考不同點, 在紙上得到正確的方程. 否則會在調(diào)試過程中浪費(fèi)兩倍的時間.
*靜態(tài)查錯可以避免浪費(fèi)更多的調(diào)試時間, 要分析每個函數(shù)每條語句的動機(jī), 以及實現(xiàn)情況. 不要盲目調(diào)數(shù)據(jù).
8.9
fence6[DFS], 2h, 數(shù)據(jù)弱
*這題充分暴露了對題意分析不明, 貿(mào)然上手的后果. 此題應(yīng)在40min內(nèi)解決, 20min左右設(shè)計DFS, 剩余時間調(diào)試.
(1)標(biāo)號. 利用map數(shù)組存儲標(biāo)號, 然后將下面的讀入下標(biāo)全部用map映射. -> 讀題時應(yīng)該完成
(2)DFS. 枚舉每個點, 向右邊DFS, 除了出發(fā)點不能再次加入. 但是題目中給出的left和right是亂序的, 也就是說必須記錄prev, 然后從不含prev的一側(cè)繼續(xù)遍歷. 所以DFS的狀態(tài)為(起始邊, 正在遍歷邊, 上次遍歷邊, 已遍歷邊權(quán)), 利用循環(huán)檢查確定遍歷方向.
*以前寫Chapter2時就是這樣, 題目在自己的能力范圍內(nèi), 但是不注意題目的分析, 浪費(fèi)大量時間.
cryptcow[算法1, 實現(xiàn)無能], 8h
讀入原串后記錄C\O\W的個數(shù)及位置, 個數(shù)不同則直接無解, 同時處理前綴和后綴(第一個C之前的和最后一個W之后的),然后深搜.
深搜過程(層數(shù)直接通過(原串-目標(biāo)串)/3確定)中出現(xiàn)的新字符串用map記錄下標(biāo), memcpy完成下標(biāo)的復(fù)制和恢復(fù), 利用vis判重(對于每個C\O\W).
其中比較麻煩的是C\O\W在變換后位置的更新和恢復(fù), 花費(fèi)了很多時間調(diào)試. 就算在紙上先算好下標(biāo)的變換值, 還是很容易因為多個函數(shù)同時改變導(dǎo)致錯誤. 第二天上午最終過了3個數(shù)據(jù)點, 其余提示崩潰, 調(diào)試無能.
*了解一些細(xì)節(jié):std關(guān)鍵字會引起沖突; memcpy(,,字節(jié)數(shù)), 一般為sizeof(類型)*數(shù)量
*比較奇怪的是利用fgets讀入第一個數(shù)據(jù)會自動加回車.
8.10
ctyptcow[算法2], 5h
通過學(xué)習(xí)<string>的一些特性(《C++ Primer Plus》記錄的很詳細(xì)), 50min寫完了不加任何優(yōu)化的爆搜, 過了5個點.
1.得到s串的子串[i,j]: string newname(&s[i], &s[j]) -> 類似這樣的函數(shù)還有別的一些神奇的寫法
2.通過+\+=完成連接; .size()/.length()計算長度
3.getline(file, value) -> 有value的長度限制讀入長度, 不必顯式制定.
接下來是實現(xiàn)各種優(yōu)化:
1.改變搜索順序, 先順序搜O, 然后順序搜C, 最后逆序搜W(逐層if)
2.判斷變換后的串COW間的子串是否為原串的子串, 可以記錄原串每種字符出現(xiàn)的位置, 不是原串子串的話, 剪枝
3.判斷變換后的串第一個C, 最后一個W的位置, 若C>W或從兩端沒有找到C/W但是找到O, 剪枝
4.利用ELF Hash. 嚴(yán)格意義上這步算騙分, 選取質(zhì)數(shù)131071時恰好沒有沖突. 但是嚴(yán)格意義上的Hash需要判重
5.找到第一個C和最后一個W, 確定DFS字符范圍 -> 這個用了反而TLE
*對于涉及到數(shù)組的問題, 不一定要按照原來改變 -> 恢復(fù)的模式, 應(yīng)該設(shè)法避免“恢復(fù)”過程.
*關(guān)于Hash, 參見WC2007李羽修《Hash函數(shù)的設(shè)計優(yōu)化》, 很驚悚的發(fā)現(xiàn)我居然用直接取余A了.
*最后一個測試點卡著過的.
8.11
job[貪心(對稱性) + 二分], 1h
首先要注意到這題是多機(jī)器并行工作, 所以不能使用DP, 可以貪心. 事實上如果從1到max{A[i]}*n逐個枚舉t, 就可以得到最小的t. 這提示我們可以使用二分, 判定函數(shù)為Σt/A[i](1<=i<=n).
對于兩種操作A、B, 要分別計算最短時間和方案(要保證A[]\B[]序列升序), 然后利用對稱性找最大值.
*計算方案利用二重循環(huán), 1..t為外層i, 1..na\nb為內(nèi)層j, 未生產(chǎn)工件數(shù)為rest, 如果rest>0&&i|j, 那么ta\tb[n-(--rest)] = i;
*對于二分, 目前掌握兩種寫法. 一是lrj白書l>=r;check(m);l=m+1;r=m, 二是dd_engi在fence8中的l+1=r;check(m-1);l=n;r=m;
stall4[二分圖最大匹配 -> 匈牙利算法]
[二分圖最大匹配問題匈牙利算法]http://www.matrix67.com/blog/archives/39
[匈牙利算法]http://www.byvoid.com/blog/hungary/
[二分圖最大匹配的K?nig定理及其證明]http://www.matrix67.com/blog/archives/116
第三項和這題關(guān)系不大.
[匈牙利算法] by M67
從二分圖中找出一條路徑來，讓路徑的起點和終點都是還沒有匹配過的點，并且路徑經(jīng)過的連線是一條沒被匹配、一條已經(jīng)匹配過，再下一條又沒匹配這樣交替地出現(xiàn)。找到這樣的路徑后，顯然路徑里沒被匹配的連線比已經(jīng)匹配了的連線多一條，于是修改匹配圖，把路徑里所有匹配過的連線去掉匹配關(guān)系，把沒有匹配的連線變成匹配的，這樣匹配數(shù)就比原來多1個。不斷執(zhí)行上述操作，直到找不到這樣的路徑為止。
*可以從每個點開始找增廣路, 最初的覆蓋是空集, 第一個點過后就有了一條邊, 之后邊數(shù)會逐漸增多, 直到不存在交錯路.
*似乎這題應(yīng)該是無向圖, 但是寫有向圖也不影響結(jié)果.
tyvj 1035[二分圖最大匹配 -> 棋盤覆蓋], 1h
對棋盤進(jìn)行染色, 標(biāo)記不能通過的點, 然后對于每個點(x,y), 分別和(x-1,y) (x,y-1) (x+1,y) (x,y+1)建立邊(另一個點必須可以通過). 這里可以把二維坐標(biāo)一維化, 之后這屆套用匈牙利算法即可.
*注意輸入中的坐標(biāo)從1開始, 而實現(xiàn)中從0開始
*注意擴(kuò)展邊的時候, 新點同樣可以訪問 -> 卡了30min
poj 1422[二分圖最大匹配 -> 最小路徑覆蓋], 20min, 1Y
[轉(zhuǎn)載]在一個有向圖中，路徑覆蓋就是在圖中找一些路徑，使之覆蓋了圖中的所有頂點，且任何一個頂點有且只有一條路徑與之關(guān)聯(lián)；（如果把這些路徑中的每條路徑從它的起始點走到它的終點，那么恰好可以經(jīng)過圖中的每個頂點一次且僅一次）
將圖中的每個點拆為出點和入點, 將原來的邊轉(zhuǎn)化為出點和入點間的有向邊, 利用匈牙利算法可以得到最大匹配數(shù)p. 顯然二分圖中每個匹配的出點都存在后繼, 故而這些點不可能是DAG的重點, 因而答案為n-p.
[這個寫得比較好]http://www.cnblogs.com/jackiesteed/articles/2043934.html
向gXX神牛請教如何對拍.
cowcycle[DFS], 2h
同時枚舉F-組合和R-組合, 數(shù)據(jù)較弱, 加上可行性剪枝就A了.
1.搜索順序
注意到題目要求答案字典序最小, 故而可以逆序枚舉避免對字典序的判斷.(也可以順序, 然后找一個比較強(qiáng)的條件, 在完成找到答案后退出, 效率估計逆序的幾倍.)
2.狀態(tài)設(shè)置
dfs(當(dāng)前F kf, 當(dāng)前R kr, 剩余F數(shù) nf, 剩余R數(shù) nr).
3.終止條件
nf = nr = 0 || kf + 1 < F1 || kr + 1 < R1.
對于nf = nr = 0, 進(jìn)行可行性剪枝(判斷傳動比率倍數(shù)) -> 注意這里是int
4.狀態(tài)轉(zhuǎn)移
非常麻煩, nf/nr為零的情況需要單獨處理, 4種轉(zhuǎn)移方式, 但是有8種情況.
5.優(yōu)化
1)考慮到生成的待排序序列與排序后很接近, 而且數(shù)據(jù)量極小, 于是用冒泡代替快排
2)求平均值時, 先累加, 最后除; 求方差時直接忽略除, 不影響結(jié)果
這樣可以把最后一個點從1.9s優(yōu)化到0.6s, 很有效的控制常數(shù).
*所有同時涉及double和int的語句, 必須進(jìn)行強(qiáng)制類型轉(zhuǎn)換
*memcpy(ansF+1, f+1, sizeof(int)*F)必須這樣寫, 如果將第三部分寫作sizeof(f)或sizeof(f+1)導(dǎo)致錯誤 -> 原因不明
*對于這類比較復(fù)雜的搜索, 應(yīng)該現(xiàn)在紙上寫出大致模型, 并試圖找出一些問題. 直接寫程序很容易寫錯變量名, 或者出現(xiàn)設(shè)計問題. 這樣應(yīng)該能夠大幅減少調(diào)試時間.
8.12
lgame[枚舉 + 優(yōu)化], 2h
1.讀入目標(biāo)串并記錄分值.
2.讀入字典, 如果字典中串的長度小于等于4, 且目標(biāo)串長度大于7, 記錄該串. 需要注意該串的每一個字母出現(xiàn)次數(shù)不應(yīng)超過目標(biāo)串出現(xiàn)字?jǐn)?shù).
3.如果該串分?jǐn)?shù)大于等于目前記錄最大分?jǐn)?shù), 則更新答案. 比較奇怪的是這里memcpy直接用sizeof(dic[t])不影響結(jié)果, 可能是字符串的原因.
4.對記錄子串進(jìn)行枚舉, 并更新答案. 這里如果利用字符數(shù)組的話, 要注意計算連接處的坐標(biāo)(不妨利用for, memcpy容易出錯)
*對于字符串可以利用qsort間接排序, cmp函數(shù)先逐位比較, 然后比較長度.
*注意到題目中每個單詞不超過7個字母, 但是輸出中可能包含空格! 如果內(nèi)存過小或不指定'\0'的話, 會繼續(xù)輸出后面的字符串.
*對于這類寫代碼都需要0.5h的題目, 需要思考如何減少調(diào)試時間, 現(xiàn)在調(diào)試時間是思考算法和寫代碼時間的兩倍.