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