看來寒假只能寫完Chapter3,然后做相當(dāng)于1-2個Section的Chapter4. -> 只能說穩(wěn)定性有了提升,這應(yīng)該就是重復(fù)做題的效果.
2011.1.30
rect1 90min 1WA.
逆序進行矩形切割:使用遞歸方式的矩形切割,實際上就是一種分治算法
(1)比對新添加矩形和已添加矩形
(2-1)若未覆蓋，計算顏色面積
(2-2)若覆蓋，刪除新矩形，矩形切割(坐標(biāo)比對)
[關(guān)于順序]
矩形切割是一種平面上矩形的動態(tài)統(tǒng)計手段，因而統(tǒng)計和切割是同步進行的，所以必須逆序統(tǒng)計.若順序統(tǒng)計，則必須把統(tǒng)計過程放在最后.
2011.1.31
NOI 1997 衛(wèi)星覆蓋 3/20
2011.2.1
stamps 15min 1Y.
rect1 42min 1Y.
[過程] 逆序添加矩形 -> 動態(tài)統(tǒng)計.
add-
1.添加矩形
2.判斷覆蓋 -> 補集思想,坐標(biāo)必須使用閉區(qū)間.[卡了25min]
3-1 無覆蓋則統(tǒng)計顏色
3-2 設(shè)置標(biāo)準(zhǔn)變量,切割矩形(4)
NOI '97 矩形覆蓋 2h 19/20->{0.47s,352KB} [逆序切割] => 難度過大,最終放棄
[注意]判斷覆蓋利用了補集思想，所以必須是閉區(qū)間.
基本思想和算法 同 rect1.
[關(guān)于標(biāo)程]Bvoid標(biāo)程利用遞歸直接統(tǒng)計,0.28sAC. -> 差距
spin 40min 1Y 模擬
樣例理解不能 -> 未讀題[20min] => 不要臆斷!!!
ratios 11min 1Y 枚舉
2011.2.5
agrinet 11min 1Y.
hmuble 29min 1Y.
*思路錯誤,忽視異分子相乘的情況
(1)記錄丑數(shù)，及每個因子所乘最大丑數(shù)
(2)去重,若新丑數(shù)等于上一丑數(shù)則不記錄,記錄因子所乘最大丑數(shù)
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],..,優(yōu)惠組s}
[min] 特殊處理0和INT_MAX -> 15min
-> f[a][b][c][d][e] = min{cost,優(yōu)惠組};
-> 注意思考問題實質(zhì)
game1 38min [UNAC]
輪流取數(shù),狀態(tài)設(shè)置錯誤: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 [未完]