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