數(shù)數(shù)題。數(shù)數(shù)題。數(shù)數(shù)題。

2024暑期CSP-S&NOIP模擬賽第8套

鏈接：link
題解：暫無

時(shí)間：4h (2025.10.28 14:00~18:00)
題目數(shù)：4
難度：

估分：100 + [0,20] + 80+ 0 = [180,200]
得分：100 + 0 + 80 + 0 = 180
Rank：2/6

場(chǎng)祭

讀題。

怎么三個(gè)數(shù)數(shù)題 /jk，要寄

A 簽。

B 一眼容斥，然后就沒有然后了，發(fā)現(xiàn)怎么容斥都是只過小樣例。1h 拼盡全力無法戰(zhàn)勝，然后寫了個(gè) \(O(n^2)\) 的反演還是錯(cuò)的，最后就只寫了個(gè)暴力了，然后發(fā)現(xiàn)似乎加個(gè)記憶化就可以跑到起飛，于是打了個(gè) \(200\) 的表，結(jié)果一測(cè)還是之過小樣例，哦哦忘了考慮在胡亂填字符的時(shí)候填到 SOS 的情況了，加上之后……還是過不了。

不管了扔掉了。浪費(fèi)了太多時(shí)間了。

開 C，\(c=1\) 的特殊性質(zhì)是容易的，單步容斥即可，然后想了下正解，發(fā)現(xiàn)答案是這個(gè)：

想到這里就打算扔掉了，畢竟看起來不是任何可反演的形式，但是等等……注意到后面可以等價(jià)于在 \(n\) 個(gè)數(shù)中選若干個(gè)，所以可以考慮一個(gè) dp 令 \(f_{i,j}\) 為前 \(i\) 個(gè)數(shù)選 \(j\) 個(gè)的答案，帶修之后就是一個(gè) DDP 然后直接上線段樹即可。

但是分析一下發(fā)現(xiàn)復(fù)雜度達(dá)到了恐怖的 \(O(qc^2 \log n)\)，大樣例跑了 11s，加點(diǎn)優(yōu)化變成了 3.4s，不過這個(gè)大樣例強(qiáng)度很弱啊，那應(yīng)該是卡不過去了。

D 怎么一點(diǎn)暴力分不給 /fn

補(bǔ)題

B 怎么是 dp。關(guān)鍵是你長(zhǎng)得太像容斥了啊喂！

補(bǔ) C，學(xué)習(xí)到了新科技：退背包。

例題是洛谷 P4141。題意是 \(n\) 個(gè)物品 \(a_i\)，背包最大容積 \(m\)，求 \(\forall i \in [1,n] , j \in [1,m]\)，刪掉 \(a_i\) 這個(gè)物品后，選擇一些物品使其體積之和為 \(j\) 的方案數(shù)。要求復(fù)雜度 \(O(nm)\)。

思路：考慮在暴力做背包的時(shí)候，有轉(zhuǎn)移 \(f_j \gets f_{j-a_i}\)，而由于是背包，所以 \(a_i\) 的枚舉順序是不影響答案的，于是在刪掉一個(gè) \(a_i\) 的時(shí)候，可以直接把背包刪掉一個(gè)元素，變成 \(f_j \gets - f_{j-a_i}\)，就可以得到刪掉 \(a_i\) 的答案了。

注意正常背包的枚舉順序是 rpe(j,m,0)，退背包的枚舉順序應(yīng)為 rep(j,0,m)。

于是這個(gè)題也是一樣的，對(duì)上面那個(gè) dp 做退背包即可，一次退背包復(fù)雜度是 \(O(c)\) 的。

然后退背包式子的推導(dǎo)就是根據(jù)背包來推的，令考慮 \(i\) 前的 dp 數(shù)組為 \(f\)，考慮 \(i\) 后的為 \(f’\)，則背包的式子為：

從這個(gè)式子出發(fā)反推回去，把 \(f_j\) 單獨(dú)放一邊，就可以得到退背包的式子：

這也是為什么要和背包枚舉順序相反的原因，只有這樣才能在求 \(f_j\) 的時(shí)候保證 \(f_{j-1}\) 是刪掉 \(i\) 后的 dp 值。

天依寶寶可愛！