文章目錄

• C - Tak and Cards
• D - Digit Sum
• E - Tak and Hotels
• F - Best Representation

比賽鏈接

C - Tak and Cards

Score : $300$ points $dp$

基礎$dp$了，隨便搞搞就能過了。

設$dp[i][j][k]$表示選到了第$i$個物品，當前體積是$j$，已經選擇了$k$個物品，轉移：

• $f[i][j][k]+=f[i?1][j][k]$
• $f[i][j][k]+=f[i?1][j?v[i]][k?1]$

之后枚舉$j,k,j\mathrm{m}\mathrm{o}\mathrm{d}k==0$的時候算答案即可。

復雜度$O(n^3)$

代碼

D - Digit Sum

Score : $500$ points 根號 + 數學

差一點點就做出來了，想到根號了，還是對數學不敏感啊。。

分兩種情況考慮：

• $b\le \sqrt{n}$ 此時直接暴力算即可
• $b>\sqrt{n}$此時不難發現題面中給的過程最多進行兩次，也就是說$n=a_0?b+a_1$，$s=a_0+a_1$，帶入之后$n?s=(b?1)?s_0$，根號枚舉$n?s$的因子算即可，注意$b?1$。

復雜度$O(\sqrt{n}\log n)$

代碼

E - Tak and Hotels

Score : $700$ points 倍增

一眼倍增啊，但是當時沒怎么想明白怎么倍增(純純的擺爛)。

跟大部分倍增不同，大部分的都是跳$2^j$步到哪里，這個題正好反過來，定義$f[i][j]$代表從$i$開始花費$j$個操作最遠能跳到哪里，預處理$f[i][0]$的時候可以二分一下位置即可，讓后預處理$f$之后查詢直接倍增即可。注意最后倍增的時候應該還需要從小到大倍增一次，這個根據每個人寫法不同而不同。

復雜度$O(n\log n+q\log n)$

代碼

F - Best Representation

Score : $900$ points $kmp$ + 猜結論

看了許久之后猜了個結論，除了全部相等之外其他的要么分成$1$段要么分成$2$段，下面簡單證明一下：

• 如果$s$本身就不循環，那么只能分成一段
• 否則$s$本身一定循環，那么去掉開頭的一個字母之后，剩下的串一定不循環。

所以只需要求一次$kmp$，讓后判斷循環節是否能整除當前的長度即可，第二種情況直接枚舉斷點。

所以題面$1e9+7$就是個幌子。。。。。

復雜度$O(n)$

代碼

總結

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

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