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