2015年3月25日 星期三

SRM654ˋ

向來在台灣時間早上的場次或許因為參加的人偏少,題目有偏間單的趨勢,這場也不例外,我難得沒有重大失誤的破台了。不過我每一題都 debug 好久就是了。

這場第一名Endagorion寫的 Editorial

250 --- SquareScores


題意:給一個由小寫字母和問號構成的字串,並且給你問號代表每個字母的機率,並定意一個字串的分數為所有字母都相同的 substring 個數 (不同位置算不同)。求這個字串的分數期望值。

數據範圍:字串長度($n$)不超過 $1000$。

tag:[ 數學 ] [ 期望值 ]

關鍵字:簡單期望值

= = = = = = = = = = = = = = =
就直接運用期望值可以拆開的概念,全部也只有 $n*(n-1)/2$個子字串,若再多考慮每個字串相同的字母是哪個的至多 $26$ 種可能性去枚舉,最裸的做法時間複雜度是 $O(26n^3)$,但是$s[i...j]$ 全為同一個字母的機率可以由 $s[i...j-1]$ O(1) 轉移得知,所以立刻就壓到 $O(26n^2)$ 了。但實際上這題根本可以做到 $O(n)$,大家可以想想看~。這題算是期望值類的老掉牙的題目吧。

450 --- SuccessiveSubtraction2

題意: 給定一個數列 $a_1 \sim a_n$,考慮算式 $a_1 - a_2 - a_3 - ... - a_n$,我們可以至多家上兩組括號,求最大的可能計算結果是多少。

數據範圍:$1 \leq n \leq 2000$,有至多 $2000$個詢問(每個詢問是把上一筆詢問的其中一個數字改成另外一個數字)。

tag:[ dp ]

關鍵字:最大連續和

= = = = = = = = = = = = = = =
自己亂補上刮號就可以發現,補至多兩個括號,等價於把 $a_3 \sim a_n$ 中至多連續的兩段數字正負對調。

這題做法一堆吧,限制非長寬鬆,加上他每筆詢問實際上只有變動一個數字,那應該是可以做到 $O((q+n) log n)$ 的。

我的做法是 dp 做出每個 prefix 和 suffix 的最大連續和,然後枚舉prefix 和 suffix 切開的位置。

這題還有一個有趣的做法(參考此連結的),先找一次最大連續和的一段正負反過來,然後再做一次相同的事就行了。

850 --- TwoEntrances

題意:給一個長的像 Tree 的家,由兩個 node 是家的入口,現在要搬家具進去每個 node,但是能般進去的條件是,由某個入口到該 node 的 path 上都還沒有放入家具,問般家具的順序有幾種?答案 mod $10^9+7$。

數據範圍:邊數不超過 $3000$。

tag :[ dp ] [ 排列組合 ]

關鍵字:燈飾 dp

= = = = = = = = = = = = = = =

私認為這題難度只有 $500$,若入口只有一個,那他就只是一個非常經典的題目,我這個  BLOG 已經出現過了... 請看 CF290 pD

若是這樣的問題相信不少人都見過,但入口兩個要怎麼處理呢?

先畫意張示意圗 :)

黑點是入口,我們想像一下把代表入口的兩個點釘在牆上掛起來,大概就會變成上圖所示。

我們先想想退化的 case,例如說...掛起來後沒有任何點垂下來。我們會發現,這種 case 的話,任何時刻有擺家具的 node 都是連在一起的!於是就給了我一個靈感,我們可以 dp 狀太設成: $dp[l][r]$ 代表 $p_l \sim p_r$間及其垂下來的所有 node 都擺上家具,但其他 node 都沒有的方法數。

至於要怎麼轉移呢?我們可發現,代表 $dp[l][r]$ 的狀態,最後一個擺上家具的位置一定是 $p_l$ 或 $p_r$ 兩者之一,於是我們分別把 $p_l$ 和 $p_r$ 當作 root,然後想像你是怎麼解原始的經典題版本,那應該就會知道要怎麼轉移了 :)