Climber.pI的OI之路

NOIp 2011 初賽備考

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

Problem List (9.7 ~ 9.29)

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

USACO Training Chapter 4 ~ 6 Summary

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

Problem List (8.13 ~ 8.21)

8.13

prime3[DFS + 手動指定搜索順序], 4h, 0.1s左右出解
1.構造所有五位素數, 可以先做一個313以內的素數表, 試除即可. 注意素數末尾不是偶數和0.
*官方題解中枚舉6n-1和6n+1, 同時判斷末位5和0, 從素數7開始枚舉即可, 枚舉量進一步減少
2.手動指定搜索順序, 對于每種情況分別處理, 代碼很長. 對角線優先, 末尾數組優先(顯然素數末尾數字只能是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)可計算位(即該行或列或對角線已經填了4個數). sum < 10, 判斷是否為素數, dfs下一層時, sum-下一層已填充位置.
4)對于由情況3)轉移而來的狀態, 需要檢查sum >= 0
*可以把情況1)和2)分別合并, 利用數組指定順序亦可(代碼長度可能變化不大)
*官方題解在這里以行\列\對角線為單位填數, 需要預處理某些位為某些數的素數.
3.對保存的結果進行排序, 利用qsort間接排序即可.
*NOCOW上有人寫15重for循環, 效率比這個低10倍. 但是15重for加上縮進實在不好看.

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

shuttle[BFS/數學], 4h
1)BFS做法(n <= 7)
1.利用位運算保存狀態, 1表示'W', 2表示'B'或空格, 附加k表示空格所在位
2.按照字典序轉移狀態(共4種方式), k的方向可以任意理解, 不影響結果. k從0開始, 顯然W只向右, B只向左.
*在草稿紙上寫好狀態轉移的具體代碼(if部分), 注意變量
*讀題, 一開始認為棋盤長度不超過12于是就BFS, 實際上棋盤長度不超過25, 位運算保存狀態會爆內存. 此外輸出限制每行20個數字.
2)數學 by NOCOW
我們憑借極其敏銳的眼光發現這組序列為
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
　　*奇數組為降序列，偶數組為升序列
　　*對于第i組(1<=i<=n+1),若為奇數組則首項為n+i，偶數組則首項為n-i+2
對于第n+2~2n+1組，可以由對稱性求出.
*官方題解做法類似數學做法, 觀察后得出每次都是空格向右移動2格, 直到不能移動(如果不能向右移動1格的話轉向)或者達到狀態.
*如果輸出字典序最小解, 不妨找規律; 如果輸出所有解, 只能搜索.

milk6[最小割+貪心], 按計劃cheat.

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

8.14

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

8.15

調教laptop.

8.16

frameup[拓撲排序], 20min -> 參照 北極南天星 的題解, 意簡言賅
構圖這里不再贅述. 注意到題目要求輸出拓撲序列, 長度一定, 并不像DP中出現明顯層次性.
dfs狀態(當前序列長度), 按照定義做: 每次找入度為0的點u, 然后將于此點存在邊的點v入度-1. 直到所有點都在序列中.
*dfs按照字母升序搜索, 即滿足題目順序要求.
*構圖統計每個點u入度時注意判重, 存在多個點滿足條件.

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]為起點的序列的最大長度, 以j-i為階段, 注意f[i][j]<=j-i. 注意到狀態之間存在依賴性, 各階段間不存在依賴性, 只需保存當前狀態. 不斷更新答案即可.
*不能直接二分, 答案可能小于j-i, 無法寫判定函數 -> 如果對于每個j-i的長度序列單調不下降的話還是可以二分.

8.17

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

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

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

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

8.18

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

bigbrn[DP], 30min
f[i][j]表示以(i, j)為右下方頂點的正方形的最大邊長
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, 且該點不進行dp

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

8.19

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

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

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

telecow[網絡流], 按計劃cheat

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

tour[雙進程DP/費用流/刷表法], 3h, O(N^3)
狀態想對了, f[i][j]表示兩個人分別從起點出發到達城市i\j所經過的城市數.
一開始認為方程是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
規定對于任意狀態f[i][j], i > j, 需要注意f[j][k]\f[k][j]必須計算過. 初始化f[1][1] = 1, 其余為0.
*利用strcmp比較字符串即可, memcmp似乎某些情況下會出錯.
*這題和NOIp 08傳紙條的主要區別: 這題是無向圖, 而傳紙條是矩陣. 因而轉移方式不同.
[故事] by BYVoid
這是加拿大IOI93的一道原題。在WC2008中聽吳教授說道，當時參加IOI的選手沒有人了解動態規劃，對這道題束手無策。選手們都用上了最復雜的搜索技巧，有人還寫了雙向搜索，可是都沒有通過。回國后開始研究，最終提出了動態規劃這一算法設計方法，于是動態規劃變成了之后競賽出題的熱點。

8.20

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

cowxor[?]
很容易聯想到最大連續和, 注意到異或運算滿足結合律, 可以利用O(N^2)的時間枚舉每個區間. 但是這題范圍很大, 第6個點就TLE了.

8.21

charrec[DP + 統計 + 記錄方案], 2.5h
注意到題目對于最優解的定義是損壞數據最少, 因而可以考慮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][_]對應的字符)
f[i]表示從第i行到第n行的最少損壞(不同位數). C[i][j]表示從第i行開始連續匹配j行的最小損壞(不同位數), 這里需要返回所對應的字符, 實現時可以利用記憶化.
對于f數組, (n - 19, n]需要初始化為+∞
*可以利用d[i][j][k]表示第i個字符第j行和輸入數據第k行不同位數
*需要注意數組大小, 以及題目中寫出的font.in和給出的font.in不同.

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

twofive[Contor展開], ?h, 全仿std.
1.暴搜 -> 理論6組, 實際4組 -_-
2.類似kimbits, 可以使用康托展開(比較直觀的解說參見白書第10章).
關鍵在于對于一個給定的串, 如何知道小于其前n位的串的方案數. 定義f[a][b][c][d][e]表示方案數. 對于每個字母ch, 如用過, 那么繼續ch+1. 否則枚舉已填位后所有位, 累計方案值.
(數學描述)
若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.
*[數組開小]
  > 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個點
2.參考WC03王知昆論文, 非常好理解
懸線：上端點覆蓋了一個障礙點或達到整個矩形上端的有效豎線. 顯然對于每個懸線擴展得到矩形一定包含答案. 我們可以利用O(RC)的時間得到所有懸線, 因而問題的關鍵在于利用O(1)的時間處理懸線. 這里可以使用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)}即為答案
*北極天南星 和 論文 似乎都有一個地方把 min 打成了 max.
*i和j不能隨意交換, 需要注意所對應的下標范圍.(#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]之后需要高精度.
*推導方法待研究.
*求哈密頓回路個數, 可以使用基于連通性的SC.

cowxor[枚舉 + 優化], 1h, 全仿std

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

寫在USACO通關之后

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

Problem List (8.6 ~ 8.12)

posted @ 2011-08-18 12:31 Climber.pI 閱讀(252) | 評論 (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 閱讀(249) | 評論 (0) | 編輯 收藏

Problem List (7.26 ~ 8.5)

7.26

最長公共子序列lcs, 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
*狀態轉移過程中, 充分不一定最優, 必要才是最優; 事實上邊界條件總有其具體意義
*[相關]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]即為答案
*利用滾動數組優化, 空間復雜度O(N), 80
*關鍵語句k = 1 - k, 注意在內層循環外
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變為回文串的最小代價，則
f[i][j] = f[i+1][j-1] (若Ai=Aj)
    min(f[i+1][j],f[i][j-1])+1 （若Ai<>Aj）
4.利用位運算優化
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
*注意下標非零 和 INT_MAX的溢出

7.28

導彈攔截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]單調, 因而可以利用二分查找降低復雜度, 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
[代碼實現]
//情況ii和iii需要單獨處理
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的單獨處理LIS的方案, 記錄方案需要使用pre數組, 范例不知???
*需要注意的是, f數組給出的并非是一個
(2)最少鏈劃分 = 最長反鏈長度(關于偏序集, 參見《組合數學》P73)
[Dilworth定理]令（X,≤）是一個有限偏序集，并令m是反鏈的最大的大小。則X可以被劃分成m個但不能再少的鏈。

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

7.29

加分二叉樹tree[區間 + 記錄方案], 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的情況

整數劃分separate[區間 + 記錄方案], 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[區間]
f[i][j] = max{f[i][k] + f[k][j] + w(i, j, k)} (i < k < j)
初始化1<=i-j<=2的f只為0, 其他為-1
*表達式中同時出現long long和int的話, 會自動轉換為int
*只過了6個點, 原因不知 -> 數據錯誤, 最后4個點output一樣
*各種神牛們普遍指出沒有考慮i>j的情況 -> 怎么寫???

機器分配machine[區間], 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個公司分配j臺機器的盈利", 不是分配第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
*讀題時注意變量的對應關系
*注意本題中背包不一定要裝滿

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是否相同
*弄錯j和len[j], 注意方程的字母指代, 以及實現中的字符指針位置, 注意靜態查錯[30min]
*[8.4優化]把check函數直接寫在循環中, 如果f[i] == 1直接break -> 依舊超時三個點
*[8.5優化]i的上限為min(n, ans + 20), 更新f[i]的時候記錄ans即可 -> AC
8.1

關鍵子工程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)
*利用定義求拓撲排序, 輸出方案可以利用隊列將遞歸轉化為迭代, 無解情況用flag標記(inq數組表示是否在隊列中)
*在紙上寫出關鍵部分的代碼, 兩倍行距(比如遞推或者記憶化函數, 輸出方案的函數)

8.2

三角蛋糕trigon[坐標dp], 130min
[做法1](需保留空格)
f_[i][j]表示以(i, j)為頂點的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)為頂點的△的最大高度
對于倒三角形, 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時對照std發現
*有兩個點數據錯誤, 對照std后發現std僅當橫坐標為奇數是考慮倒三角形, 橫坐標為偶數時考慮正三角形, 而題目中無此限制
*學習利用批處理對拍的寫法
@echo off
:again
gen
trigon
trigon_me
fc trigon.out trigon_me.out > nul
if not errorlevel 1 goto again

選課course[樹形dp]
[做法1]多叉轉二叉
f[i][j]表示以i為根節點的樹中, 選擇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]泛化物品
??? -> 想撞墻 -> 需要學習

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

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

8.4

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

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

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

卡車更新問題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), 利用記憶化搜索實現
記錄方案利用bool型數組prev[i][j][k]記錄是否購買新車, 遞歸即可
*盡可能不換新車
*利用樣例構造樹, 寫出狀態即可得到方程
*測試點1存在等價方案, 已修正數據(可能需要Special Judge)
*f[i][j][k]中i和k可以唯一確定狀態, 因而可以去掉中間1維

選課course[樹形dp + 記錄方案], 多叉轉二叉實現
f[i][j]表示以i為根節點的樹中, 選擇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]推得, 這時需記錄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]即為答案
對于每個f[i-1][S']利用dfs(當前行i, 當前行狀態s1, 下一行狀態s2, 當前行指針k)尋找S
if(!(s2 & 1<<k) && !(s2 & 1<<(k+1)))
 dp(i, s1, s2, k + 2);//存在連續兩個空位, 即橫放
dp(i, s1, s2 ^ (1<<(k)), k + 1);//對當前位取反, 即豎放
利用int保存每一位的擺放方式, 1表示當前行被上一行占用, 0表示當前行未被占用
[邊界]k = 0, 遞歸過程中k > w則退出

硬木地板floor2[狀壓dp]
f[i][S] = Σf[i-1][S'] (S由S'推得)
初始化f[1][0] = 1, f[h+1][0]即為答案
*實現無能, 最終放棄 -> 我應該去學位運算優化BFS -_-
*魚牛《狀態壓縮》理解不能, NOI導刊朱全民文章code不全.
*耗時最長的題目往往不是表面上的難題, 而是那些被簡單估計的難題

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

Problem List (7.13 ~ 7.20)

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

LGOI 2011 初賽備考

記得去年在紙上寫過一份這樣的東西，迎來的是exhaustive fail.需要明確復習重點是數據結構和算法, 考場上要注意出題規律和草稿的清晰性. 簡單復習大概用了6個番茄鐘.

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

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

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

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

5.出棧序列
一個數列滿足條件，當且僅當每一段單調遞減數列要么不存在空缺（即為公差-1的等差數列），要么它的空缺在之前全部已經出現。

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

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

7.邏輯表達式恒值
注意符號, 轉化為分情況表示的函數

8.叉積的計算(特別注意第二個負號)
|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
隨機存儲: 訪問時間與位置無關
[Hash]http://www.nocow.cn/index.php/%E6%95%A3%E5%88%97%E8%A1%A8
[拓撲排序(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 閱讀(4732) | 評論 (0) | 編輯 收藏