9.7
NOIp03 network[拓撲排序+模擬], 2h
注意讀題, 題目中給出公式C[i] = Σ(W[j][i]*C[j]) - U[i](C[j] > 0), 特別注意成立條件.
把題目中給出的DAG反向, 對于C[i], 計算所有i的后繼即可. 僅按照編號順序輸出大于零的神經(jīng)元, 題目描述有誤.
*注意分析題目, 不要急于敲程序.
*對于DAG上的拓撲排序問題, 一類如本題和project, 直接利用圖; 另一類如frameup, 要輸出完整路徑, 需要按照定義消去點.
9.8
NOIp01 Car的旅行路線[預(yù)處理+最短路], 2h
1.構(gòu)造矩形, 利用點積判斷垂直, 利用平行四邊形坐標(biāo)關(guān)系求第四點坐標(biāo)
2.構(gòu)造圖, 分別處理矩形內(nèi) 和 不同矩形的情況
3.Floyd最短路, 對始末矩形判斷最小值(此處假設(shè)始末矩形不同)
*需要特判始末矩形相同的情況
*注意double的強制轉(zhuǎn)換
9.10
Tyvj Sept月賽(2.5h)
badgers, 0/1背包, 預(yù)計AC.
tree, 排序+亂搞, 看錯題.
沒有考慮深度>2的樹, 似乎需要用到并查集.
number, 模擬, 預(yù)計30
顯然top>=2^(n-1)
register, 沒寫, 只會30.
估計150. -> 50;
9.14
badgers, 二分+貪心, 40min, 1Y
對于n只badgers, 需要的食物總量tot = Σ(H[i] + (n-1)*G[i]), 二分求解即可.
*讀題!
*寫出關(guān)鍵函數(shù)
tree, kruskal變形
利用和kruskal一樣的思想.
1. 對于每個點A分別屬于各自的集合
2. 對邊排序
3. 按順序合并集合, ans += (num[i]*num[j]-1)(c[i]+1)+c[i];
9.26
NOIp10 關(guān)押罪犯[二分+BFS判重], 3h
1. 用鄰接表存儲邊, 可以抽象為addEdge函數(shù)
2. 二分最大值
3. check函數(shù)用BFS染色判重, 枚舉每一個點進行BFS.
*判重可以將數(shù)組初始化為-1, 然后判斷隊列中每個點的顏色是否為-1, 可以避免使用vis數(shù)組.
[注意事項]
1. 題目中僅給出無向邊
2. 標(biāo)記節(jié)點是否已讀 -> 利用color即可
3. 遍歷所有連通分量 -> 枚舉每個點即可, 不必記錄所有滿足條件的邊上的端點
9.27
NOIp10 關(guān)押罪犯, 30min, AC
1. 鄰接表不熟
2. 二分打錯
3. 不理解gXX程序判重原理
[原理]和我的做法一樣, 不同的是gXX程序避免了對每個點重復(fù)染相同顏色, 因而需要進行染色的點必然未訪問.
9.28
NOIp10 關(guān)押罪犯, 10min, AC
1. 鄰接表first沒有初始化
2. 邊界打錯
NOIp10 烏龜棋[DP], 20min, AC
注意到已通過路徑可以用a+2*b+3*c+4*d表示, 因而設(shè)置狀態(tài)為f[a][b][c][d];
f[a][b][c][d] = max{f[a-1][b][c][d], f[a][b-1][c][d], f[a][b][c-1][d], f[a][b][c][d-1]} + A[a+2*b+3*c+4*d];
*注意從第一個格子開始, 故A[0..n-1], f[0][0][0][0] = A[0], 注意下標(biāo)實際意義.
*去年寫錯方程主要是沒有考慮下標(biāo)間練習(xí), 直接套用NOIp05過河方程. 對于相似的題目, 最重要的是找到不同的部分.
9.29
NOIp08 雙棧排序[DFS+剪枝], 50min, 30
1. dfs狀態(tài): (操作序列長度, 已輸入序列長度, 已輸出序列長度, 棧1深度, 棧2深度)
2. 可行性剪枝:
(1) 優(yōu)先彈出符合條件元素(即等于 已輸入序列長度+1)
(2) 找到解后立即退出
*標(biāo)準(zhǔn)做法的構(gòu)造非常神奇, 解釋動機無能. -> 觀點來自gXX