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，然後想像你是怎麼解原始的經典題版本，那應該就會知道要怎麼轉移了 :)