3.12
MAR11 Bronze Division [AK]
[戰(zhàn)術(shù)]先通讀試題，想到大概算法，然后具體實施.測試了極限數(shù)據(jù).
[注意]題目描述細節(jié); 字母打錯;
讀題時間 27min
charms 69in
[大意]題目中給出一條鏈子，然后從中間吊起. 鏈子上還掛有鏈子，求每個鏈子在重力作用下的末端值.
[算法]O(N),做一個數(shù)組映射吊起后鏈子的位置，逐個鏈子計算，輸出.
pathfind 110min
[大意]給出一個鄰接矩陣和起點，算最短路.
[算法]O(N^2), bfs求最短路. 輸出時利用flag變量, flag=0時輸空格, 反之不輸出.
spiral 53min
[大意]蛇形數(shù)陣
[算法]O(N^2), 若當前方向可前進, 繼續(xù)填充; 反之，按照 右->下->左->上的順序換方向.
3.13
USACO Contest get to Silver Division Success!
MAR11 Silver Division
[戰(zhàn)術(shù)]通讀題目，沒有設(shè)計進一步的數(shù)據(jù).
讀題時間 22min
meetplace 90min
[大意]尋找樹上任意兩節(jié)點的最近公共祖先.
[算法]O(M*N^2), 期望得分30~50.
利用數(shù)組模擬鏈表存儲樹，對于每次詢問用O(N^2)的時間用數(shù)組循環(huán)查找最近公共祖先.
[進一步的改進]把循環(huán)查找公共祖先的時間降到O(NlogN), 總復雜度O(N^2logN), 可以AC. 具體方式不明
packdel 44min
[大意]稀疏的無向圖最短路
[算法]O(2N), 期望得分100, 裸的SPFA, 利用臨界表存儲.
spiral 63min
[大意]給出N個坐標，判斷任意四點可成平行四邊形的個數(shù)(包括重合情況).
[算法]O(N^4), 期望得分10~30, 操作數(shù)為C(4,N), 考慮常數(shù)的話N上限為200
利用四重循環(huán)生成子集(元素個數(shù)為4), 坐標判斷(討論AB, AC, AD為對角線的情況, A.x + B.x == C.x + D.x, y同理), 計數(shù)輸出.
[進一步的改進]無
3.14
fence6 unAC
質(zhì)心法，研究樣例，發(fā)現(xiàn)缺少判斷條件
3.15
ditch AC 學習最大流增廣路算法的鄰接矩陣實現(xiàn)，基本照抄lrj白書
*兩點多邊處理方法：合并
？如何用鄰接表實現(xiàn)
3.16
ditch 30min AC 復習最大流增廣路算法的鄰接矩陣+BFS實現(xiàn)
*使用memset清空數(shù)組, 應在任何操作之前
*文件名(潛在問題)
stall4 38min AC 二分圖最大匹配的網(wǎng)絡(luò)流實現(xiàn)[參照Section 4.2.0 Text]
*起點和終點到對應點的流量限制是1而不是無限大, 因為流量限制對邊而言
*注意兩個集合的點的標號
3.17
ditch 15min AC 復習最大流增廣路算法的鄰接矩陣+BFS實現(xiàn)
*邊權(quán)回溯修改錯誤
job 40min -