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