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