Climber.pI的OI之路

NOIp 2011 初賽備考

posted @ 2011-10-15 11:27 Climber.pI 閱讀(416) | 評論 (0) | 編輯 收藏

Problem List (9.7 ~ 9.29)

posted @ 2011-10-01 21:53 Climber.pI 閱讀(208) | 評論 (0) | 編輯 收藏

USACO Training Chapter 4 ~ 6 Summary

posted @ 2011-08-23 13:26 Climber.pI 閱讀(491) | 評論 (0) | 編輯 收藏

Problem List (8.13 ~ 8.21)

8.13

prime3[DFS + 手動(dòng)指定搜索順序], 4h, 0.1s左右出解
1.構(gòu)造所有五位素?cái)?shù), 可以先做一個(gè)313以內(nèi)的素?cái)?shù)表, 試除即可. 注意素?cái)?shù)末尾不是偶數(shù)和0.
*官方題解中枚舉6n-1和6n+1, 同時(shí)判斷末位5和0, 從素?cái)?shù)7開始枚舉即可, 枚舉量進(jìn)一步減少
2.手動(dòng)指定搜索順序, 對于每種情況分別處理, 代碼很長. 對角線優(yōu)先, 末尾數(shù)組優(yōu)先(顯然素?cái)?shù)末尾數(shù)字只能是1\3\7\9)
 0 21 18 22  5
12  2 13  8  9
16 23  3 24 10
14  7 15  4 11
 6 19 17 20  1
大致分為幾種情況:
1)非末位. 邊界條件是 0 <= i <= min{sum(除去已使用位), 9}
2)末位. 邊界條件是i = 1, 3, 7, 9(i <= sum)
3)可計(jì)算位(即該行或列或?qū)蔷€已經(jīng)填了4個(gè)數(shù)). sum < 10, 判斷是否為素?cái)?shù), dfs下一層時(shí), sum-下一層已填充位置.
4)對于由情況3)轉(zhuǎn)移而來的狀態(tài), 需要檢查sum >= 0
*可以把情況1)和2)分別合并, 利用數(shù)組指定順序亦可(代碼長度可能變化不大)
*官方題解在這里以行\(zhòng)列\(zhòng)對角線為單位填數(shù), 需要預(yù)處理某些位為某些數(shù)的素?cái)?shù).
3.對保存的結(jié)果進(jìn)行排序, 利用qsort間接排序即可.
*NOCOW上有人寫15重for循環(huán), 效率比這個(gè)低10倍. 但是15重for加上縮進(jìn)實(shí)在不好看.

race3[DFS判斷連通性], 40min
第一問, 去掉每個(gè)點(diǎn)后判斷是否能夠到達(dá)終點(diǎn), 利用DFS+vis數(shù)組標(biāo)記即可.
第二問, 第二問是第一問答案的子集. 從原點(diǎn)(標(biāo)記A不可訪問)和第一問某個(gè)點(diǎn)A分別DFS, 如果不存在某點(diǎn)在兩次同時(shí)被訪問, 那么滿足題意.
證明: 假設(shè)第二問不是第一問的子集, 那么不經(jīng)過第二問中某個(gè)點(diǎn), 必然可以到達(dá)終點(diǎn), 與題目中對于分割的定義矛盾.
*用Floyd判斷連通性亦可(有向圖傳遞閉包).

shuttle[BFS/數(shù)學(xué)], 4h
1)BFS做法(n <= 7)
1.利用位運(yùn)算保存狀態(tài), 1表示'W', 2表示'B'或空格, 附加k表示空格所在位
2.按照字典序轉(zhuǎn)移狀態(tài)(共4種方式), k的方向可以任意理解, 不影響結(jié)果. k從0開始, 顯然W只向右, B只向左.
*在草稿紙上寫好狀態(tài)轉(zhuǎn)移的具體代碼(if部分), 注意變量
*讀題, 一開始認(rèn)為棋盤長度不超過12于是就BFS, 實(shí)際上棋盤長度不超過25, 位運(yùn)算保存狀態(tài)會(huì)爆內(nèi)存. 此外輸出限制每行20個(gè)數(shù)字.
2)數(shù)學(xué) by NOCOW
我們憑借極其敏銳的眼光發(fā)現(xiàn)這組序列為
4 35 642 1357 642 35 4 (n=3,樣例)
5 46 753 2468 97531 2468 753 46 5 (n=4)
即長度為1,2,3,4,...,n,n+1,n,...,4,3,2,1這樣的2n+1組等差序列
我們討論第1~n+1組序列，這些序列滿足
　　*公差的絕對值為2
　　*奇數(shù)組為降序列，偶數(shù)組為升序列
　　*對于第i組(1<=i<=n+1),若為奇數(shù)組則首項(xiàng)為n+i，偶數(shù)組則首項(xiàng)為n-i+2
對于第n+2~2n+1組，可以由對稱性求出.
*官方題解做法類似數(shù)學(xué)做法, 觀察后得出每次都是空格向右移動(dòng)2格, 直到不能移動(dòng)(如果不能向右移動(dòng)1格的話轉(zhuǎn)向)或者達(dá)到狀態(tài).
*如果輸出字典序最小解, 不妨找規(guī)律; 如果輸出所有解, 只能搜索.

milk6[最小割+貪心], 按計(jì)劃cheat.

frameup[拓?fù)渑判騗
1.構(gòu)造有向圖. 在讀入圖的同時(shí)計(jì)算每種矩形的坐標(biāo)邊界, 然后按照邊界遍歷, 若矩形A上存在B, 則G[A][B] = 1.
2.拓?fù)渑判虿⑤敵? 注意到這里并沒有明顯層次性, 答案可能遠(yuǎn)遠(yuǎn)超過所得序列長度. 如果標(biāo)記層次的話, 若圖中指向復(fù)雜, 那么會(huì)少輸出一部分答案(如測試點(diǎn)7).
*一開始沒有看出來是拓排, 一門心思想怎么DFS.
*打錯(cuò)變量調(diào)了1h, 沒有看出來輸出序列的不同浪費(fèi)了1h. -> 開始的分析非常重要, 邊寫邊改時(shí)間成本太高.

8.14

theme[二分], 1.5h, O(N^3logN)
1.對序列做差, d[i] = A[i+1] - A[i].
2.二分求最大值. 注意l=m+1, 可能存在m為最大值的情況, 所以需要check(l).
3.分別枚舉兩個(gè)序列的開端(序列1開端為i, 序列2開端為i+l+1), 如果相同, 繼續(xù)比較.
*數(shù)組開小, 導(dǎo)致詭異錯(cuò)誤 -> 讀題!!!, 20min
*注意編寫的程序前分析邊界情況 -> 1h

8.15

調(diào)教laptop.

8.16

frameup[拓?fù)渑判騗, 20min -> 參照 北極南天星 的題解, 意簡言賅
構(gòu)圖這里不再贅述. 注意到題目要求輸出拓?fù)湫蛄? 長度一定, 并不像DP中出現(xiàn)明顯層次性.
dfs狀態(tài)(當(dāng)前序列長度), 按照定義做: 每次找入度為0的點(diǎn)u, 然后將于此點(diǎn)存在邊的點(diǎn)v入度-1. 直到所有點(diǎn)都在序列中.
*dfs按照字母升序搜索, 即滿足題目順序要求.
*構(gòu)圖統(tǒng)計(jì)每個(gè)點(diǎn)u入度時(shí)注意判重, 存在多個(gè)點(diǎn)滿足條件.

theme[DP], O(N^2)
f[i][j] = max{f[i+1][j+1]}(A[i+1]-A[i] == A[j+1]-A[j]) + 1
f[i][j]表示以A[i]和A[j]為起點(diǎn)的序列的最大長度, 以j-i為階段, 注意f[i][j]<=j-i. 注意到狀態(tài)之間存在依賴性, 各階段間不存在依賴性, 只需保存當(dāng)前狀態(tài). 不斷更新答案即可.
*不能直接二分, 答案可能小于j-i, 無法寫判定函數(shù) -> 如果對于每個(gè)j-i的長度序列單調(diào)不下降的話還是可以二分.

8.17

starry[floodfill+模擬], 4h
讀入圖, 對每個(gè)點(diǎn)進(jìn)行floodfill; 如果存在星座, 那么和之前的星座進(jìn)行判重; 不重復(fù)的話, 利用數(shù)組st0記錄當(dāng)前星座. 否則改變標(biāo)號.
判重首先判斷 長度 和 星體個(gè)數(shù)(只利用這兩點(diǎn)可以過4個(gè)點(diǎn)), 然后直接模擬即可. 在floodfill過程中記錄坐標(biāo)極值, 然后提取矩形, 和st0中星座比較.
比較需要用到順時(shí)針向右轉(zhuǎn)90度和水平翻轉(zhuǎn), 坐標(biāo)變換分別是(tx-x, y)和(y, tx-x), 可以畫圖觀察.
*一開始沒有考慮如何判重, 想了1h
*沒有考慮同一矩形內(nèi)存在多個(gè)相同星座, 浪費(fèi)0.5h

fc[凸包(Graham-Scan, 水平序?qū)崿F(xiàn))], 1h, 參考黑書
1.以縱坐標(biāo)為第一關(guān)鍵字, 橫坐標(biāo)為第二關(guān)鍵字, 對坐標(biāo)升序排序.
2.左鏈掃描, 從1到n. 如果棧內(nèi)存在超過兩個(gè)元素, 那么叉積判斷是否>180°(即cross<=0), 滿足的話彈出棧頂元素(利用while). 將當(dāng)前點(diǎn)加入棧.
3.右鏈掃描, 從n-1到1. 判斷同上.
4.計(jì)算周長. 加入初始點(diǎn)和末端點(diǎn)距離, 依次加入棧中元素.
*利用棧表示凸包序列

snail[DFS], 50min
讀入路障坐標(biāo)(x,y)標(biāo)記為-1, 其他值為1; DFS過程中檢查下一格是否可行, 若不可行, 如果是邊界或路障可以轉(zhuǎn)向. 記錄最大值.
*注意當(dāng)前標(biāo)記在DFS后清除, 已路過格不可轉(zhuǎn)向; 障礙縱坐標(biāo)可能不是一位, 讀入橫坐標(biāo)后標(biāo)記該為為'0', 利用sscanf讀入即可.
*想起了去年NOIp第四題, 只有半個(gè)小時(shí), 但是寫了floodfill卻調(diào)不出來. 心里沒底, 仿佛這是看RP的事情, 今天半個(gè)小時(shí)的時(shí)候發(fā)生了同樣的事情, 務(wù)必加長算法設(shè)計(jì)時(shí)間.

wissqu[DFS] -> cheat
題目給出了每種牛的個(gè)數(shù), 實(shí)質(zhì)上就是帶限制的全排列, 可行性剪枝很多, 代碼大概要100+行.
*不過這題只有一個(gè)測試數(shù)據(jù), 就是樣例 -_-

8.18

fence3[局部搜索], 1h
標(biāo)準(zhǔn)做法是模擬退火, 或者隨機(jī)化搜索. 基本思想是逐漸加精度(官方題解也這么寫).
首先搜索所有整數(shù)坐標(biāo), 記錄最小距離和當(dāng)時(shí)坐標(biāo); 然后在此坐標(biāo)±1范圍內(nèi)搜索最小值, 注意增量dx/dy要初始化為0(這時(shí)不會(huì)更新最小值).

bigbrn[DP], 30min
f[i][j]表示以(i, j)為右下方頂點(diǎn)的正方形的最大邊長
f[i][j] = min(f[i-1][j], f[i][j-1], f[i-1][j-1]) + 1
初始化 f[i][j] = 1; 若(i, j)有障礙, 則f[i][j] = 0, 且該點(diǎn)不進(jìn)行dp

window[鏈表(字符串實(shí)現(xiàn)) + 矩形切割(10行)], 3h
對于操作w/t/b/d, 維護(hù)操作序列order, 利用<string>實(shí)現(xiàn). 注意string str(&a[i], &a[j])對應(yīng)區(qū)間為[i, j). 構(gòu)造小數(shù)據(jù)調(diào)試即可.
對于操作s, 利用矩形切割, 逆序添加操作序列order中矩形(可以同時(shí)維護(hù)面積). 實(shí)現(xiàn)非常簡單, 首先對判斷是否被已有矩形覆蓋(x2 < x1), 然后分成四部分添加未被覆蓋部分.
注意到數(shù)據(jù)中s操作可以連續(xù), 不妨利用char記錄上一操作, 可以避免一些矩形切割.
*這題想想會(huì)覺得頭疼, 但是實(shí)現(xiàn)非常簡單(ctypcow實(shí)現(xiàn)非常麻煩). 題目并不難, 很明顯下午看題的時(shí)候高估了實(shí)現(xiàn)難度. 不要給自己制造"難題".
*提交程序中對stdout輸出過多同樣會(huì)造成崩潰

8.19

milk4[DFS-ID + DP], 45min
利用DFS-ID枚舉桶(即枚舉r-組合), 然后DP判斷能否裝滿.
f[j] |= f[j-ans[i]](完全背包, 不考慮背包數(shù))
初始化f[0] = 1, 其他為0; f[i]表示可以量出i夸脫的牛奶
*打錯(cuò)變量(DFS/DP), 應(yīng)該首先靜態(tài)差錯(cuò), 而不是上數(shù)據(jù).
*有純dp做法, 記錄方案很繁瑣.

schlnet[強(qiáng)連通分量(Tarjan)], 1h
利用鄰接表存儲(chǔ)圖, 利用Tarjan尋找強(qiáng)連通分量(BYVoid有個(gè)很好的教程, 主過程19行).
第一問是最小點(diǎn)基, 對求得的所有強(qiáng)連通分量進(jìn)行縮點(diǎn), 入度為0的點(diǎn)的個(gè)數(shù)即為答案.
第二問為min(入度為0的點(diǎn)的個(gè)數(shù), 出度為0的點(diǎn)的個(gè)數(shù)), 需要注意只有一個(gè)點(diǎn)的時(shí)候需要特判.
[Tarjan]入棧\時(shí)間戳 -> 遍歷相鄰邊 -> 未遍歷點(diǎn)遍歷 -> 更新LOW -> LOW是否等于DFN -> 出棧標(biāo)記SCC

latin[DFS + 數(shù)學(xué)], 1h
注意第一行題目中已確定, 最后一行和最后一列同樣可以推算, 因而只需枚舉中間(n-1)*(n-2)方格即可. 可以規(guī)定第一列升序, 這樣一來計(jì)算量只是原來的1/(n-1)!, 可以過六組. 第七組需要cheat, 運(yùn)行時(shí)間大概1min左右(可能常數(shù)可以少一些). 標(biāo)準(zhǔn)做法是置換群.(std理解不能)

telecow[網(wǎng)絡(luò)流], 按計(jì)劃cheat

besty[DFS], 1h, N=7 15s
按照題意進(jìn)行DFS, 有幾個(gè)優(yōu)化.
1.當(dāng)點(diǎn)的可選擇方向?yàn)?時(shí), 用floodfill判斷圖內(nèi)未填充點(diǎn)是否可以互相到達(dá), 不能到達(dá)則剪枝.
2.如果經(jīng)過點(diǎn)(1,n), 但填充順序k不滿足題意, 剪枝.
3.內(nèi)層檢查擴(kuò)展節(jié)點(diǎn)是否符合題意(常數(shù)優(yōu)化).
4.判斷某點(diǎn)到(1,n)距離是否小于n*n-k(加了反而更慢).
*可以輸出狀態(tài)觀察歸納不可解狀態(tài)的共性, 然后剪枝. -> by dd_engi
*據(jù)說可以使用著名的cdqDP..
-> 參考黑書P184, 3h
1.圖中必須沒有孤立區(qū)域, 即上文優(yōu)化1, 這里僅討論■□■的情況.
2.搜索過程中, 除被搜索點(diǎn)和目標(biāo)點(diǎn)外, 其他點(diǎn)至少有兩個(gè)點(diǎn)與之相連. 可以利用數(shù)組link[i][j]記錄(i, j)的連通情況.
3.如果移動(dòng)方向上前一個(gè)點(diǎn)未被遍歷, 左邊點(diǎn)未被遍歷, 且左前方點(diǎn)已被遍歷時(shí), 剪枝. 右側(cè)同理.
利用剪枝1和2以及前文剪枝2, 在本地N=7需要2.3s, 加上剪枝3在本地需要1.9s, 在USACO卡時(shí)AC.
*一個(gè)技巧, 可以預(yù)先表示行列編號為0和n+1的點(diǎn)已讀, 可以避免對越界的討論.

tour[雙進(jìn)程DP/費(fèi)用流/刷表法], 3h, O(N^3)
狀態(tài)想對了, f[i][j]表示兩個(gè)人分別從起點(diǎn)出發(fā)到達(dá)城市i\j所經(jīng)過的城市數(shù).
一開始認(rèn)為方程是f[i][j] = max{f[i.prev][j], f[i][j.prev], f[i.prev][j.prev]+1}, 覺得不太對, 就去查題解.
北極天南星給出的方程是 f[i][j] = max{f[j][k], f[k][j]} + 1
規(guī)定對于任意狀態(tài)f[i][j], i > j, 需要注意f[j][k]\f[k][j]必須計(jì)算過. 初始化f[1][1] = 1, 其余為0.
*利用strcmp比較字符串即可, memcmp似乎某些情況下會(huì)出錯(cuò).
*這題和NOIp 08傳紙條的主要區(qū)別: 這題是無向圖, 而傳紙條是矩陣. 因而轉(zhuǎn)移方式不同.
[故事] by BYVoid
這是加拿大IOI93的一道原題。在WC2008中聽吳教授說道，當(dāng)時(shí)參加IOI的選手沒有人了解動(dòng)態(tài)規(guī)劃，對這道題束手無策。選手們都用上了最復(fù)雜的搜索技巧，有人還寫了雙向搜索，可是都沒有通過。回國后開始研究，最終提出了動(dòng)態(tài)規(guī)劃這一算法設(shè)計(jì)方法，于是動(dòng)態(tài)規(guī)劃變成了之后競賽出題的熱點(diǎn)。

8.20

hidden[字符串], 2.2h
最初的做法很猥瑣, 按題意模擬, 記錄最小字典序串的口令. 第8個(gè)點(diǎn)TLE了, 大概都要5s左右.
進(jìn)一步的修正記錄了每個(gè)字母每次出現(xiàn)的位置, alpha[i][0]表示出現(xiàn)次數(shù), 類似鄰接表. 只處理字典序最小出現(xiàn)次數(shù)非零的字母, 第10個(gè)點(diǎn)TLE了.
更進(jìn)一步, 對于串中若干個(gè)連續(xù)的該字母, Count[j]表示alpha[i][j]開始, 由該字母組成的最長連續(xù)串. 只處理第一個(gè), 一開始沒有考慮環(huán)狀, 第11個(gè)WA了.
*處理環(huán)狀的必要條件是, alpha[i][alpha[i][0]] + 1 == n;
*對于復(fù)雜度估計(jì)不周, O(N)的常數(shù)太大所以掛了, 之后修正沒有考慮環(huán)狀情況, 卡了1h.
*秒殺做法包括最小表示法\后綴數(shù)組\類KMP\最小后綴, 有空應(yīng)該學(xué)一下著名的KMP算法

cowxor[?]
很容易聯(lián)想到最大連續(xù)和, 注意到異或運(yùn)算滿足結(jié)合律, 可以利用O(N^2)的時(shí)間枚舉每個(gè)區(qū)間. 但是這題范圍很大, 第6個(gè)點(diǎn)就TLE了.

8.21

charrec[DP + 統(tǒng)計(jì) + 記錄方案], 2.5h
注意到題目對于最優(yōu)解的定義是損壞數(shù)據(jù)最少, 因而可以考慮DP.
f[i] = min{f[i + 19] + C[i][19], f[i + 20] + C[i][20], f[i + 21] + C[i][21]}
prev[i] = i + 19\20\21
prevk[i] = K(C[i][_]對應(yīng)的字符)
f[i]表示從第i行到第n行的最少損壞(不同位數(shù)). C[i][j]表示從第i行開始連續(xù)匹配j行的最小損壞(不同位數(shù)), 這里需要返回所對應(yīng)的字符, 實(shí)現(xiàn)時(shí)可以利用記憶化.
對于f數(shù)組, (n - 19, n]需要初始化為+∞
*可以利用d[i][j][k]表示第i個(gè)字符第j行和輸入數(shù)據(jù)第k行不同位數(shù)
*需要注意數(shù)組大小, 以及題目中寫出的font.in和給出的font.in不同.

picture[離散化+掃描線? / 離散化+線段樹 / 離散化], 1h
1.無需離散化, 直接染色, 可以過8組數(shù)據(jù). -> But, 第7組莫名奇妙的掛了.
[統(tǒng)計(jì)] 對于兩線段交點(diǎn), (G[i-1][j]^G[i+1][j]) && (G[i][j-1]^G[i][j+1])(即(i,j)左右\上下相鄰點(diǎn)顏色不同).
  對于一般點(diǎn), 水平方向上, 可以(G[i][j-1]^G[i][j+1]) && G[i-1][j] && G[i+1][j]. 豎直方向同理.
2.掃描線 + 離散化 by BYVoid
對于水平和豎直方向分別處理, 下面僅討論水平情況, 豎直同理.
(1)對于每個(gè)矩形, 將其在水平方向上的邊按照縱坐標(biāo)的大小, 分為始邊和終邊.
(2)按照縱坐標(biāo)升序掃描, 相同情況下始邊優(yōu)先(因?yàn)檫呏睾系臅r(shí)不算入周長). -> 快排即可
(3)如果遇到始邊, ++ level[i]; 如果遇到終邊, -- level[i]; 如果出現(xiàn)level[i]從0到1的情況, ++ ans; 從1到0的情況相同, 不必考慮.
-> 對于這一題直接掃描每個(gè)點(diǎn)即可, 如果數(shù)據(jù)范圍進(jìn)一步擴(kuò)大的話, 不妨使用線段切割.
答案即為ans*2;
*很像KOI10 Day2的某題, 當(dāng)時(shí)貌似我直接模擬, 然后數(shù)組爆了. 其實(shí)用sizeof算一下內(nèi)存即可.
*突然發(fā)現(xiàn)神牛的構(gòu)造能力都很強(qiáng). 比如說BYVoid的做法, 個(gè)人以為最重要的是level數(shù)組的構(gòu)造.
*如果自己寫計(jì)時(shí)函數(shù)并提交的話, 會(huì)發(fā)現(xiàn)USACO函數(shù)顯示的時(shí)間比USACO給出的時(shí)間少得多, 原因不知.
*很奇葩的是, 以前一直用PROG, 然后USACO這次突然提示使用PROB -> 什么狀況

twofive[Contor展開], ?h, 全仿std.
1.暴搜 -> 理論6組, 實(shí)際4組 -_-
2.類似kimbits, 可以使用康托展開(比較直觀的解說參見白書第10章).
關(guān)鍵在于對于一個(gè)給定的串, 如何知道小于其前n位的串的方案數(shù). 定義f[a][b][c][d][e]表示方案數(shù). 對于每個(gè)字母ch, 如用過, 那么繼續(xù)ch+1. 否則枚舉已填位后所有位, 累計(jì)方案值.
(數(shù)學(xué)描述)
若ch未被使用, f[a][b][c][d][e] = f[a+1][b][c][d][e] + f[a][b+1][c][d][e] + f[a][b][c+1][d][e] + f[a][b][c][d+1][e] + f[a][b][c][d][e+1];
初始化f[5][5][5][5][5] = 1.
*[數(shù)組開小]
  > Run 1: Execution error: Your program had this runtime error:
        Illegal file open (/dev/tty). The program ran for 0.000 CPU
        seconds before the error.

rectbarn[DP], 1.5h
1.暴力, O(R^2*C^2*P), 可以過3個(gè)點(diǎn)
2.參考WC03王知昆論文, 非常好理解
懸線：上端點(diǎn)覆蓋了一個(gè)障礙點(diǎn)或達(dá)到整個(gè)矩形上端的有效豎線. 顯然對于每個(gè)懸線擴(kuò)展得到矩形一定包含答案. 我們可以利用O(RC)的時(shí)間得到所有懸線, 因而問題的關(guān)鍵在于利用O(1)的時(shí)間處理懸線. 這里可以使用DP.
H[i][j] = H[i-1][j] + 1   (G[i][j]未損壞)
    0      (G[i][j]損壞)
L[i][j] = min{l[j], L[i-1][j]} (G[i][j]未損壞)
    ∞      (G[i][j]未損壞)
R[i][j] = min{r[j], R[i-1][j]} (G[i][j]未損壞)
    ∞      (G[i][j]未損壞)
max{H[i][j]*(L[i][j] + R[i][j] - 1)}即為答案
*北極天南星 和 論文 似乎都有一個(gè)地方把 min 打成了 max.
*i和j不能隨意交換, 需要注意所對應(yīng)的下標(biāo)范圍.(#3 WA)

vans[DP / SCDP], 1h
奇葩的遞推式, f[n] = 2*(f[n-1] + f[n-2] - f[n-3]) + f[n-4] (n >= 5)
初始化, f[1] = 0, f[2] = 2, f[3] = 4, f[4] = 5; f[50]之后需要高精度.
*推導(dǎo)方法待研究.
*求哈密頓回路個(gè)數(shù), 可以使用基于連通性的SC.

cowxor[枚舉 + 優(yōu)化], 1h, 全仿std

posted @ 2011-08-23 12:17 Climber.pI 閱讀(229) | 評論 (0) | 編輯 收藏

寫在USACO通關(guān)之后

posted @ 2011-08-22 21:07 Climber.pI 閱讀(775) | 評論 (0) | 編輯 收藏

Problem List (8.6 ~ 8.12)

posted @ 2011-08-18 12:31 Climber.pI 閱讀(253) | 評論 (0) | 編輯 收藏

USACO Training 4.1.4 Cryptcowgraphy

USER: Yupan Liu [liuyupa1]
TASK: cryptcow
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 3240 KB]
   Test 2: TEST OK [0.000 secs, 3240 KB]
   Test 3: TEST OK [0.000 secs, 3240 KB]
   Test 4: TEST OK [0.000 secs, 3240 KB]
   Test 5: TEST OK [0.000 secs, 3240 KB]
   Test 6: TEST OK [1.377 secs, 3240 KB]
   Test 7: TEST OK [0.054 secs, 3240 KB]
   Test 8: TEST OK [1.026 secs, 3240 KB]
   Test 9: TEST OK [1.782 secs, 3240 KB]
   Test 10: TEST OK [1.971 secs, 3240 KB]

All tests OK.
Your program ('cryptcow') produced all correct answers!  This is your
submission #37 for this problem.  Congratulations!

posted @ 2011-08-10 20:36 Climber.pI 閱讀(250) | 評論 (0) | 編輯 收藏

Problem List (7.26 ~ 8.5)

7.26

最長公共子序列l(wèi)cs, O(N^2)
f[i][j] = max{f[i-1][j], f[i][j-1], f[i-1][j-1]+1(if A_i==B_j)}
初始化f[_][0] = f[0][_] = 0

7.27

編輯距離edit, O(N^2)
f[i][j] = min(f[i][j-1] + 1, f[i-1][j] + 1, f[i-1][j-1] + !(A_i==A_j))
初始化f[i][0] = f[0][i] = i
*參考[這里]http://en.wikipedia.org/wiki/Levenshtein_distance
*狀態(tài)轉(zhuǎn)移過程中, 充分不一定最優(yōu), 必要才是最優(yōu); 事實(shí)上邊界條件總有其具體意義
*[相關(guān)]http://www.matrix67.com/blog/archives/333

最短回文串palindrome[poj 1159], O(N^2)
1.套用lcs, O(N^2), 60
f[i][j] = max{f[i-1][j], f[i][j-1], f[i-1][j-1]+1(if A_i==B_j)}
初始化f[_][0] = f[0][_] = 0, n - f[n][n]即為答案
*利用滾動(dòng)數(shù)組優(yōu)化, 空間復(fù)雜度O(N), 80
*關(guān)鍵語句k = 1 - k, 注意在內(nèi)層循環(huán)外
2.套用edit, O(N^2), 30
f[i][j] = min(f[i][j-1] + 1, f[i-1][j] + 1, f[i-1][j-1] + 2*!(A_i==A_j))、
初始化f[i][0] = f[0][i] = i, f[n][n]/2即為答案
3.O(N^2), 30
f[i,j]表示將Ai..Aj變?yōu)榛匚拇淖钚〈鷥r(jià)，則
f[i][j] = f[i+1][j-1] (若Ai=Aj)
    min(f[i+1][j],f[i][j-1])+1 （若Ai<>Aj）
4.利用位運(yùn)算優(yōu)化
http://www.csse.monash.edu.au/~lloyd/tildeStrings/Alignment/86.IPL.html

硬幣找零coin[完全背包], O(N^2)
f[j] = min(f[j], f[j-c[i]]+1)
初始化f[0] = 0, f[1..T] = INT_MAX
*注意下標(biāo)非零 和 INT_MAX的溢出

7.28

導(dǎo)彈攔截missile[LIS + 二分], O(NlogN)
(1)二分查找O(logn)
f[i] = max(f[j] + 1) (j < i)
d[i] = min(f[k]) (f[k] == i)
易知d[i]單調(diào), 因而可以利用二分查找降低復(fù)雜度, i最大值即LIS長度為t, 那么
i)  f[i-1] < k <= f[i] (1 <= i <= t)
ii) 若k > 任意f[], 則f[t+1] = k;
iii) 若!k, 則f[1] = k;
*例子參見[這里]http://www.matrix67.com/blog/archives/112
[代碼實(shí)現(xiàn)]
//情況ii和iii需要單獨(dú)處理
x = 1; y = t;
while (x <= y){
 m = (x + y)/2;
 if (f[m-1] < k && k <= f[m]) break;//對于最長上升子序列和最長不下降子序列判定條件不明???
 //if (f[m-1] < k && k <= f[m]) return m;
 else if (k > f[m]) x = m + 1；
 else y = m - 1;
 //return x;
}
*利用注釋, 可以避免對情況ii的單獨(dú)處理LIS的方案, 記錄方案需要使用pre數(shù)組, 范例不知???
*需要注意的是, f數(shù)組給出的并非是一個(gè)
(2)最少鏈劃分 = 最長反鏈長度(關(guān)于偏序集, 參見《組合數(shù)學(xué)》P73)
[Dilworth定理]令（X,≤）是一個(gè)有限偏序集，并令m是反鏈的最大的大小。則X可以被劃分成m個(gè)但不能再少的鏈。

最長不下降子序列l(wèi)is[LIS + 二分], O(NlogN)
對[1..k-1][k+1..n]兩個(gè)序列分別進(jìn)行一次LIS即可.
*問題的關(guān)鍵之處在于第一次理解不徹底和浮躁, 以及對于困難程度的不合理估計(jì).

7.29

加分二叉樹tree[區(qū)間 + 記錄方案], O(N^3), 20min
f[i][j] = max(f[i][k-1] * f[k+1][j] + A[k]) (i <= k <= j)
初始化f[i][i] = A[i], f[i+1][i] = 1
[記錄方案]pa[i][j] = k, 遞歸即可, [邊界]pa[i][j] == i 或者 j, 以及i == j的情況

整數(shù)劃分separate[區(qū)間 + 記錄方案], O(N^3), 2h
f[k][i]表示序列1..i分成k段的最大值
f[k][i] = max(f[k-1][j-1] * A[j][i])
pa[k][i] = j
初始化f[1][_] = A[1][_], 其他f[][] = -1
*注意等號情況同樣需要更新
if (f[K][i] <= f[K-1][k-1] * A[k][i])
 f[K][i] = f[K-1][k-1] * A[k][i],
 pa[K][i] = k; //記錄方案
*將[pa[k][i], i]加入答案, 遞歸[1, pa[k][i]-1], [邊界] k == 0
*在Win下使用long long占位符為"%I64d", 在Linux下占位符為"%lld", 考試中利用<fstream>避開占位符問題

凸多邊形的三角剖分division[區(qū)間]
f[i][j] = max{f[i][k] + f[k][j] + w(i, j, k)} (i < k < j)
初始化1<=i-j<=2的f只為0, 其他為-1
*表達(dá)式中同時(shí)出現(xiàn)long long和int的話, 會(huì)自動(dòng)轉(zhuǎn)換為int
*只過了6個(gè)點(diǎn), 原因不知 -> 數(shù)據(jù)錯(cuò)誤, 最后4個(gè)點(diǎn)output一樣
*各種神牛們普遍指出沒有考慮i>j的情況 -> 怎么寫???

機(jī)器分配machine[區(qū)間], O(N^3)
f[i][j] = max(f[i-1][k] + A[i][j-k]) (0 <= k <= j)
初始化f[][] = 0, f[i][j] = max(f[i][j], A[i][j])
*注意讀題"第i個(gè)公司分配j臺(tái)機(jī)器的盈利", 不是分配第j臺(tái)機(jī)器的盈利

裝箱問題box[分組背包], O(N^2), 30min
f[i][j] = max{f[i-1][j], f[i-1][j-c[i][k]] + w[i][k]}
初始化f[][] = 0
*讀題時(shí)注意變量的對應(yīng)關(guān)系
*注意本題中背包不一定要裝滿

7.31

最長前綴prefix[判斷性dp], O(kN), 70min
f[i] |= f[i - len[j]] & check(i - len[j] + 1, j) (1 <= i,j <= n)
初始化f[] = 0, check(x,y)表示主串[x,x+len[y]-1]和前綴y是否相同
*弄錯(cuò)j和len[j], 注意方程的字母指代, 以及實(shí)現(xiàn)中的字符指針位置, 注意靜態(tài)查錯(cuò)[30min]
*[8.4優(yōu)化]把check函數(shù)直接寫在循環(huán)中, 如果f[i] == 1直接break -> 依舊超時(shí)三個(gè)點(diǎn)
*[8.5優(yōu)化]i的上限為min(n, ans + 20), 更新f[i]的時(shí)候記錄ans即可 -> AC
8.1

關(guān)鍵子工程project[DAG最長路], 70min
f[i] = max(f[j] + w[i]) (G[j][i] == 1)
初始化f[i] = w[i]
記錄方案, 利用f[i] == w[i] + f[j] (G[j][i] == 1)
*利用定義求拓?fù)渑判? 輸出方案可以利用隊(duì)列將遞歸轉(zhuǎn)化為迭代, 無解情況用flag標(biāo)記(inq數(shù)組表示是否在隊(duì)列中)
*在紙上寫出關(guān)鍵部分的代碼, 兩倍行距(比如遞推或者記憶化函數(shù), 輸出方案的函數(shù))

8.2

三角蛋糕trigon[坐標(biāo)dp], 130min
[做法1](需保留空格)
f_[i][j]表示以(i, j)為頂點(diǎn)的Rt△的最大邊長
對于倒三角形, 自右向左 f1[i][j] = min(f1[i+1][j], f1[i][j+1]) + 1
    自左向右 f2[i][j] = min(f2[i+1][j], f2[i][j-1]) + 1
對于正三角形, 自右向左 f1[i][j] = min(f1[i-1][j], f1[i][j+1]) + 1
    自左向右 f2[i][j] = min(f2[i-1][j], f2[i][j-1]) + 1
初始化, f[][] = 0(A[][] = '#'), f[][] = 1(A[][] = '-'); min(f1[i][j], f2[i][j])^2的最大值即為答案
[做法2](不需保留空格)
f[i][j]表示以(i, j)為頂點(diǎn)的△的最大高度
對于倒三角形, f[i][j] = min(f[i-1][j], f[i-1][j+1], f[i-1][j+2]) + 1
對于正三角形, f[i][j] = min(f[i+1][j], f[i+1][j-1], f[i+1][j-2]) + 1
初始化, f[][] = 0(A[][] = '#'), f[][] = 1(A[][] = '-'); min(f[i][j])^2即為答案
*輸入需保留空格, 卡了30min(排除ASCII為10或13的字符即可)
*沒有考慮正方向, 大約2h時(shí)對照std發(fā)現(xiàn)
*有兩個(gè)點(diǎn)數(shù)據(jù)錯(cuò)誤, 對照std后發(fā)現(xiàn)std僅當(dāng)橫坐標(biāo)為奇數(shù)是考慮倒三角形, 橫坐標(biāo)為偶數(shù)時(shí)考慮正三角形, 而題目中無此限制
*學(xué)習(xí)利用批處理對拍的寫法
@echo off
:again
gen
trigon
trigon_me
fc trigon.out trigon_me.out > nul
if not errorlevel 1 goto again

選課course[樹形dp]
[做法1]多叉轉(zhuǎn)二叉
f[i][j]表示以i為根節(jié)點(diǎn)的樹中, 選擇j門課
f[i][j] = max(f[i.r][j], f[i.l][k] + f[i.r][j-k-1] + i.v) (0<=k<j)
初始化f[][] = 0
*無法記錄方案 -> gXX表示比較困難
[做法2]泛化物品
??? -> 想撞墻 -> 需要學(xué)習(xí)

通向自由的鑰匙key[樹形dp], 150min, zoj 2280
f[i][j]表示以i為根節(jié)點(diǎn)的數(shù), 花費(fèi)能量為j時(shí)可以拿到的最多的鑰匙數(shù)
f[i][j] = max(f[i.r][j], f[i.l][k] + f[i.r][j-k-i.c] + i.v) (o<=k<=j-i.c)
初始化f[][] = -1, 邊界處理f[i][j] = 0(i<=0 || j<0)
*記錄各點(diǎn)鄰接矩陣, 利用dfs構(gòu)造樹(注意處理后取消鄰接), 并多叉轉(zhuǎn)二叉 -> 30min
*對于f[i.r][j]不必在記憶化搜索函數(shù)中遍歷所有兄弟, 只遍歷最近的即可
*注意讀題, 出發(fā)點(diǎn)為1, i.c和i.v非負(fù) -> 1.5min
*注意靜態(tài)查錯(cuò), 如記憶化搜索中dp(i, j)打成f(i, j)的情況
*覺得比較暈的時(shí)候等一下再調(diào)題, 可以先干點(diǎn)別的, 這樣可以減少時(shí)間的浪費(fèi)

警衛(wèi)安排security[樹形dp], 100min
[狀態(tài)]
f[i][0]表示以i為根節(jié)點(diǎn), 并在i安排警衛(wèi)的最小花費(fèi)
f[i][1]表示以i為根節(jié)點(diǎn), i的父節(jié)點(diǎn)已安排警衛(wèi)的最小花費(fèi)
f[i][2]表示以i為根節(jié)點(diǎn), i的子節(jié)點(diǎn)已安排警衛(wèi)的最小花費(fèi)
[方程]
f[i][0] = Σmin(f[i.son][0], f[i.son][1], f[i.son][2]) + i.v
f[i][1] = Σmin{f[i.som][0], f[i.son][2]} (i不是樹的根節(jié)點(diǎn))
f[i][2] = min{Σmin{f[i.son][0], f[i.son][2]}(i.son != k) + f[k = i.son][0]}
[初始化]
對于葉節(jié)點(diǎn), f[i][0] = i.v, f[i][1] = 0, f[i][2] = i.v
對于其他值, f[][] = -1
*對于根節(jié)點(diǎn)的尋找, 利用prev[i]記錄i的前驅(qū), 若!prev[i], 則i為樹根
*結(jié)合批處理和makedata以及小范圍暴力程序, 可以有效地避免各種錯(cuò)誤及極端情況 -> 需要學(xué)習(xí)搜索
*對于這類題目, 思考的關(guān)鍵在于分類寫出方程, 并注意方程的邊界條件(類似:tyvj 沒有上司的舞會(huì))
*對于樹形dp, 存在兩種類型; 一種是對于加權(quán)路徑長度限制, 另一種則是求加權(quán)最值

8.4

青蛙的煩惱frog[區(qū)間dp]
初看是最小生成樹問題, 但是此題有幾個(gè)特別的性質(zhì):
1.以1號荷葉為起點(diǎn), 終點(diǎn)不定
2.遍歷荷葉的最短路徑是一條鏈
3.題目給出的坐標(biāo)順序是一個(gè)順時(shí)針方向的多邊形
4.最短路徑不相交(畫一個(gè)四邊形, 利用三角形性質(zhì)可以觀察到)
根據(jù)性質(zhì)1和2, 容易得出O(N^3)的方程, 很明顯會(huì)超時(shí)
f[i][j] = min(f[k][j-1] + d[i][k]) (i!=k)
-f[i][j]表示以i為起點(diǎn), 長度為j的最短路徑, 初始化f[i][1] = 0
進(jìn)而考慮性質(zhì)3和4, 因而對于點(diǎn)1, 只能選擇相鄰的點(diǎn)2和n, 可以得到O(N^2)的方程
f[i][j][0] = min{f[i+1][j-1][0] + d[i][i+1], f[i+1][j-1][1] + d[i][i+j-1]}
f[i][j][1] = min{f[i][j-1][1] + d[i+j-1][i+j-2], f[i][j-1][1] + d[i+j-1][i]}
-f[i][j][0]表示以i為起點(diǎn), 長度為j的最短路徑, f[i][j][1]表示以i為終點(diǎn), 長度為j的最短路徑, 初始化f[][1][] = 0
-一個(gè)實(shí)現(xiàn)上的小優(yōu)化, 保證d[i][j](i<j)
*注意靜態(tài)查錯(cuò), 區(qū)別變量名, 思考算法的過程應(yīng)該長于調(diào)試的過程
*修正了測試點(diǎn)6

火車進(jìn)站train[線性dp], 70min
1.M <= 3 -> 可以分類討論
2.只存在一條軌道, M只能決定軌道的長度 -> 如果同時(shí)在軌道中, i在j前的必要條件是i.s<=j.s和i.t<=j.t
3.小站工作人員可以任意安排這些火車進(jìn)站的先后排列 -> 記憶化搜索
4.小站允許幾輛火車同時(shí)進(jìn)站或出站 -> 所有條件都可取等號
M = 1, f[i] = max(f[j] + 1)    (i.t <= j.s)
M = 2, f[i][j] = max(f[j][k] + 1)  (i.t <= k.s)
M = 3, f[i][j][k] = max(f[j][k][l] + 1) (i.t <= l.s)
初始化f = 0, 利用vis記錄是否計(jì)算過, 各下標(biāo)互不相等
*枚舉過程中注意剪枝, 利用i!=j和i.s<=j.s,i.t<=j.t逐層處理即可
*[讀題]明確要求的是什么, 存在哪些條件, 寫list
*[未驗(yàn)證]先對以進(jìn)站時(shí)間為第一關(guān)鍵字, 出站時(shí)間為第二關(guān)鍵字進(jìn)行快排, 然后直接遞推, 下標(biāo)滿足i < j < k < l

快餐問題meal[資源分配(不妨認(rèn)為是背包)dp + 貪心優(yōu)化] -> 類似, usaco 3.4.4 rocker
f[k][i][j]表示k條生產(chǎn)線生產(chǎn)i個(gè)漢堡, j個(gè)薯?xiàng)l時(shí)生產(chǎn)飲料的最大值, p[k][i][j]表示第k條生產(chǎn)線, 其他同.
f[k][i][j] = max{f[k][i-ki][j-kj] + p[k][i][j]}
sum[i] = sum[i-1] + A[i]
初始化f[1][i][j] = p[1][i][j], f[2..n][i][j] = -1, 復(fù)雜度O(N*100^4)
幾個(gè)優(yōu)化
1.注意到每種物品總數(shù)小于100, 最大產(chǎn)量的上限是lim = min(100/a, 100/b, 100/c, sum[n]/(a*p1+b*p2+c*p3))
2.為了避免數(shù)組越界, i的上限是min(lim*a, sum[n]/p1), j的上限min(lim*b, (A[k] - i*p1)/p2);
ki的上限min(i, A[k]/p1), kj的上限min(j, (A[k] - ki*p1)/p2) -> 對于逗號右邊, 其實(shí)就是ki*p1+kj*p2<=A[k]
3.將程序中的min/max用if語句替代
4.對于每一套生產(chǎn)線, 盡量成套生產(chǎn)
[反例]
1 1 1
2 3 7
3
15 16 17
貪心可得最大值為3, 實(shí)際上15 = 7 + 3 + 3 + 2, 16 = 7 + 3 + 2 + 2 + 2, 17 = 7 + 7 + 3, 最大值為4;
利用優(yōu)化1和2可以過5個(gè)測試點(diǎn), 優(yōu)化3可以進(jìn)一步優(yōu)化時(shí)間常數(shù), 利用優(yōu)化4可以過9個(gè)測試點(diǎn)
AC程序參見[此文]http://hi.baidu.com/zijingningmeng/blog/item/2761617e2afe7ae32e73b3b3.html
*調(diào)試過程中的主要問題是邊界溢出(沒有區(qū)分是否計(jì)算過), 變量名寫錯(cuò)
*網(wǎng)上有說法表示去掉每種物品的件數(shù)限制后, 題目變成網(wǎng)絡(luò)流 -> gXX證偽
*比賽的話, 不妨小數(shù)據(jù)(n<5)DP, 大數(shù)據(jù)(n>=5)貪心, 這樣應(yīng)該可以得到超過一半的分?jǐn)?shù)

卡車更新問題truck, O(N^2), 1h
f[i][k]表示第i年某車已使用了k年
f[i][k] = max{f(i+1, 1) + R[0] - U[0] - C[k], f(i+1, k+1) + R[k] - U[k]}
初始化f[][] = -1, 邊界條件f[i][k] = 0(i>N,k>K), 利用記憶化搜索實(shí)現(xiàn)
記錄方案利用bool型數(shù)組prev[i][j][k]記錄是否購買新車, 遞歸即可
*盡可能不換新車
*利用樣例構(gòu)造樹, 寫出狀態(tài)即可得到方程
*測試點(diǎn)1存在等價(jià)方案, 已修正數(shù)據(jù)(可能需要Special Judge)
*f[i][j][k]中i和k可以唯一確定狀態(tài), 因而可以去掉中間1維

選課course[樹形dp + 記錄方案], 多叉轉(zhuǎn)二叉實(shí)現(xiàn)
f[i][j]表示以i為根節(jié)點(diǎn)的樹中, 選擇j門課
f[i][j] = max(f[i.r][j], f[i.l][k] + f[i.r][j-k-1] + i.v) (0<=k<j)
初始化f[][] = 0
[記錄方案]
利用print(i, j)遞歸, vis[i][j]表示是否已遍歷, [邊界]i∈[1, m], j∈[1, n]
right[i][j]表示f[i][j]是否等于f[i.r][j]
prev[i][j] = k表示f[i][j]由f[i.l][k],f[i.r][j-k-1]推得, 這時(shí)需記錄p[i] = 1
從1到n判斷p[i]直接輸出即可.

8.5

廣場鋪磚問題floor[狀壓dp], 2h
f[i][S] = Σf[i-1][S'] (S由S'推得)
初始化f[1][0] = 1, f[h+1][0]即為答案
對于每個(gè)f[i-1][S']利用dfs(當(dāng)前行i, 當(dāng)前行狀態(tài)s1, 下一行狀態(tài)s2, 當(dāng)前行指針k)尋找S
if(!(s2 & 1<<k) && !(s2 & 1<<(k+1)))
 dp(i, s1, s2, k + 2);//存在連續(xù)兩個(gè)空位, 即橫放
dp(i, s1, s2 ^ (1<<(k)), k + 1);//對當(dāng)前位取反, 即豎放
利用int保存每一位的擺放方式, 1表示當(dāng)前行被上一行占用, 0表示當(dāng)前行未被占用
[邊界]k = 0, 遞歸過程中k > w則退出

硬木地板floor2[狀壓dp]
f[i][S] = Σf[i-1][S'] (S由S'推得)
初始化f[1][0] = 1, f[h+1][0]即為答案
*實(shí)現(xiàn)無能, 最終放棄 -> 我應(yīng)該去學(xué)位運(yùn)算優(yōu)化BFS -_-
*魚?！稜顟B(tài)壓縮》理解不能, NOI導(dǎo)刊朱全民文章code不全.
*耗時(shí)最長的題目往往不是表面上的難題, 而是那些被簡單估計(jì)的難題

posted @ 2011-08-05 20:51 Climber.pI 閱讀(577) | 評論 (0) | 編輯 收藏

Problem List (7.13 ~ 7.20)

posted @ 2011-07-21 15:55 Climber.pI 閱讀(313) | 評論 (0) | 編輯 收藏

LGOI 2011 初賽備考

記得去年在紙上寫過一份這樣的東西，迎來的是exhaustive fail.需要明確復(fù)習(xí)重點(diǎn)是數(shù)據(jù)結(jié)構(gòu)和算法, 考場上要注意出題規(guī)律和草稿的清晰性. 簡單復(fù)習(xí)大概用了6個(gè)番茄鐘.

1.表達(dá)式樹
[中綴] (a + b) * c + d * c
(((a + b) * c) + (d * c))
[前綴] +(*(+(a b) c) * (d c))
+ * + a b c * d c
[計(jì)算方法1] 壓棧(前綴 -> 從后向前)
[計(jì)算方法2] 括號(opt后) -> 中綴

2.二分查找的平均次數(shù) log(n+1)-1

3.heap的實(shí)現(xiàn)
[up] while(k > 1) 比較 交換(h[k], h[k/2])
[down] while(2 * k <= n) 比較 交換(h[k], h[2k + 1(小于n的話)])

4.排序算法的穩(wěn)定性
[穩(wěn)定]插入排序、冒泡排序、歸并排序、分配排序(桶式、基數(shù))
[不穩(wěn)定的]直接選擇排序、堆排序、shell排序、快速排序都是不穩(wěn)定的排序算法。
[穩(wěn)定排序]http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/chapter7/01/05.html
[排序原理]http://hi.baidu.com/cuifenghui/blog/item/0587932b039557f9e7cd4051.html

5.出棧序列
一個(gè)數(shù)列滿足條件，當(dāng)且僅當(dāng)每一段單調(diào)遞減數(shù)列要么不存在空缺（即為公差-1的等差數(shù)列），要么它的空缺在之前全部已經(jīng)出現(xiàn)。

[充要條件]若出棧序列合法，則一定不存在1<=i<j<k<=n，使s[j]<s[k]<s[i]

6.鄰接表的插入操作(鏈表的插入)
next[e] = first[u[e]]; first[u[e]] = e;

7.邏輯表達(dá)式恒值
注意符號, 轉(zhuǎn)化為分情況表示的函數(shù)

8.叉積的計(jì)算(特別注意第二個(gè)負(fù)號)
|i j k|
|a1 a2 a3|=i|a2 a3|-j|a1 a3|+k|a1 a2|
|b1 b2 b3|  |b2 b3|  |b1 b3|  |b1 b2|

9.閱讀程序注意意圖, 草稿的清晰度(減少亂劃)

[RAM]http://baike.baidu.com/view/3558.htm
隨機(jī)存儲(chǔ): 訪問時(shí)間與位置無關(guān)
[Hash]http://www.nocow.cn/index.php/%E6%95%A3%E5%88%97%E8%A1%A8
[拓?fù)渑判?DAG)]http://zh.wikipedia.org/wiki/%E6%8B%93%E6%92%B2%E6%8E%92%E5%BA%8F\

posted @ 2011-05-14 19:21 Climber.pI 閱讀(4734) | 評論 (0) | 編輯 收藏