3.19
MAR11 Bronze Division Analysis
charms 邊讀入邊處理, 由于讀題失誤沒有想到
pathfind -
spiral -
MAR11 Silver Division Analysis
meetplace[AC] O(N^2)的比較最早公共元素常數較小, 最大測試點0.019s
[算法1] O(N^2 + NM)
O(N^2)預處理, 枚舉公共祖先j, 計算dist(a, j)+dist(b, j)的最小值; O(NM)針對每次詢問取最小值.
[算法2] O(N + MN) 最大測試點0.03s
O(N)的預處理, 計算不同結點間距離, 設置表示變量; O(MN)的循環比較最小值.
packdel[-2] SPFA, INF值過小, 使用循環隊列后[-1]
[std] Dijkstra + Heap, O(E lg V)
[實現]gXX指出, 此題卡SPFA
rotsym O(N^4), 暴力模擬
[std] O(N^2lgN) 生成任意兩點的中點, 排序, 確定相同坐標區間長度j-i, 累加C(j-i, 2).
[實現]gXX曰:(1)數組開大 -> Error127 (2)long long輸入使用%lld
3.21
fence6 研究sinya的質點系做法(Floyd求最小環)
3.22
ditch 23min AC 復習最大流增廣路算法的鄰接矩陣+BFS實現
fence6 AC 對拍sinya程序
3.23
ditch 11min AC 復習最大流增廣路算法的鄰接矩陣+BFS實現
fence6 22min AC 大量參考昨日程序
(1)質點邊賦值錯誤
(2)循環取最小環G[k][rn[i][j]]打反
*機械記憶而非深入理解機理, 易忘
*Ctrl + click函數 -> 函數的實現代碼
學習Floyd求最小環
for (k = 1; k <= n; k+=){
for (i = 1; i <= k-1; i++)
for (j = 1; j <= k=1; j++)
ans = min(ans, G[i][j] + G[i][k] + G[k][j]);
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
}
3.28
fence6 40min AC 復習Floyd求最小環
[Linker error] undefined refetence to 'WinMain@16'
ld returned 1 exit status
-> main() 打反
3.29
fence8 40min
*fscanf 注意尋址&
3.30
buylow 高精度 & 判重無能
4.6
msquare 位運算判重, 未輸出路徑
4.7
msquare AC 位運算 35MB[MLE]
[4.10]位運算判沖實質與flag[][][][]..相同 -> MLE
4.11
如何估算答案長度
4.13
自動進行操作A, 原因不明.
如何避免頹廢狀態 ???
4.14
msquare AC
memcmp() 進行剪枝, 效率提升約60%;
*借鑒回溯思想, 枚舉每種情況后應置換為原始狀態.
[算法簡述]
print() 輸出路徑, 注意方向.
encode() Contor展開編碼判重.
trans() 置換表, 需要建立雙方向表.
bfs() 隊列使用state類型 -> 空間復雜度換編程復雜度
5.1
U S Open 2011 Silver Division
花了0.5h讀題, 調了1.5h后第一題放棄了.
cornmaze
加了點花樣的BFS最短路, 注意事項:
(1)瞬間移動用置換表解決, 需要注意新位置距離賦值
(2)(x,y)的代表關系
cowcheck
博弈問題, 沒找到先手必敗態, 簡單分析的結果是初始狀態在對角線附近的話先手必敗
forgot
字串匹配, 似乎可以爆搜.
llang
原諒我找不到合適的模型描述