文章目錄

• C - Be Together
• D - Unbalanced
• E - Children and Candies
• F - Unhappy Hacking

題目鏈接

C - Be Together

$200$分 結論

直接取所有數的平均數，由于需要是整數，所以算一下$mid,mid+1,mid?1$，取最小值即可。

代碼

D - Unbalanced

$400$分 結論

不難發現如果有一段是合法的那么一定存在長度為$2$或者$3$的串合法，直接找即可。

代碼

E - Children and Candies

$800$分 $dp$ + 前綴和優化

題面太陰間了，簡單解釋一下。

有$n$個小朋友，$c$個糖果，如果第$i$個小朋友分了$a$個糖果，那么他得到的快樂值是$x_i^a$，一個幼兒園的快樂值是小朋友快樂值乘積，定義$f(x_1,x_2,...,x_n)$為一個幼兒園的快樂值，現在讓你計算：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-d6J2qEfu-1645840763184)(C:\Users\Libra_Glow\AppData\Roaming\Typora\typora-user-images\image-20220226094553741.png)]

顯然考慮$dp$，$dp[i][j][k][p]$ 表示到第$i$個人，已經分了$j$個，要分給他$k$個，當前選了$x_i=p$，轉移方程也比較明顯$dp[i][j][k][p]+={\sum }_{t=0}^{j?k}{\sum }_{h=a_{i?1}}^{b_{i?1}}dp[i?1][j?k][t][h]$，可以發現對于第三維和第四維我們可以使用前綴和優化掉，更進一步可以發現根本不需要存第三維和第四維，直接記$dp[i][j]$即可，預處理一下$[a_i,b_i]$的區間取某個冪次的和即可，復雜度可以降到$O(n^3)$

代碼

F - Unhappy Hacking

$800$分 $dp$

直接考慮$dp[i][j]$表示用了$i$次操作，匹配到了第$j$位，一開始沒想出來，因為是將$j$放到了第一層循環，以長度作為$dp$決策的轉移，也就是考慮$dp[i][j],dp[k][j?1]$，這樣顯然是不好搞的，考慮反過來，以操作次數作為決策點，$i?1?>i$只進行了一次操作，顯然就只有三個情況，我們依次考慮：

• $dp[i][j]+=dp[i?1][j?1]$ 當前操作打$1$或者$0$，根據第$j$位確定
• $dp[i][j]+=dp[i?1][j+1]?2$ 當前操作選擇按回退，因為我們并不關心$j+1$位是$0$還是$1$，所以需要乘$2$。

注意$j=0$的時候還需要加上$f[i?1][0]$。

復雜度$O(n^2)$

代碼

還有一種比較巧妙的方法，可以知道長度為$len$的字符串出現的概率都相等，所有情況是$2^{len}$，所以我們如果能求出來所有的情況，除上$2^{len}$即可。

設$dp[i][j]$表示用了$i$次操作，長度為$j$的方案數，直接寫轉移了：

• $dp[i][j]+=dp[i?1][j?1]?2$ 當前操作打$1,0$，所以需要乘$2$
• $dp[i][j]+=dp[i?1][j+1]$ 按回退，由于$f[i?1][j+1]$的方案就已經包含了$j+1$是$0,1$的兩種情況，所以不需要乘$2$。

復雜度$O(n^2)$

代碼

總結

以上是生活随笔為你收集整理的AtCoder Regular Contest 059的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。