#
9.5
Tyvj 1049 最長不下降子序列
f[j] = max(f[i]) + 1 (A[j] < A[i], 0 < j < i)
9.15
NOIp 2004 chorus
雙向最長不下降子序列
9.16
NOIp 2003 network[UNAC]
拓撲排序
9.23
UVa 10305
拓撲排序[裸] -> 貪心實現
10.2
NOIp 2000 方格取數 O(N^4)
f[i][j][k][l] = max(f[i-1][j][k-1][l], f[i-1][j][j][l-1], f[i][j-1][k-1][l], f[i][j-1][k][l-1])
+ G[i][j] + G[k][l]
NOIp 2008 message O(N^3)
DP, 尋找各維數值關系, 計算確定第四維.
10.3
NOIp 2003 matches
建立數字表(對應match數), 枚舉
10.5
NOIp 2006 budget 分組背包
預處理取消分組(生成各種情況), 01背包
NOIp 2003 tree 樹形+統計DP
f[i][j] = max{f[i][k-1] * f[k+1][j] + a[k]} (i < k < i + l - 1)
10.8
NOIp 2005 river
線性DP+路徑壓縮(利用裴蜀定理)
10.12
NOIp 2004 fruit 小根堆
*復習堆的寫法
10.19
nuggests 裴蜀定理 + 完全背包
10.26
(1)學習Union-set
(2)復習各種排序(qsort, bouble sort, merge)
10.28
1411 學習Prim
11.1
1386 枚舉
11.2
1495 復習Flood fill
11.4
1451 復習DFS
11.10
NOV10 Bronze(daisy, marathon, mathprac)
11.11
water 枚舉
11.14 NOIp 2007 Prob
count qsort + 統計
expand 模擬
game DP(高精度)[30]
11.15
NOIp 2007 game -> 高精度無能, longlong 無能[30]
11.18
NOIp 2004 alpha 暴力枚舉 30
11.19
復習heap, dijkstra, SPFA, Krusal.
11.28 - 11.29
lrj第一次提供題目
12.1
UVa 11374 SPFA+記錄路徑[UNAC]
12.5
DEC10 Bronze(badrand, commas, boolclub)
12.6
1115
12.7 & 12.15
UVa 11374 SPFA+記錄路徑[UNAC]
求教gXX神牛, 對拍無能.
12.18
lrj第二次提供題目(至今未完成)
5.7
p1004 滑雪[2d最長下降子序列]
無思路.
p1005 采藥[簡單01背包], 調了1.5h
[spec,1d] f[j] = max{f[j], f[j - c[i]] + w[i]}, 能夠有效避免f[i][j]中i的指代問題
*2d寫法須注意f[i][j] = f[i-1][j]的值傳遞
for (i = 1; i <= n; i++)
for (j = T; j >= 1; j--)
if (j >= t[i])
f[i][j] = max(f[i - 1][j], f[i - 1][j - t[i]] + w[i]);
else f[i][j] = f[i - 1][j];
p1003 找啊找啊找GF[加強版01背包], 調了1h
讀題分析后發現是0/1背包模型, 時間需要單獨處理.(一開始認為要記錄路徑, 其實不用這么麻煩)
f[m][r] = max{f[m][r], f[m - rmb[i]][r - rp[i]] + 1}
t[m][r] = max{t[m][r], f[m - rmb[i]][r - rp[i]] + time[i]}, 如果f[m]..和f[m-rmb[i]]..相等,注意更新t[m][r]
[補]寫rocker的時候想到一種方法，對于dp，維度往往是需要表示的量數-1，所以關于方程狀態的表示可以從時間復雜度、空間復雜度、需要表示的量數綜合考慮.此題中加上time的話，顯然爆時間，然后從這個方向思考方程.
p1015 公路乘車[線性dp]
f[i] = max{f[i - k] + A[k]} (1 <= k <= 10)
p1011 傳紙條[雙線程dp + 時間降維]
注意讀題, 題目中的來回等價為兩次同時的單向過程
f[x1][y1][x2][y2] = max{f[x1-1][y1][x2-1][y2], f[x1-1][y1][x2][y2-1], f[x1][y1-1][x2][y2-1], f[x1][y1-1][x2-1][y2]}+A[x1][y1]+A[x2][y2]
注意每個數if and only if取一次, f[x1][y1][x2][y2] -= A[x1][y1](x1=x2&&y1=y2)
p1014 乘法游戲[區間dp]
無思路
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
原諒我找不到合適的模型描述
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 -
Welcome to the USACO submission gateway for the Elite 2011 March Competition contest.
You can submit SILVER solutions for three hours (or until the contest ends). The timeclock starts as soon as you read the problems!
僅此慶祝成功晉級的喜悅.
[題外話]因為party正在召開meeting于是非工作時間斷網, 前一周腹痛, Training基本癱瘓.
2.28
camelot 50min UNAC
3.1
camelot
*隊列尾指針r與行寬R重復定義 -> 常量應使用大寫字母
*枚舉坐標打漏
3.7
camelot 45min 16/19
解決輸入問題
3.8
camelot 1h
樣例未過，對拍無問題
3.9
fence4 0.5h 思路混亂
fence8 unAC 無向圖最小環
利用質點系化邊為點，然后用SPFA取最短路.
2.21
butter 17min 1WA
*數組開小
fence 70min 1WA 復習歐拉回路
[充要條件]每個點的度數均為偶數,或只有2點度數為奇數.
寫了1h 70+行的DFS-ID不知哪里錯了，標程十分簡潔.
2.22
fence 10min 1Y 復習歐拉回路
rockers 9WA
*我的方程 f[i][j][k] = max{f[l][j][k-c[i]]+1, f[l][j-1][t-c[i]]+1} (0 < l < i))，O(N^4) -> 沒有考慮不錄的情況
參考了leokan程序 f[i][j][k] = max(f[i-1][j][k], f[i-1][j][k-c[i]]+1, f[i-1][j-1][t-c[i]]+1), O(N^3)
似乎是基于0/1背包問題
*改善狀態轉移從而避免求f[l][][]的最值
2.23
fence 13min 1WA
*深搜過程中不必使用break
*記錄路徑為p[++t] = k
rockers 7min 1Y
*狀態轉移與 待選擇狀態 順序無關
heritage 15min 1Y -> 另:通過指針重建樹,進行遍歷
基本照抄lrj白書
*利用字符指針替代字符串傳遞(長度\起始地址)
kimbits 35min 1WA NAC -> 基本思想正確
2.24
heritage 8min 1Y 復習字符串指針寫法
kimbits 22min 1WA
[分析]類似康托展開的思想，定義F(n,m)表示 ∑C(n,i)(0<=i<=m),顯然若首位為1，則序號i必大于F(n-1,m),反之為0.
根據組合恒等式C(n,m) = C(n-1,m) + C(n-1,m-1),有F(n,m) = F(n,m-1) + C(n,m).
*因i越界，故使用double
msquare 30min 未完成
2.25
找Ylen要KOI題目,驚聞她一等.
http://u.youku.com/user_playlist/id_UMjIzOTYyODUy.html 題解視頻
2.26
fence9 50min 4WA
復習 輾轉相除法 Pick公式 某個幾何結論
2.14
agrinet 29min 1Y
- 使用qsort進行結構體排序
int cmp(const int* a, const int* b){
edge* pa = (edge*)a, pb = (edge*)b;
return (pa->w > pb->w) ? 1 : 0;
}
couducters UNAC
butter UNAC
2.15
agrinet 15min 1WA
- 復習結構體排序.
butter 30min+? 3WA
*錯誤的變量名
*內存過小 -> 嚴格按照題目
2.16
butter 19min 2WA
*錯誤操作 -> 隊列的進出
*錯誤的文件讀入
=> 如何進行肉眼查錯
URAL 1011 conductors
- 邊界處理問題，需要注意，題目中區間的開閉.
-> *100 避免浮點誤差，強制類型轉換可能造成浮點誤差!!
2.17
range 15min 1Y DP
- f[i][j] = min{f[i-1][j], f[i][j-1], f[i-1][j-1]} + f[i][j];
- f[i][j]表示以其為右下角的最大正方形邊長
*變量打錯count
game1 39min 1Y DP
- f[i][j] = sum[i][j] - min{f[i+1][j], f[i][j-1]};
- f[i][j]表示從i開始連續n個數先手取的最大值
*方程20min沒想出來
*循環求值過程中，長度優先
2.18
[精度處理問題 by gXX]
#define EPS 1e-7
e.g. int(99.98*100)的正確寫法int(99.98*100 + EPS)
2.19
GDKOI 2011 Day1[YY] -> Thk for Ylen.
第一題，暴力，覺得能A.
第二題，30%暴力；50%離散化，估計現場寫不出來.
第三題，30%暴力，只會用Floyd求強連通分量.
第四題，似乎是生成某種子集，然后最小生成樹，也許30%能過
理論估計最高值76，實際不出大錯40+無壓力.
2011.2.7
USACO Monthly Feb 2011
[讀題模式]邊讀邊做 -> 第一題讀題出錯 -> 浪費40min => 在不確定梯度的考試,通讀全卷異常重要
40min時,開始崩潰狀態.80min,崩潰狀態結束.
最后超時1min -> 變量少了一個初始化 -> 寫完后的靜態調試非常重要
讀題順序 1 -> 2 -> 3. 解答順序 1 -> 3 -> 1 -> 2
[dance2] 70min -> 30line
括號匹配,弄一個run變量記錄'>'個數,出現'<'run-1.輸出的情況:
1)illegal ->(1)途中run < 0 (2)最后run != 0
2)legal -> run == 0
[treats] 45min {讀題} -> 77line
模擬,讀題有難度.
題目中給出了一種啟發式搜索(A*),要把最大值通過line row交換轉換到(1,1).之后值同理,但不能交換已確定的row line.
定義check()函數檢查row line是否交換,swap交換row line.利用check()循環求解即可.
[hexgon] 45min {坐標的意義} -> 42line
模擬:1)按題意填充矩陣;2)坐標判斷可能值,加入隊列;3)升序排序隊列,輸出;
butter 25min [未完成] SPFA
2011.2.8
humble 19min 1Y
butter 2h 2WA[SPFA]
(0)讀題 -> 每個牧場可能有多個牛
(1)初始化 -> first[*] = -1 無從*點開始的邊
-> d[*] = INF (* != k)
(2)SPFA -> 三角不等式d[v[e]] > d[u[e]] + w[e]
=> 若v[e]不在隊列,(1)加入隊列(2)更新距離d[v[e]] *
fence9 40min 9/12->TLE
利用行列式求面積判定點是否在三角形內,枚舉
->皮克公式忘記
heritage 40min [UNAC]
使用<string>,無法編譯
2011.2.9
USACO Monthly Feb 2011 [杯具的被封號了T^T]
**Cena -> 15/36
[dance2] AC.
fprintf (fout, "%slegal\n", bad || nesting > 0 ? "il" : ""
標程的 ?: 用的恰到好處
[treats] 調試未完
和標程思路基本一致，除了標程逐個元素判斷，我用行列判斷.
-> 行列判斷如果出單行或單列數據就杯具了
butter 40min 1Y -> spfa主程序壓縮至11行
重復定義變量;
看來寒假只能寫完Chapter3,然后做相當于1-2個Section的Chapter4. -> 只能說穩定性有了提升,這應該就是重復做題的效果.
2011.1.30
rect1 90min 1WA.
逆序進行矩形切割:使用遞歸方式的矩形切割,實際上就是一種分治算法
(1)比對新添加矩形和已添加矩形
(2-1)若未覆蓋，計算顏色面積
(2-2)若覆蓋，刪除新矩形，矩形切割(坐標比對)
[關于順序]
矩形切割是一種平面上矩形的動態統計手段，因而統計和切割是同步進行的，所以必須逆序統計.若順序統計，則必須把統計過程放在最后.
2011.1.31
NOI 1997 衛星覆蓋 3/20
2011.2.1
stamps 15min 1Y.
rect1 42min 1Y.
[過程] 逆序添加矩形 -> 動態統計.
add-
1.添加矩形
2.判斷覆蓋 -> 補集思想,坐標必須使用閉區間.[卡了25min]
3-1 無覆蓋則統計顏色
3-2 設置標準變量,切割矩形(4)
NOI '97 矩形覆蓋 2h 19/20->{0.47s,352KB} [逆序切割] => 難度過大,最終放棄
[注意]判斷覆蓋利用了補集思想，所以必須是閉區間.
基本思想和算法 同 rect1.
[關于標程]Bvoid標程利用遞歸直接統計,0.28sAC. -> 差距
spin 40min 1Y 模擬
樣例理解不能 -> 未讀題[20min] => 不要臆斷!!!
ratios 11min 1Y 枚舉
2011.2.5
agrinet 11min 1Y.
hmuble 29min 1Y.
*思路錯誤,忽視異分子相乘的情況
(1)記錄丑數，及每個因子所乘最大丑數
(2)去重,若新丑數等于上一丑數則不記錄,記錄因子所乘最大丑數
rect1 25min 1Y 注意輸入
contact 2h 12WA
(1)以a,b分段讀入字串 -> 利用二進制直接編碼,在首添一,記錄0開始情況;
(2)[qsort] qsort(set + 1, Max, sizeof(int), cmp);
int cmp(const void *a, const void *b){
if (flag[*(int*)a] == flag[*(int*)b])
return *(int*)a - *(int*)b;
return flag[*(int*)b] - flag[*(int*)a];
}
(3)輸出:每6個換行,換行后無空格 -> 40min
kimbits 70min 2WA+1RE [UNAC]
利用組合恒等式C[k,n] = C[k,n-1] + C[k-1,n-1];
求值思想類似逆康拓展開.
2011.2.6
shopping 43min 1Y[DP]
SB做法:f[a][b][c][d][e] = min{f[a-1][b][c][d][e]+cost[a],..,優惠組s}
[min] 特殊處理0和INT_MAX -> 15min
-> f[a][b][c][d][e] = min{cost,優惠組};
-> 注意思考問題實質
game1 38min [UNAC]
輪流取數,狀態設置錯誤:f[i][j] = max{f[i+1][j]+A[i], f[i][j-1]+A[j]};
range 40min [TLE 1點+MLE]
f[i][j][k] DP. O(n^3)
job 25min [未完]