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