11.19
poj 1258[Kruskal]
和training的那題一樣, 注意有多組數據
*數組開錯, 沒有區分MAXn/MAXedge
11.21
poj 1944[DP], unAC
沒看出來是DP.
網上有兩種做法:
(1) 三維DP
(2) 兩個二維DP
快速讀入 by gXX
int getInt() {
char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
int ret = 0;
while ('0' <= ch && ch <= '9') {
ret = ret * 10 + ch - '0';
ch = getchar();
}
return ret;
}
qc #20:
getInt(), 0.06s
fscanf(), 0.2s
fstream, 0.35s
11.28
馬走日問題[回溯], 1h
*lrp問了, 昨晚隨便敲了一下, 發現想得亂七八糟, 果然要想清楚問題再敲.
求(1, 1)到(m, n)的路徑數, 注意回溯邊界即可.
NOIp2011P, 統計單詞數[字符串], 1h
讀入文章中的每個單詞, 轉換大小寫后, 和已知目標單詞比較. 記錄相同單詞數, 及每個單詞的首字母在文章中位置即可.
*trick:
(1)文章中單詞間可能存在多個空格, 因而需要讀入每個字符
-> 需要注意的是, 需要刪除pdf樣例中多余的空格
(2) 文章中的單詞長度可能遠大于目標單詞長度
*很像叉姐第一次模擬題的第一題
NOIp2011P, 瑞士輪[雙關鍵字排序], 60, 40min
*樣例說明很詳細
需要注意雙關鍵字排序和間接排序的區別:
(score[i] < score[j] || (score[i] == score[j] && i > j))
這里直接比較i和j, 而非id[i]和id[j].
*我覺得我這么廢都能一等就是一個奇跡.. >_<
11.30
NOIp2011T, 選擇客棧[數學], 2h
(1) 注意到各顏色間相互獨立, 不妨單獨處理
(2) 題目要求找到區間中存在任意滿足條件點的區間個數, 即所有子區間的個數減去連續不滿足條件的區間個數
*邊界各種掛, 調試無能
12.5
NOIp2011P, 瑞士輪, 1h
*非常心不在焉
*注意靜態查錯 -> 如果出現循環, 大部分正確, 最后出現錯誤的情況, 極有可能是打錯變量.
*注意數組的實際意義, 如存儲標號還是值
(1) 以force[]為第一關鍵字降序, id[]為第二關鍵字升序排序
(2) 注意到過程中只有N個元素+1, 其余N個元素不變, 且對于變化或者不變的元素, score[]單調遞減
故而對于每組選手(i, j), 利用隊列A[]存儲勝利選手, 隊列B[]存儲失敗選手
(3) 按照雙關鍵字合并隊列A[]和B[]
(4) 將(2)(3)進行R輪, 輸出id[Q]即可
NOIp2011T, 選擇客棧, 1h
(1) 利用鄰接表(數組實現), 按顏色存儲客棧; 利用前綴和sum[i]表示1..i中cost_i <= p的客棧個數
(2) 對于每種顏色的每個區間預處理part[], 表示該區間是否符合條件
(3) 利用補集思想, 計算連續的不符合條件區間, C(2,N) - ∑C(2,N_i);
初始化pos = 1; 對于當前指針k, 若part[k] == 1, 則ans -= C(2, k-pos+1), pos = k+1; //pos記錄當前第一個不符合條件區間的標號
*邊界比較麻煩, 實現之前應該計算好
*盡可能分開不同步驟, 降低思維難度
12.12
NOIp 2011P, 表達式的值[表達式樹], 1.5h, 80
*實際上50min就寫完了, 查錯查了很久
(1) 建樹(左閉右開區間)
1) 找到括號外第一個+或*(即結合性反方向在括號外第一個運算符, 利用p記錄是否在括號中)
2) 若不存在+, 令posO=posA
3) 遞歸build_tree(L, posO), build_tree(posO+1, R)
若不存在*, 則遞歸build_tree(L+1, R-1)
*[優化] 每次過程執行前, 脫去所有括號, 需要記錄括號位置; 如果直接判斷端點, 可能會出現(*)+(*)的情況, 導致WA
(2) treedp(其實就是簡單統計)
1) op[i] == '*'
f[i][0] = (f[i.l][0] + f[i.l][1])*(f[i.r][0] + f[i.r][1]) - f[i.l,1]*f[i.r,1]
f[i][1] = f[i.l][1] * f[i.r][1]
2) op[i] == '+'
f[i][0] = f[i.l][0] * f[i.r][0]
f[i][1] = (f[i.l][0] + f[i.l][1])*(f[i.r][0] + f[i.r][1]) - f[i.l,0]*f[i.r,0]
*如果左子樹或右子樹不存在, 則f[i.k][0] = f[i.k][0] = 1(特判, 直接賦值引起錯誤)
*樸素的表達式樹是O(N^2)的, 常數較小, 可以利用兩個奇怪的棧做到O(N). by gXX
12.19
NOIp 2011T, 觀光公交, 研究題解.[*待實現]
*真是每周一題我擦...
(1) 初步的分析包括不使用加速器時的時間計算, 以及對加速器對時間影響的簡要分析. => 一個比較關鍵的結論是, 加速器對時間的影響一定是一個連續段
(2) clj題解給出了一種非常高效的O(M+NlgN)做法, 實質上利用堆處理了取最大值的問題.
(3) O(kN)的做法比較好理解, 實質是利用g(i)數組表示d[i]-1可以影響[i, g(i)]的時間值, 對于每個加速器找最大值即可. 看起來時間可能比較尷尬, 不過實測效果很好.
12.26
NOIp 2011T, 觀光公交[貪心+遞推], AC
[1] 10% 做法, O(N)
每個景點的最晚出發時間
time[i] = max{T_j} (A_j = i)
每個景點的到達時間
enter[i] = max{time(i-1), enter(i-1)} + D[i-1]
景點1..i的游客數為sum[i]
ans = Σ(enter[B[i]] - T_i) (1 <= i <= M)
[2] 20% 做法, O(N^2)
僅考慮一個加速器, 嘗試將其用于任意兩個連續景點間, 記錄最小值.
[3] 60%做法, O(kN^2)
可用反證法證明, 當前加速器在最優位置時, 前一個加速器必然在最優位置. 符合貪心選擇性質.
因而, 對于每個加速器, 重復20%做法即可, 非常易于編寫.
[4] AC做法, O(kN)
分析易知, 若對景點i到景點i+1應用一個加速器, 景點i之前的距離不受影響, 景點i之后僅當enter[i]-1 >= time[i]有影響, 因而受影響的若干個景點必為一連續線段.
g[i]表示在景點i到景點i+1應用一個加速器, 連續段[i, g(i)]受到影響, 可得
[方程]g[i] = g[i+1] (enter[i] > time[i])
i+1 (enter[i] <= time[i])
[邊界]g[N-1] = g[N]
(1) 初始化數組
(2) 對于D[i] > 0的段, 計算max{sum[g[i]] - sum[i]}, 應用加速器
(3) 對于[i, min(g(i), N-2)]更新enter[]和g[]
(4) (2)(3)重復k次
*60分做法的只有50行, AC做法也不過70行. 60分做法只要對題意理解清楚不難實現, 10+min可以寫完. AC做法發現了連續性質, 利用遞推將尋找最優位置的耗時從O(N^2)變為O(N^2), 有一定思維難度, 但是和Day2P2的難度相差無幾.
[5] AC做法, O(M + NlogN)
基本同上, 無需使用g[]數組, 對于每個路徑一次應用多個加速器, 利用堆求得最大值.
未實現, 參考clj題解.