3.31
(1) 如何確定對那些題目進行深入思考
(2) 即使全打暴力不見得打得完
(3) 數(shù)論?
(4) SC DP?
GDOI 2011 Day1分析[未實現(xiàn)]
P1, 直接模擬, AC.
P2, 生成子集+高精變形, 8
P3, 暴力模擬, ?
P4, 快排, 4
P5, 暴搜, 12
大概是40 + 8 + ? + 4+ 12 = 64.
4.7
US Open Silver Division, 2h, 未實現(xiàn)
P1_unlock[DFS-ID + 二分]
[Brief]
在10*10的方格中, 有三個連通塊, 對于每個連通塊可以向四個方向移動, 求使得三個連通塊互不相鄰所需的最小移動次數(shù).
[Solution]
---------|
-++++++++|
--------+|
*******|+|
*******|+|
*******|+|
*******|+|
*******|+|
*******|+|
*******|||
分析:
(1) 大概最小移動次數(shù)的最大值不會超過20, 如上圖. 移動次數(shù)的上限大概略大于 相連的邊數(shù)/2.
(2) 可以發(fā)現(xiàn), 每次的決策必然小于3*4 = 12種, 可以利用一次Floodfill得到不同連通塊之間的相接關(guān)系, 顯然只有相對方向有一方相連, 或者均不相連的部分可以移動.
可能的優(yōu)化:
(1) 兩個相連的連通塊, 向相反方向移動是互相等價的.
(2) 若在某個方向能夠移動的話, 一次移動到位.
*復雜度很難分析, 應(yīng)該能通過大部分測試數(shù)據(jù).
P2_bookshelf[DP]
[Brief]
給定N個長為W_i, 寬為H_i的書, 書的放置必須按照給定順序, 每層的長度限制為L, 試求書柜高度最小值.
[Solution]
很明顯是O(N^2)的動態(tài)規(guī)劃, 但是我只想到了O(N^2*L)的, 似乎是有限制的背包問題.
[狀態(tài)] f[i][j][k]表示放了i本書, 在第j層, 該層剩余寬度為k的最小值
[方程] 略, 討論第i-1本書放在哪層即可.
*正解可能通過單調(diào)隊列或是別的手段降維, 也可能是重新設(shè)計狀態(tài).
P3_running[數(shù)據(jù)結(jié)構(gòu)]
[Brief]
N頭牛, 跑L圈, 圈長C. 給出每頭牛的速度v_i, 求跑的最快的牛到達終點是, 牛群中超車了多少次.
[Solution]
正解復雜度大概是O(NlogN).
可以知道T = C*L / max{v_i}, 然后對于每頭牛i跑了C_i = T*v_i/C圈, Σ[C_i-C_j]即為答案. 復雜度O(N^2).
大概可以總結(jié)幾點:
(1) 對題目的分析能力顯著下降
(2) 實現(xiàn)能力是個問題
(3) 如何恰當?shù)膶ε? 減少時間成本, 又不損失正確率
4.9
GDOI 2011 Day2 分析[未實現(xiàn)]
P1, 讀題無能, 完全不能找到"瞬移水只能作用于到過的點的描述". 做法是prim+heap或kruskal
P2, 時間常數(shù)比較大, 很難寫, 不一定能AC
(1) 讀入每部小說后, 對小說中每個單詞進行排序(字典序), 注意不區(qū)分大小寫, O(n*NlogN)
(2) 將排序后的單詞按照順序插入動態(tài)數(shù)組(指針/數(shù)組模擬鏈表/vector實現(xiàn)), O(N)
(3) 按照時髦值對小說進行間接排序, O(NlogN)
(4) 對于每個詢問, 在每部小說中進行二分查找, O(QlogN)
總復雜度是O(n*NlogN), n = 1000, N <= 20000, 預計能通過大部分測試數(shù)據(jù)
P3, 數(shù)論題, AC做法需要用到中國剩余定理, 下面是50%的做法
(1) 構(gòu)造素因子表判斷A的合法性
(2) 對每個1..N除去因子后, 求乘積末位
(3) 記錄構(gòu)成K的因子的次數(shù), 計算多余部分乘積末尾
(4) 輸出結(jié)果
復雜度是O(QN)
P4, 計算幾何, 這種做法大概能通過大部分數(shù)據(jù)
對于每個方案, 計算每個點和其中相連兩點構(gòu)成三角形面積之和(利用行列式), 并檢測點是否在五邊形上, 復雜度是O(5MN)
P5, treeDP, 看不出來...比較容易想到O(N!)的暴搜
(1) 利用兒子兄弟表示法建樹
(2) 生成N!種順序, 判斷其合法性(利用樹的層次關(guān)系?)
(3) 維護最小值
可能的分數(shù)大概是40? + 40- + 20 + 40- + 12?
考慮實際情況, 可能是0 + 32 + 20 + 24 + 0 = 76.
于是綜合考慮兩天, 大概是64 + 76 = 140, 差不多二等了. 可能的預計是, 題目方向變化, 難度提升.
4.15 ~ 4.28
用CTex寫的, 雖然只是徒勞的努力, 不過也有些初窺門徑的味道. 結(jié)局意料之外情理之中, 倒也罷了. 段神說他是反面教材, 我是反面教材2.0
省賽備戰(zhàn)實錄.pdf
4.28
一個idea, 算法模板, 并準備若干測試數(shù)據(jù), 以測試模板.