JohnYam

摘要： 傳送門 注：如無特殊說明，本篇題解中所有的序列，均用紅色標示已經放置硬幣的位置。若本次操作為拿走硬幣，用藍色標示本次操作拿走的硬幣的位置，用黑色標示從未放過硬幣或放置過硬幣且在本次操作之前的操作中被拿走的位置。 根據題意和數據范圍，不難想到本題的做法是區間 DP。然而難點在于刻畫放置和拿走硬幣這兩個 閱讀全文

摘要： 傳送門 絕大多數的計數題都可以用 dp 和容斥解決。 本題的 dp 比較好想，設 \(f_{i,j}\) 表示前 \(i\) 個位置填了 \(j\) 個數。考慮如果第 \(i\) 個位置不填，則貢獻是 \(f_{i-1,j}\)；否則前面 \(i-1\) 個位置一共填了 \(j-1\) 個數，由于第 閱讀全文

摘要： 傳送門 首先如果沒有任何限制條件，則原問題即變為簡單的「求方程 \(\sum_{i=1}^nx_i=m\) 的解的個數」。此時考慮插板法，等價于將 \(m\) 個 \(1\) 分成 \(n\) 份，這時有 \(m-1\) 個空隙，要插 \(n-1\) 個板，方案數就是 \(\binom{m-1}{n 閱讀全文

摘要： 傳送門 一道有趣的思維題。 我們從最簡單的情況開始考慮：如果還剩下 \(2\) 格電呢？ 那么直接詢問 \(\texttt{O}\) 和 \(\texttt{H}\)，剩下的位置就是 \(\texttt{C}\)。 從以上的樸素做法中我們得到啟發：能不能通過耗電量更低的方式來確定三個字母的所有位置？ 閱讀全文