10.22
P1326, SPFA.
最短路模板題
P2022, 模擬.
維護(hù)長(zhǎng)度為N的序列即可, 對(duì)于每個(gè)操作注意細(xì)節(jié).
P2017, 搜索
貪心上界, 累加下界, 中間暴搜. 昨天打漏了\sum C_i的初始化, 把C_i和A_i打混了.
*據(jù)說數(shù)據(jù)弱到直接交下界就A
*需要復(fù)習(xí)下gen怎么寫了
P2021, 位運(yùn)算+DP
and, 統(tǒng)計(jì)連續(xù)的1, 直接計(jì)算
or, 統(tǒng)計(jì)連續(xù)的0, 間接計(jì)算
10.27
Vijos Monthly Oct12
P1742, 模擬.
平均數(shù) 加權(quán)累加即可;
中位數(shù) qsort排序, 按照奇偶分類輸出;
眾數(shù) 排序后累計(jì)不同的值和出現(xiàn)次數(shù), 排序輸出;
P1745, 貪心?
數(shù)據(jù)范圍否定了DP, 但是作為貪心范圍確實(shí)有點(diǎn)小. 按照切割的權(quán)w_i排序, 如果w_i相等, 則行/列多的先切. 排序后累加即可.
如果f[i][j]來dp的話, 大概是O(N^3)的時(shí)間, O(N^4)的空間...
-> 很好, 爆longlong了...T_T
P1746, 圖論.
最短路變形, N = 300. 直接利用Floyd得到所有最短路, 對(duì)于一對(duì)u,v, 分別枚舉N個(gè)節(jié)點(diǎn), min{G[u][i] + G[i][v]}即為所求.
P1747, ?.
30%明顯是搜索, 但是我實(shí)在不會(huì)暴力了, 連方向都不知道. 我想起來今天AIME那幾個(gè)暴力算的圓...
*對(duì)于算法, 在實(shí)現(xiàn)前必須充分討論細(xì)節(jié). 在實(shí)現(xiàn)過程中修改細(xì)節(jié)及其浪費(fèi)時(shí)間.
*對(duì)拍 & 特別小數(shù)據(jù)的構(gòu)造需要復(fù)習(xí), 正確率.
*各類算法模板的整理.
-> 150/300, 實(shí)現(xiàn)能力啊啊啊啊
http://www.vijos.org/Discuss_Show.asp?DisID=55613
10.28
Vijos T1062, 實(shí)在沒動(dòng)力寫, 就YY了一下(...
P1, 十進(jìn)制小數(shù)轉(zhuǎn)二進(jìn)制小數(shù)
不會(huì)...乘二取整法套不上
P2, ?
只會(huì)暴力做法, O(N!)生成序列, 然后根據(jù)約束條件剪枝, 譬如:
(1) 賀卡的時(shí)間順序
(2) 每個(gè)人的時(shí)區(qū)互異性
(3) 時(shí)間范圍
其實(shí)手算可容易了...(
P3, 模擬
[70%做法]
(1) O(N^2)把每個(gè)區(qū)域蓋房子的權(quán)值預(yù)處理一遍
(2) 蓋N次房子, 每次掃一遍找最小值, 然后標(biāo)記相關(guān)區(qū)域不可用O(N^3)
*可能的房子數(shù)量上限好像是大于N的 ...
[AC做法]
(1) O(N^2)把每個(gè)區(qū)域蓋房子的權(quán)值預(yù)處理一遍
(2) 把每個(gè)區(qū)域的權(quán)值升序排序, 依次選擇, 對(duì)于選中的區(qū)域, 標(biāo)記其周邊區(qū)域不可用, 復(fù)雜度O(N^2)