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