AtCoder ABC 234 個人題解 (2022.1.8)

# AtCoder ABC 234 個人題解 (2022.1.8) ###### tags: `AtCoder題解` `ABC` https://atcoder.jp/contests/abc234 [My Submissions](https://atcoder.jp/contests/abc234/submissions?f.Task=&f.LanguageName=&f.Status=&f.User=Cookie197) 又是被奇怪的錯誤搞爛的一場![](https://i.imgur.com/swwKwb8.png) --- ## pD Prefix K-th Max 用一個$PQ$維護就好。如果新數大於目前的答案就把他丟到$PQ$，再把$top$丟掉。每次的答案就是$PQ.top()$。 #### Complexity: $O(nlog(k))$ #### Status: AC 41:41(2) --- ## pE Arithmetic Number 枚舉所有的首項和公差，如果合法就更新最佳答案。 #### Complexity: $O(log(x) \times$ 某個很小的常數$)$ #### Status: AC 30:12 --- ## pF Reordering "a permutation of a non-empty, not necessarily contiguous subsequence of $S$" 其實這就表示$S$是什麼不重要，只需要知道字母的個數。 ### 觀察首先可以發現，只要字母的組合數不同，或個數不同，無論怎麼排列都一定會做出不一樣的字串。當固定某個長度，要加入新字母的時候，只要長度固定，新字母數量固定，就可以做出特定不重複的字串，因此考慮$dp$。 ### 狀態和轉移令$dp(i,j)=$長度為$i$的字串總數，目前看到第$j$個字母。假設我們有3個$a$ ($="aaa"$) 以及4個$b$等著加入（$b$不一定要用完），那就多少種新的字串？ $b=0:$ 1種 $b=1:$ 有4個空位，1個人，所以是$H_{1}^4 = C_1^4 = 4$ $b=2:$ 有4個空位，2個人，所以是$H_{2}^4 = C_2^5 = 10$ $b=3:$ $H_{3}^4$ $b=4:$ $H_{4}^4$ 這也就是$dp(3,1)$ 利用「推的」轉移到$dp(3,2) ~dp(4,2) \cdots dp(7,2)$ 的過程。可以得到$dp(i+k,j+1) ~+= dp(i,j) \times H_k^{i+1}, for ~k=0 ~to~ cnt[j+1]$。（$cnt[j]$表示存在幾個字母$j$。）答案就是$dp(n,$"z"$)$。 #### Complexity: $O(26n)$狀態，$O(n)$轉移，總共$O(26n^2)$，但好像常數很小？？ #### Difficulty: 中等 (upd:可惡他竟然才淺藍) #### Status: AC 57:09 --- ## pG Divide a Sequence 又是序列切切切所以，以$dp(i,0)$表示把$i$當成新的開頭，$dp(i,1)$表示把$i$當成這一塊的結尾：答案的總和。初始值$dp(1,0)=1$，答案就是$dp(n,1)$。 ### $O(n^2)$ 做法很容易想到一個$O(n)$轉移。首先令$f(i,j) = max(arr[i],arr[i+1]...arr[j]) - min(arr[i],arr[i+1]...arr[j])$。 $dp(i,0) = dp(i-1,1)$，因為新的$i-1$這塊還沒關起來，要繼承$i-1$有關起來的值。要算$dp(i,1)$，則要枚舉他這塊的開頭是誰。所以： $dp(i,1) = dp(i-1,0) \times f(i-1,i) \\ ~~~~~~~~~~~~~+dp(i-2,0)\times f(i-2,i)\\ ~~~~~~~~~~~~~+dp(i-3,0)\times f(i-3,i) \cdots \\ ~~~~~~~~~~~~~+dp(1,0)~~~~~~\times f(1,i)$ 只要從$i-1$跑個迴圈到$1$，同時記好目前的$min,max$就好了。 ### $O(n)$ 做法 :::info Upd : 2022/1/9 AM 11:00 ::: 把$f(i,j)$寫回來，變回$max(i..j) - min(i..j)$。首先我們可以觀察到，在任何時刻，$max$的序列必為非嚴格遞減，$min$的序列必為非嚴格遞增。 :::spoiler Example 1 arr = 1 9 6 2 7 3 4 min = 1 2 2 2 3 3 4 max = 9 9 7 7 7 4 4 ::: 假設我們加了一個新的數進來，$min$和$max$的序列會有什麼變化？ :::spoiler Example 2 arr = 1 9 6 2 7 3 4 8 max = 9 9 8 8 8 8 8 8 arr = 1 9 6 2 7 3 4 1 max = 9 9 7 7 7 4 4 1 ::: $max$序列（$min$也是）會有「一段後綴」被改值，而且是改成新的那個數。我們要算的$dp(i,1) =\sum_{k=1}^{i-1} (dp(k,0) \times max[k] - dp(k,0) \times min[k])$，所以可以紀錄： <center>「$max$序列值$=x$」的$dp_0$值總和</center> 我們可以開一個$stack$之類的東西，每次如果看到比自己小或等於自己的$max$就$pop$出來（因為他們的$max$都會變大），把$dp_0$值總和記下來。最後的這些人，再加上現在這個位置的$dp_0$（也就是$dp(i,0)$ ），他們的$max$都會變成$arr[i]$，所以把這個$(arr[i],dp$總和$)$的$pair$丟進$stack$。要注意「**所有$max$相同的那些位置，都會被融合成一項！**」在以上的同時，我們要紀錄一個全域變數「目前$dp_0\times max$的總和」，並在$pop ,~ push~$時同時更新。對$min$也做一樣的事，只是大小於相反。最後的$dp(i,1)$就是「目前$dp_0\times max$的總和」減掉「目前$dp_0\times min$的總和」。 :::spoiler AC code ```cpp= #define mp make_pair stack<pii> big,small; // <val of max/min , tot of dp[0]> signed main(){ cin>>n; for (int i=1;i<=n;i++) cin>>arr[i]; dp[1][0]=1; big.push(mp(arr[1],1)); small.push(mp(arr[1],1)); //注意這裡是1喔 ll bigtot = 0, smalltot = 0; for (int i=2;i<=n;i++){ dp[i][0] = dp[i-1][1]; ll num = arr[i], dptot = dp[i][0]; while(1){ if (big.empty()) break; if (big.top().first<=num) { dptot += big.top().second; dptot %= mod; bigtot -= big.top().first * big.top().second % mod; bigtot = (bigtot + mod) % mod; big.pop(); }else break; } big.push(mp(num,dptot)); bigtot += num * dptot % mod; bigtot %= mod; dptot = dp[i][0]; while(1){ if (small.empty()) break; if (small.top().first>=num) { dptot += small.top().second; dptot %= mod; smalltot -= small.top().first * small.top().second % mod; smalltot = (smalltot + mod) % mod; small.pop(); }else break; } small.push(mp(num,dptot)); smalltot += num * dptot; smalltot %= mod; dp[i][1] = (bigtot - smalltot + mod) % mod; } cout<<dp[n][1]<<endl; } ::: #### Complexity: $O(n)$ #### Difficulty: 稍難 #### Status: --