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