WaterSun

摘要： asdf 閱讀全文

摘要： 思路 每一個硬幣最終都會走到 \(2 \times n\) 的矩形里面，所以不妨將它們先到其到矩形中最近的節(jié)點。 現(xiàn)在只需要在這個矩形中調整使每一個位置都有一個硬幣。貪心的，我們希望讓 \(x\) 更小的填的位置盡量靠前。 從前往后掃，記 \(a,b\) 分別表示 \(y = 1,y = 2\) 的 閱讀全文

摘要： 思路 首先應當讓位數(shù)最多，因此我們欽定 \(s_1 = S\)。 當 \(S\) 全零和全一都是容易解決的，那么現(xiàn)在只需處理 \(S\) 形如 111000111000... 的情況。 此時為了讓最后異或的結果盡可能大，我們肯定選擇將第一段連續(xù) 0 填上。 令第一段 1 的下標在 \([a,b]\) 閱讀全文

該文被密碼保護。 閱讀全文

摘要： 思路 考慮從每一個 \(d_i \neq -1\) 的點開始往外走 \(d_i\) 步，然后所有這些點走到的點的集合取交集就是答案，復雜度是 \(\Theta(n^2)\) 的。 注意到我們需要對一些集合取交，容易想到 bitset 優(yōu)化，此時的復雜度瓶頸在于 BFS 的次數(shù)。 因為 \(u \le 閱讀全文

摘要： 思路 有一個很簡單的 \(\Theta(n^2m)\) 的做法，每一輪枚舉所有未進行的考核，判斷以當前的能力能否通過這個考核，然后更新當前的能力。 考慮優(yōu)化，如果每一次都能精準找到一個能夠通過的考核，那么就能優(yōu)化掉一個 \(n\)。對于每一場考核的對科目 \(i\) 的要求從小到大排序，那么以當前科 閱讀全文

摘要： 思路 對于 Subtask 2，本質是確定了最小值，要使 \(1 \leadsto u\) 路徑上邊權最大值最小，顯然直接上 Kruskal 重構樹。 對于 Subtask 3，本質是確定了最大值，要使 \(1 \leadsto u\) 路徑上邊權最小值最小，顯然直接跑邊雙即可。 這啟發(fā)我們考慮枚舉 閱讀全文

摘要： 以為是拓撲排序之類的東西，結果一看 tag 是構造，已老實。 思路 注意到當 \(b\) 有一段連續(xù)相同數(shù)的時候，對于最后一個經(jīng)過這一段的操作必須覆蓋整個這一段，因此考慮將一段相同的數(shù)縮成一個點，記作 \(c_1,\dots,c_k\)。 有解的條件為：\(c\) 序列是 \(a\) 序列的一個子序 閱讀全文

摘要： 主播主播，你怎么調了一上午這個題，是不是可撤銷并查集寫了路徑壓縮啊 /yun 思路 為了方便，將題目中所有 0-index 改為 1-index。 切掉 \([p,p + 1]\) 等價于計算 \([1,p],[p + 1,n]\) 兩個點集和其連邊構成的連通塊數(shù)之和。兩個問題相互獨立，現(xiàn)只考慮 \ 閱讀全文

該文被密碼保護。 閱讀全文

摘要： 信息學不是數(shù)學，所以樂子題解當樂子看看就行了 /lh 思路 大膽猜測，當查詢的 \(h\) 變小時，用按鈕的次數(shù)一定不會減少，于是上決策單調性可以直接秒掉。 接下來嘗試證明一下。設允許的最高高度為 \(h\)，令 \(f(x)\) 表示按 \(x\) 次按鈕的代價，\(g(h,x)\) 表示按 \( 閱讀全文

摘要： 挺有意思的一個題。 思路 在下文中，記 \(col_{x,y} = \operatorname{color}(x,y)\)。 因為顏色只有 \(0,1\)，那么 \(|A|\) 等于相鄰兩個位置 \((x_1,y_1),(x_2,y_2)\) 滿足 \(col_{x_1,y_1} + col_{x_ 閱讀全文

摘要： 感謝此題將我送上 Master。 思路 注意觀察 \(F(v,l,r)\) 的定義，容易將其刻畫成 \(v_{l \sim r}\) 中 \(1\) 的數(shù)量減去 \(0\) 的數(shù)量。 不妨將 \(1\) 的權值記作 \(1\)，\(0\) 的權值記作 \(-1\)，令這個序列的權值序列為 \(val 閱讀全文