8.6

poj 1731[全排列生成]

參照白書(shū)上的做法, 關(guān)鍵在于
(1)遞歸的邊界條件cur == n
(2)遞歸調(diào)用的條件c1(在生成序列中出現(xiàn)次數(shù)) < c2(在原序列中出現(xiàn)次數(shù))
(3)!i || P[i-1] != P[i]判重
*需要注意, qsort可以直接對(duì)char排序

RQNOJ四周年模擬賽 -> 據(jù)說(shuō)是NOIp難度 -> 審題壓力很大
[七顆果子]給出一個(gè)數(shù)開(kāi)七次方
30%的做法是直接開(kāi)七次方
AC算法, 注意到輸入不超過(guò)777位, 所以答案不超過(guò)[lg(10^(777/7))]+1 = 112位, 二分次數(shù)不超過(guò)log{2}{10^112} = 372.很明顯對(duì)于每一個(gè)輸入我們可以得到答案的位數(shù), 先利用位數(shù)確定范圍, 然后壓位高精乘.
[七夕星夜]
此題無(wú)思路..只會(huì)模擬. 猜測(cè)標(biāo)準(zhǔn)算法是DP+優(yōu)化
[七色彩虹]
將起點(diǎn)和終點(diǎn)各看做一朵云彩, 題目可以看作規(guī)定起點(diǎn)和終點(diǎn)的DAG最長(zhǎng)路問(wèn)題. 方程f(i, j) = min(f(k, j-1) + w(i, k)), 時(shí)間復(fù)雜度是O(N^7).由于每個(gè)點(diǎn)經(jīng)過(guò)不止一次, 不能利用vis.想不到什么優(yōu)化.
[七夕的禮物]
模擬或者利用公式[usaco friday涉及的蔡勒公式]
[估計(jì)]理論得分190, 實(shí)際上120左右, 還不一定調(diào)的出來(lái). 去年做的話, 應(yīng)該能90左右.

8.7

checker[DFS]

思路和昨天的生成全排列如出一轍, 可行性剪枝都在擴(kuò)展節(jié)點(diǎn)的時(shí)候, 不同的是此題利用vis避免了循環(huán)檢查.
*把vis數(shù)組利用位運(yùn)算實(shí)現(xiàn), 速度提升不大, 從0.73s到0.7s而已.
*M67給出的位運(yùn)算做法只需要0.135s, 測(cè)試后發(fā)現(xiàn)兩程序遞歸次數(shù)一樣. 主要差別應(yīng)該是在循環(huán)擴(kuò)展節(jié)點(diǎn).
*vis下標(biāo)打反一次, 沒(méi)有看對(duì)稱(chēng)性剪枝.
*發(fā)現(xiàn)一個(gè)驚人事實(shí), USACO服務(wù)器計(jì)算能力加強(qiáng)了, NOCOW上據(jù)說(shuō)0.9X的程序, 現(xiàn)在提交0.6X.

poj 1049[DFS], 1h, 3WA
直接套用生成全排列, 不同的是遞歸邊界條件不是l而是c, 擴(kuò)展節(jié)點(diǎn)注意滿(mǎn)足A[i-1] < A[i]
*萬(wàn)般無(wú)奈找std對(duì)拍, 復(fù)習(xí)了隨機(jī)數(shù)和bat的寫(xiě)法, 再次提示, 注意靜態(tài)查錯(cuò)!!!

fence8
全排列生成+可行性剪枝, 時(shí)間復(fù)雜度O(K!), 只過(guò)了一個(gè)測(cè)試點(diǎn) -_-

poj 3050[DFS], 50min
學(xué)習(xí)DFS-ID, 突然發(fā)現(xiàn)我昨天寫(xiě)的事實(shí)上就是DFS-ID. 不同的是, DFS-ID將深度逐漸遞增, 進(jìn)行多次搜索. 也就是說(shuō)會(huì)存在一些冗余, 但是鑒于解答樹(shù)的節(jié)點(diǎn)主要集中在最后兩層, 所以前面的狀態(tài)量并不大. 事實(shí)上DFS-ID結(jié)合了BFS處理距離節(jié)點(diǎn)最近的問(wèn)題, 以及DFS的空間復(fù)雜度優(yōu)勢(shì).
*調(diào)試了20min, 原因是因?yàn)閷?duì)狀態(tài)編碼的一個(gè)循環(huán)寫(xiě)錯(cuò)了. -> 如果涉及多組易混變量的話, 一定要重點(diǎ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牛的程序]
枚舉每一個(gè)board可以切成那些rail, 分析各種剪枝的動(dòng)機(jī).
優(yōu)化:
1.排序后計(jì)算Σrail[1..i]>Σboard[1..N]的R=i的最小值 => 縮小R的可能性
2.二分[如何處理邊界???] => 減少DFS-ID的枚舉量
*關(guān)于邊界處理的動(dòng)機(jī) by gXX
因?yàn)槲ㄒ坏膯?wèn)題就是出現(xiàn)在[i, i + 1]這種區(qū)間, 你總是要調(diào)整mider的取法, 使得每次至少能夠刪掉一個(gè)元素。
(1)如果mider成功調(diào)整為[left, mider]否則是[mider + 1, right]
那么你需要寫(xiě)一個(gè)mider = (left + right + 1) / 2;
(2)如果mider成功調(diào)整為[mider, right]否則是[left, mider - 1]
那你就要寫(xiě)mider = (left + right) / 2
(3)在區(qū)間長(zhǎng)度小于2的時(shí)候進(jìn)行特判
3. rail[i] == rail[i-1] -> 這一個(gè)能切出來(lái), 下一個(gè)直接試能不能切一個(gè)同樣的
4. board[i] == board[i-1] -> 相等的情況下, 這個(gè)能切出來(lái), 下一個(gè)顯然也能切出來(lái)
[關(guān)于剪枝3和4]
如果有兩個(gè)欄桿的長(zhǎng)度相同，那么這兩個(gè)欄桿從哪兩塊木板或者從一塊木板中切出對(duì)最終結(jié)果是沒(méi)有影響的，所以在遍歷木板的時(shí)候，可以按照木板的順序進(jìn)行切割。比如規(guī)定一種次序，編號(hào)靠前的木板優(yōu)先切割相同欄桿的第一個(gè)，以此類(lèi)推，那么當(dāng)rail[i]==rail[i+1]時(shí),現(xiàn)在用第k塊木板切出欄桿i，則欄桿i+1就從第k塊或者更后面的木板進(jìn)行切割，而不必再?gòu)念^開(kāi)始，因?yàn)閕+1在i前面的情況已經(jīng)搜索過(guò)了，其實(shí)將i+1與i的位置互換一下就是了；同理，如果兩個(gè)木板相同，那么也規(guī)定靠前的優(yōu)先切割欄桿；
[剪枝動(dòng)機(jī)] by wh
這個(gè)剪枝主要是充分利用數(shù)據(jù)性質(zhì)進(jìn)行不等式控制，和生日蛋糕有點(diǎn)類(lèi)似之處。所以說(shuō)對(duì)于“切割”類(lèi)的搜索題，通常他的“剩余部分”往往隱含著一些限制，可以作為剪枝的突破口
另外這個(gè)剪枝有個(gè)使用前提，就是要先轉(zhuǎn)化成判定性問(wèn)題，因此這也是我們必須id-dfs的原因

rqnoj 350[查找第k大]
這題對(duì)于類(lèi)似快排來(lái)說(shuō)數(shù)據(jù)比較強(qiáng), Hoare劃分法的時(shí)間常數(shù)比Lomuto劃分法時(shí)間常數(shù)少一些, 平均復(fù)雜度O(N), 最差的話O(N^2). 真正意義上的O(N)算法似乎是非常麻煩的分治. 在本題中復(fù)雜度為O(MN). 使用平衡樹(shù)的話可以做到O(MlogN).
*需要注意的是, 算法中存在swap操作, 故而如果求區(qū)間最值的話需要重新賦值
*Hoare的話實(shí)際上就是左右開(kāi)弓..
*Lomuto的話實(shí)際上就是折騰序列最后一個(gè)數(shù), 所以會(huì)多了很多不必要的swap
*這個(gè)隨手寫(xiě)的例子不錯(cuò)
7 7
5 1 3 2 6 8 7

tyvj 1001[查找第k大/小 + 素?cái)?shù)判斷]
練習(xí)Lomuto劃分法查找第k大
*查找第k大算法O(N)較直接排序O(NlogN)的差別不大, 而且更大的數(shù)據(jù)范圍需要更高級(jí)的數(shù)據(jù)結(jié)構(gòu), 總的來(lái)說(shuō)用處不大.

buylow[LIS+高精], 3h+1.5h.
方程考慮不周1h, 調(diào)試高精2h, 理解算法1h.
對(duì)于第二問(wèn), 注意到對(duì)于f[i] = f[j] + 1(j < i), 存在A[j] <= A[i](因?yàn)轭}目要求最長(zhǎng)不下降子序列). 因而可以記錄prev[i]表示f[i]的上一個(gè)f[j]的值, 注意f[i] > f[j]+1和f[i] == f[j+1]都要更新.然后會(huì)在第5個(gè)點(diǎn)掛掉.
即使是相同的A[j], 它們所對(duì)應(yīng)的g[j]不同, 按照題意應(yīng)取最大的. 故而prev[i]需要記錄上一個(gè)j的下標(biāo).
f[i] = max(f[j]+1);
prev[i] = j(f[i] >= f[j]+1)
g[i] = Σmax(g[prev[i]]) (每個(gè)不同的A[j]對(duì)應(yīng)的最大g[j]) -> 這里需要不斷更新, 因而需要高精減
為了簡(jiǎn)化, 在序列末尾增加元素0, 故而f[n], g[n]即為答案.
*對(duì)于方程2, 可以用next[i]記錄與A[i]相同且最近的值的下標(biāo), 計(jì)算方案時(shí)若next[i] && next[i]<i直接跳過(guò). by BYVoid
->同樣的A[i], 最后一個(gè)的g[i]最大. 假設(shè)A[j]==A[i], 存在g[j]<=g[i], 若區(qū)間(j, i)不存在A[k]>A[i]等號(hào)不成立.
*對(duì)于雙目運(yùn)算符, 函數(shù)()后要加const, 函數(shù)參數(shù)要加const和&, 注意利用初始化結(jié)合題目要求.
*第一版程序+=函數(shù)出現(xiàn)前導(dǎo)零
*對(duì)于每一道相似的題目, 要著重思考不同點(diǎn), 在紙上得到正確的方程. 否則會(huì)在調(diào)試過(guò)程中浪費(fèi)兩倍的時(shí)間.
*靜態(tài)查錯(cuò)可以避免浪費(fèi)更多的調(diào)試時(shí)間, 要分析每個(gè)函數(shù)每條語(yǔ)句的動(dòng)機(jī), 以及實(shí)現(xiàn)情況. 不要盲目調(diào)數(shù)據(jù).

8.9

fence6[DFS], 2h, 數(shù)據(jù)弱
*這題充分暴露了對(duì)題意分析不明, 貿(mào)然上手的后果. 此題應(yīng)在40min內(nèi)解決, 20min左右設(shè)計(jì)DFS, 剩余時(shí)間調(diào)試.
(1)標(biāo)號(hào). 利用map數(shù)組存儲(chǔ)標(biāo)號(hào), 然后將下面的讀入下標(biāo)全部用map映射. -> 讀題時(shí)應(yīng)該完成
(2)DFS. 枚舉每個(gè)點(diǎn), 向右邊DFS, 除了出發(fā)點(diǎn)不能再次加入. 但是題目中給出的left和right是亂序的, 也就是說(shuō)必須記錄prev, 然后從不含prev的一側(cè)繼續(xù)遍歷. 所以DFS的狀態(tài)為(起始邊, 正在遍歷邊, 上次遍歷邊, 已遍歷邊權(quán)), 利用循環(huán)檢查確定遍歷方向.
*以前寫(xiě)Chapter2時(shí)就是這樣, 題目在自己的能力范圍內(nèi), 但是不注意題目的分析, 浪費(fèi)大量時(shí)間.

cryptcow[算法1, 實(shí)現(xiàn)無(wú)能], 8h
讀入原串后記錄C\O\W的個(gè)數(shù)及位置, 個(gè)數(shù)不同則直接無(wú)解, 同時(shí)處理前綴和后綴(第一個(gè)C之前的和最后一個(gè)W之后的),然后深搜.
深搜過(guò)程(層數(shù)直接通過(guò)(原串-目標(biāo)串)/3確定)中出現(xiàn)的新字符串用map記錄下標(biāo), memcpy完成下標(biāo)的復(fù)制和恢復(fù), 利用vis判重(對(duì)于每個(gè)C\O\W).
其中比較麻煩的是C\O\W在變換后位置的更新和恢復(fù), 花費(fèi)了很多時(shí)間調(diào)試. 就算在紙上先算好下標(biāo)的變換值, 還是很容易因?yàn)槎鄠€(gè)函數(shù)同時(shí)改變導(dǎo)致錯(cuò)誤. 第二天上午最終過(guò)了3個(gè)數(shù)據(jù)點(diǎn), 其余提示崩潰, 調(diào)試無(wú)能.
*了解一些細(xì)節(jié):std關(guān)鍵字會(huì)引起沖突; memcpy(,,字節(jié)數(shù)), 一般為sizeof(類(lèi)型)*數(shù)量
*比較奇怪的是利用fgets讀入第一個(gè)數(shù)據(jù)會(huì)自動(dòng)加回車(chē).

8.10

ctyptcow[算法2], 5h
通過(guò)學(xué)習(xí)<string>的一些特性(《C++ Primer Plus》記錄的很詳細(xì)), 50min寫(xiě)完了不加任何優(yōu)化的爆搜, 過(guò)了5個(gè)點(diǎn).
1.得到s串的子串[i,j]: string newname(&s[i], &s[j]) -> 類(lèi)似這樣的函數(shù)還有別的一些神奇的寫(xiě)法
2.通過(guò)+\+=完成連接; .size()/.length()計(jì)算長(zhǎng)度
3.getline(file, value) -> 有value的長(zhǎng)度限制讀入長(zhǎng)度, 不必顯式制定.
接下來(lái)是實(shí)現(xiàn)各種優(yōu)化:
1.改變搜索順序, 先順序搜O, 然后順序搜C, 最后逆序搜W(逐層if)
2.判斷變換后的串COW間的子串是否為原串的子串, 可以記錄原串每種字符出現(xiàn)的位置, 不是原串子串的話, 剪枝
3.判斷變換后的串第一個(gè)C, 最后一個(gè)W的位置, 若C>W或從兩端沒(méi)有找到C/W但是找到O, 剪枝
4.利用ELF Hash. 嚴(yán)格意義上這步算騙分, 選取質(zhì)數(shù)131071時(shí)恰好沒(méi)有沖突. 但是嚴(yán)格意義上的Hash需要判重
5.找到第一個(gè)C和最后一個(gè)W, 確定DFS字符范圍 -> 這個(gè)用了反而TLE
*對(duì)于涉及到數(shù)組的問(wèn)題, 不一定要按照原來(lái)改變 -> 恢復(fù)的模式, 應(yīng)該設(shè)法避免“恢復(fù)”過(guò)程.
*關(guān)于Hash, 參見(jiàn)WC2007李羽修《Hash函數(shù)的設(shè)計(jì)優(yōu)化》, 很驚悚的發(fā)現(xiàn)我居然用直接取余A了.
*最后一個(gè)測(cè)試點(diǎn)卡著過(guò)的.

8.11

job[貪心(對(duì)稱(chēng)性) + 二分], 1h
首先要注意到這題是多機(jī)器并行工作, 所以不能使用DP, 可以貪心. 事實(shí)上如果從1到max{A[i]}*n逐個(gè)枚舉t, 就可以得到最小的t. 這提示我們可以使用二分, 判定函數(shù)為Σt/A[i](1<=i<=n).
對(duì)于兩種操作A、B, 要分別計(jì)算最短時(shí)間和方案(要保證A[]\B[]序列升序), 然后利用對(duì)稱(chēng)性找最大值.
*計(jì)算方案利用二重循環(huán), 1..t為外層i, 1..na\nb為內(nèi)層j, 未生產(chǎn)工件數(shù)為rest, 如果rest>0&&i|j, 那么ta\tb[n-(--rest)] = i;
*對(duì)于二分, 目前掌握兩種寫(xiě)法. 一是lrj白書(shū)l>=r;check(m);l=m+1;r=m, 二是dd_engi在fence8中的l+1=r;check(m-1);l=n;r=m;

stall4[二分圖最大匹配 -> 匈牙利算法]
[二分圖最大匹配問(wèn)題匈牙利算法]http://www.matrix67.com/blog/archives/39
[匈牙利算法]http://www.byvoid.com/blog/hungary/
[二分圖最大匹配的K?nig定理及其證明]http://www.matrix67.com/blog/archives/116
第三項(xiàng)和這題關(guān)系不大.
[匈牙利算法] by M67
從二分圖中找出一條路徑來(lái)，讓路徑的起點(diǎn)和終點(diǎn)都是還沒(méi)有匹配過(guò)的點(diǎn)，并且路徑經(jīng)過(guò)的連線是一條沒(méi)被匹配、一條已經(jīng)匹配過(guò)，再下一條又沒(méi)匹配這樣交替地出現(xiàn)。找到這樣的路徑后，顯然路徑里沒(méi)被匹配的連線比已經(jīng)匹配了的連線多一條，于是修改匹配圖，把路徑里所有匹配過(guò)的連線去掉匹配關(guān)系，把沒(méi)有匹配的連線變成匹配的，這樣匹配數(shù)就比原來(lái)多1個(gè)。不斷執(zhí)行上述操作，直到找不到這樣的路徑為止。
*可以從每個(gè)點(diǎn)開(kāi)始找增廣路, 最初的覆蓋是空集, 第一個(gè)點(diǎn)過(guò)后就有了一條邊, 之后邊數(shù)會(huì)逐漸增多, 直到不存在交錯(cuò)路.
*似乎這題應(yīng)該是無(wú)向圖, 但是寫(xiě)有向圖也不影響結(jié)果.

tyvj 1035[二分圖最大匹配 -> 棋盤(pán)覆蓋], 1h
對(duì)棋盤(pán)進(jìn)行染色, 標(biāo)記不能通過(guò)的點(diǎn), 然后對(duì)于每個(gè)點(diǎn)(x,y), 分別和(x-1,y) (x,y-1) (x+1,y) (x,y+1)建立邊(另一個(gè)點(diǎn)必須可以通過(guò)). 這里可以把二維坐標(biāo)一維化, 之后這屆套用匈牙利算法即可.
*注意輸入中的坐標(biāo)從1開(kāi)始, 而實(shí)現(xiàn)中從0開(kāi)始
*注意擴(kuò)展邊的時(shí)候, 新點(diǎn)同樣可以訪問(wèn) -> 卡了30min

poj 1422[二分圖最大匹配 -> 最小路徑覆蓋], 20min, 1Y
[轉(zhuǎn)載]在一個(gè)有向圖中，路徑覆蓋就是在圖中找一些路徑，使之覆蓋了圖中的所有頂點(diǎn)，且任何一個(gè)頂點(diǎn)有且只有一條路徑與之關(guān)聯(lián)；（如果把這些路徑中的每條路徑從它的起始點(diǎn)走到它的終點(diǎn)，那么恰好可以經(jīng)過(guò)圖中的每個(gè)頂點(diǎn)一次且僅一次）
將圖中的每個(gè)點(diǎn)拆為出點(diǎn)和入點(diǎn), 將原來(lái)的邊轉(zhuǎn)化為出點(diǎn)和入點(diǎn)間的有向邊, 利用匈牙利算法可以得到最大匹配數(shù)p. 顯然二分圖中每個(gè)匹配的出點(diǎn)都存在后繼, 故而這些點(diǎn)不可能是DAG的重點(diǎn), 因而答案為n-p.
[這個(gè)寫(xiě)得比較好]http://www.cnblogs.com/jackiesteed/articles/2043934.html

向gXX神牛請(qǐng)教如何對(duì)拍.

cowcycle[DFS], 2h
同時(shí)枚舉F-組合和R-組合, 數(shù)據(jù)較弱, 加上可行性剪枝就A了.
1.搜索順序
注意到題目要求答案字典序最小, 故而可以逆序枚舉避免對(duì)字典序的判斷.(也可以順序, 然后找一個(gè)比較強(qiáng)的條件, 在完成找到答案后退出, 效率估計(jì)逆序的幾倍.)
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.
對(duì)于nf = nr = 0, 進(jìn)行可行性剪枝(判斷傳動(dòng)比率倍數(shù)) -> 注意這里是int
4.狀態(tài)轉(zhuǎn)移
非常麻煩, nf/nr為零的情況需要單獨(dú)處理, 4種轉(zhuǎn)移方式, 但是有8種情況.
5.優(yōu)化
1)考慮到生成的待排序序列與排序后很接近, 而且數(shù)據(jù)量極小, 于是用冒泡代替快排
2)求平均值時(shí), 先累加, 最后除; 求方差時(shí)直接忽略除, 不影響結(jié)果
這樣可以把最后一個(gè)點(diǎn)從1.9s優(yōu)化到0.6s, 很有效的控制常數(shù).
*所有同時(shí)涉及double和int的語(yǔ)句, 必須進(jìn)行強(qiáng)制類(lèi)型轉(zhuǎn)換
*memcpy(ansF+1, f+1, sizeof(int)*F)必須這樣寫(xiě), 如果將第三部分寫(xiě)作sizeof(f)或sizeof(f+1)導(dǎo)致錯(cuò)誤 -> 原因不明
*對(duì)于這類(lèi)比較復(fù)雜的搜索, 應(yīng)該現(xiàn)在紙上寫(xiě)出大致模型, 并試圖找出一些問(wèn)題. 直接寫(xiě)程序很容易寫(xiě)錯(cuò)變量名, 或者出現(xiàn)設(shè)計(jì)問(wèn)題. 這樣應(yīng)該能夠大幅減少調(diào)試時(shí)間.

8.12

lgame[枚舉 + 優(yōu)化], 2h
1.讀入目標(biāo)串并記錄分值.
2.讀入字典, 如果字典中串的長(zhǎng)度小于等于4, 且目標(biāo)串長(zhǎng)度大于7, 記錄該串. 需要注意該串的每一個(gè)字母出現(xiàn)次數(shù)不應(yīng)超過(guò)目標(biāo)串出現(xiàn)字?jǐn)?shù).
3.如果該串分?jǐn)?shù)大于等于目前記錄最大分?jǐn)?shù), 則更新答案. 比較奇怪的是這里memcpy直接用sizeof(dic[t])不影響結(jié)果, 可能是字符串的原因.
4.對(duì)記錄子串進(jìn)行枚舉, 并更新答案. 這里如果利用字符數(shù)組的話, 要注意計(jì)算連接處的坐標(biāo)(不妨利用for, memcpy容易出錯(cuò))
*對(duì)于字符串可以利用qsort間接排序, cmp函數(shù)先逐位比較, 然后比較長(zhǎng)度.
*注意到題目中每個(gè)單詞不超過(guò)7個(gè)字母, 但是輸出中可能包含空格! 如果內(nèi)存過(guò)小或不指定'\0'的話, 會(huì)繼續(xù)輸出后面的字符串.
*對(duì)于這類(lèi)寫(xiě)代碼都需要0.5h的題目, 需要思考如何減少調(diào)試時(shí)間, 現(xiàn)在調(diào)試時(shí)間是思考算法和寫(xiě)代碼時(shí)間的兩倍.