掛得很慘，分?jǐn)?shù)就不說了。

Pro.A

這種題目都做不出來，我可以退役了，哇哦！

其實(shí)很簡單的，想復(fù)雜了。

弄一個遞歸，考慮每種情況——由于這個所謂 \(c\) - 好串是有一側(cè)全是 \(c\) 還有一側(cè)是 \(c+1\) - 好串，可以把左右兩側(cè)分別為 \(c\) 的情況各考慮一下，然后遞歸去處理就行。遞歸邊界 \(l=r\)，看這一位是不是等于 \(c\) 算代價即可。

Pro.B

“少考慮了一種情況”——這話從何說起呢。

考慮最優(yōu)性。對于第 \(i\) 關(guān)，有兩種處理方法：

• 用手槍一個一個地打死小怪，用 AWP 打死 boss。
• 用手槍攻擊所有怪，或者用一次激光槍，讓 boss 血量 \(-1\)，隨后被迫移動到第 \(i+1\) 關(guān)。

對于被迫移動的情況，又有兩種方法！

• 折回來，打第 \(i\) 關(guān)的 boss。
• 用手槍攻擊所有怪，或者用一次激光槍，讓 boss 血量 \(-1\)，隨后被迫移動到第 \(i\) 關(guān)，然后再用手槍打死第 \(i\) 關(guān)的 boss，折回第 \(i+1\) 關(guān)，一樣用手槍打死 boss，最后移動到第 \(i+2\) 關(guān)。

第二種方法確實(shí)有點(diǎn)繞啊我呃呃。

然后根據(jù)這些移動的信息方法去對應(yīng) DP 就可以了，轉(zhuǎn)移式很簡單的，注意細(xì)節(jié)，尤其考慮 \(d\) 的個數(shù)處理。

Pro.C

主播主播，你這個掃描線加樹狀數(shù)組還是太吃操作了！

考慮離線這些操作，按 \(n-y\) 分組存進(jìn) vector，然后依次遍歷 \(i\)，遍歷到了就回答，最后在一次性輸出。

考慮用樹狀數(shù)組維護(hù)差值次數(shù)前綴和，可以根據(jù)這個數(shù)值判斷某個值是否有移出去的希望；每次二分找最小 \(res\) 使 \(res\) 的前綴和值滿足條件，然后兩次 upd 更新與 \(res\) 相關(guān)的具體前綴和值，原理和差分有點(diǎn)相似。然后最后回答就可以了，總的來說是不難的。

重點(diǎn)在于這個 \(res\) 的范圍數(shù)值求解，也就是這個二分的所謂“滿足條件”是什么意思——其實(shí)就是要 \(\ge i - a_i\) 啦。

Pro.D

升級版本的歐拉回路，好玩！

其實(shí)整個的本質(zhì)就是在判斷是否存在一個歐拉回路。而且這個歐拉回路還必須包含所有要求經(jīng)過的邊。

通過并查集把所有并不強(qiáng)制要求經(jīng)過的邊全部合并起來，還要記錄每個點(diǎn)的度數(shù)，當(dāng)然啦，這里的度數(shù)只包括要求經(jīng)過的邊！因?yàn)檫@才是歐拉回路的核心基底。

然后要求的不就是把這些點(diǎn)弄成偶數(shù)嘛，這還不簡單，考慮這個修改的本質(zhì)過程，兩邊的奇偶性同時變化，相互消除嘛，但是只有一個節(jié)點(diǎn)是奇數(shù)度數(shù)那就消不動咯，因此只要連邊后的這些集合中沒有哪個集合只有一個度數(shù)為奇數(shù)的點(diǎn)就行了，否則相互拼湊總是可以消成功的。