掛掛樂，樂掛掛

我們吃薯片模擬賽掛掛樂還是太刺激了。

2026省選模擬1

為什么第一場不是吃薯片模擬賽呢？

1. T1

   考慮每個數的貢獻次數，發(fā)現若第 \(i\) 位存在一個數是 \(1\)，那么它就會被貢獻 \(2^{n - 1}\) 次。

   容易發(fā)現 \(n > 2\) 等價于 \(n = 2\)。

   接下來就是找兩個數或的種類數。

   考慮是否卡上界、下界，反正可以直接整成幾個區(qū)間求并，具體的看題解吧。

2. T2

   感覺是很經典的題。

   考慮一個四劃分 \(AB|CD\) 等價于 \(A\rightsquigarrow B\) 和 \(C\rightsquigarrow D\) 的路徑有邊相交。

   想要統(tǒng)計這個，考慮鏈等于邊數減點數（因為兩端的點不算），這樣計數一個樹就直接做了。

   考慮對稱差，顯然轉化是 \(|a \oplus b| = |a| + |b| - 2|a \And b|\) 考慮計算 \(|a \And b|\)，同樣的思路，設 \(x\) 是邊，\(y\) 是點：

   \((x_1 - y_1)(x_2 - y_2) = x_1x_2 - x_1y_2 - y_1x_2 + y_1y_2\)，分別計數即可。

   具體可以枚舉一棵樹在另一顆樹上 dp，因為有三度化的限制可以直接做到 \(n^2\)。

2026省選模擬2

簡單場。

1. T3 穩(wěn)王

   首先考慮其相當于是每種情況出現的概率和。

   考慮每種牌型的概率和在容斥一下，寫成生成函數就變成多項式遠端求值板子了。

CSP-S模擬17-A

Ciallo～ (∠?ω< )⌒★ 又見寶寶場。

總之 AK 的充要條件就是你會一下普通冪轉下降冪：\(x^n = \sum_{i = 0}^n \begin{Bmatrix} n\\ i\end{Bmatrix} x^{\underline i}\)，然后拆開維護，就沒了。

CSP-S模擬18-A

史中貴族——wang54321

1. T1 ZZH與背包（knapsack）

   發(fā)現 \(q\) 很大，考慮平衡一下，暴力排序以后二分是 \(\sqrt{q2^n}(n \log q)\) 的，可以獲得 96pts。

   特判大樣例即可過題。

   考慮特判大樣例還是太吃操作了，嘗試去掉 \(n \log q\)，考慮前 \(i\) 個物品已經選好并排好序了，加入第 \(i + 1\) 個物品時可以直接將是否選擇的兩個 \(2^i\) 的數組歸并。

   詢問也可以類似做。

   但是上面的所有都不重要，\(sqrt{2^n}q\) 帶 \(4\) 倍常數過了。

2. 盡梨了

   有一萬中寫法。

   不太用腦子的是首先建出 2-set，發(fā)現一個點不是行就是列，考慮縮完點以后的圖，每相鄰兩層都是完全連滿的。

3. 團不過

   卡農。

   這里直接考慮 FWT。

   簡單觀察式子即可，沒腦子做法，懶得寫了。

   值得一提的是我賽事寫錯一百萬個括號導致最后沒改成 \({\cal O}(n)\) 的。

4. ZZH的游戲 (game)

   難點在于發(fā)現 \(1\) 是最小的正整數，然后就是雙序列擴展的前一半的貪心。

CSP-S模擬18

敗筆是 T1 寫了一個糖做法卡了一輩子空間，最后改成了 meet-in-middle，但是暴力過了。

它有任何一場卡掉暴力了嗎？——wang54321

1. 名字（name）

   很好的題。

   首先有一個暴力拆式子的做法，不好玩，還特別長，這里就不寫了。

   考慮 \(dis(u, v) = dep_u + dep_v - 2dep_{{\rm lca}(u, v)}\)

   \(dep_u\) 顯然前綴和優(yōu)化 \({\cal O}(n)\) 遞推。

   接下來發(fā)現關鍵性質，\(u < v\) 時 \({\rm lca}(u, v)\) 只和 \(u\) 有關。證明就是發(fā)現 \({\rm lca}\) 按 \(a\) 等比分布在 \([1, u]\)。

   考慮講 \({\rm lca}(u, v)\) 變成 \({\rm lca}(u, u + 1)\)，這樣考慮 \(u + 1\) 的父親，若是 \(u\) 則直接結束，否則規(guī)約到 \({\rm lca}(fa_{u + 1}, u)\) 即 \({\rm lca}(fa_{u + 1}, fa_{u + 1} + 1)\)。

2. 好難（toohard）

   省集題，qoj bitset master，我這次改了。

   發(fā)現若 \(S_v\) 中包含 \(u\) 當且僅當存在一條遞增的路徑 \(u \rightsquigarrow v\)。

   考慮點分，考慮統(tǒng)計經過根的路徑。

   處理出每個點到達根的最早時間 \(t\)，這部分是一個很有意思的 \(dp\)，設 \(dp_{v, t}\) 表示 \(v\) 在時刻 \(t\) 的值，但是我們發(fā)現 \(v\) 一定是 \(t\) 所對應邊的淺的端點，所以只用記錄 \(t\) 即可。

   將所有操作存下來，按時間依次掃，動態(tài)維護根到每個點最晚的出發(fā)時刻，這部分也很簡單。最后用樹狀數組維護一下后綴和即可。

   注意最后要斥掉子樹內的貢獻，這個直接每個子樹在做一遍就行。

   有些細節(jié)，感覺其實并不太難寫。

3. 取?。╯elect）

   首先將期望拆成 \(n\) 個點 \(k\) 條不重復非自環(huán)邊不連通的圖的概率乘上一個不動的期望次數。

   難點在于求 \(n\) 個點 \(k\) 條不重復非自環(huán)邊連通的圖的方案數。

   考慮 [集訓隊作業(yè)2013] 城市規(guī)劃，直接即可寫成多項式卷積的形式，\(n^6\) 的。

   上個拉插即可。

   注意到另外一種方式 dp 即考慮每次加入一條邊將兩個連通塊拼起來的方案數。

   但這個要做 EGF 的平移，有沒有大手子講解一下這個東西有沒有前途。

2026省選模擬3

T3 暴力是 \(n^2\) 的，但他開了 5s。

它有任何一場卡掉暴力了嗎？——wang54321

賽后改時限了。

1. GCD再放送

   首先你會莫反轉成枚舉倍數。

   然后你考慮一下一個數的貢獻，發(fā)現形如三段拼起來，我們直接枚舉前面一段，然后暴力做即可。

2. dict

   首先會一個暴力 \(n ^ 2\) 的類數位 dp 狀物。

   然后發(fā)現其形式形如一個分裂，我們直接上啟發(fā)式分裂即可。

【HT-076-NOI】核桃NOI組周賽

1. 鮑勃雜貨店

   唐詩題。

   總之就是你建出來表達式樹以后就是一個流狀物。然后直接暴力做。

   總之是能分析到 \(|\sum| ^ 2 n\) 自信一發(fā)直接過。

2. 爭鋒頻道

   這個真好題。

   首先你隨意將兩個點分成一組，組內連虛邊，我們考慮合法的匹配，發(fā)現是若干個虛實相交的環(huán)狀物。

   然后便是暴力做環(huán)在 Exp 即可。

【HT-NOI-011】南外命題賽

T1 再現經典結論，dp 轉移前后各搞 \(1000\) 個即可。

它有任何一場卡掉暴力了嗎？——wang54321

1. 小D與電梯

   總之就是你發(fā)現只有笛卡爾樹上左鏈部分有用，直接暴力 dp 加隨便什么東西優(yōu)化一下就過了。

2. 比賽

   \(n ^ 5\) 的區(qū)間 dp 加拼包直接砍下 71pts

   然后你發(fā)現關鍵結論，就是一點 \(p\) 活到了最后那么它就天然把序列分成兩段，這樣我們只用記錄左右端點獲勝的概率，前綴和優(yōu)化一下即可 \(n ^3\)

3. 寵物Jie的調皮操作

   這唐詩三合一串題誰愛寫誰寫去吧。

   值得一提的是我們造數據的時候發(fā)現 qoj 和 uoj 的好多代碼都是錯的（連下發(fā)的 std 都是錯的），它正式數據好像值域 $ < 10$，我大受震撼。

   qoj 唯一活了的代碼是因為鎖了不能叉，這下子知道為什么鎖了。

【S組 第二輪】信息學競賽10w選手模擬考

你 TM 的大樣里這么給是吧，狂掛 \(45\)。

1. 陽光收集

   傳話游戲，只用看前一半