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