列表 題解

浩瀚星空里
只剩你的背影
銀河已凝結(jié)成冰
記憶滑過(guò)淚滴
想象能回到過(guò)去
終會(huì)存在我心底
雖然逃避
她消失在夢(mèng)里
日出的幻境
再次感覺(jué)到你
風(fēng)送來(lái)你的呼吸
月色倒映著驚喜
原來(lái)你從未離去
默默守護(hù)在這里
無(wú)聲無(wú)息
如影隨形
我不再迷茫
思念是唯一的行囊
漫天的星光
有一顆是你的愿望
前方的路不再孤單漫長(zhǎng)
天空下你我不再守望
輕聲歌唱
在我身旁
日出的幻景
再次感覺(jué)到你
風(fēng)送來(lái)你的呼吸
月色倒映著驚喜
原來(lái)你從未離去
默默守護(hù)在這里
無(wú)聲無(wú)息
如影隨形
我不再迷茫
思念是唯一的行囊
漫天的星光
有一顆是你的愿望
前方的路不再孤單漫長(zhǎng)
天空下你我不再守望
輕聲歌唱
在我身旁
我不再迷茫
思念是唯一的行囊
漫天的星光
有一顆是你的愿望
前方的路不再孤單漫長(zhǎng)
天空下你我不再守望
輕聲歌唱
在我身旁

其實(shí)昨天頂真就讓寫(xiě)了，但一直沒(méi)時(shí)間，今天補(bǔ)上來(lái)得及嗎 QwQ？

但好像就算寫(xiě)了也基本沒(méi)人看的懂。

首先先考慮題面在干啥，相當(dāng)于是先選最中間的，如果刪掉左邊一個(gè)，就選一個(gè)右邊，如果刪掉右邊一個(gè)就選上左邊。

顯然答案具有單調(diào)性，考慮二分區(qū)間長(zhǎng)度，枚舉左端點(diǎn) \(L\)，將在答案區(qū)間的點(diǎn)在原序列標(biāo)記成 \(1\)，否則是 \(0\)。

于是問(wèn)題轉(zhuǎn)化為如何判斷是否能取到所有 \(1\)。

考慮雙指針 \(l,r\) ，初始時(shí) \(l=n\) 和 \(r=n+2\) 處，表示下一次可能選的值，顯然每次是盡可能刪掉近的 \(0\)，且不能刪 \(1\)，考慮若 \(l,r\) 中有一個(gè)是 \(0\)，則一定是刪掉 \(0\) 使得 \(l,r\) 同時(shí)向左右跳一個(gè)，若是都是 \(1\)，就是刪掉左邊或右邊最近的一個(gè)，使另一邊跳一個(gè)，容易發(fā)現(xiàn)刪掉左邊和右邊是一樣的，最后跳到頭證明都能取，否則一定有一組 \(1\) 卡住了不能都取。

模擬即可達(dá)到 \(O(n)\) 的復(fù)雜度。

考慮優(yōu)化，發(fā)現(xiàn)在枚舉 \(L\) 時(shí)每次只會(huì)增刪一個(gè)值，考慮動(dòng)態(tài)維護(hù)判斷。

首先發(fā)現(xiàn)在都是 \(1\) 時(shí)指針的跳動(dòng)不對(duì)稱(chēng)，考慮改變操作，變?yōu)閷⒆罱?\(0\) 變成 \(1\)，兩邊同時(shí)跳一個(gè)，容易發(fā)現(xiàn)其剩余對(duì)于序列沒(méi)有變化。

于是將兩邊一起考慮，當(dāng)值是 \((0,0),(0,1),(1,0)\) 時(shí)直接跳，當(dāng)值是 \((1,1)\) 時(shí)要將后面一個(gè) \(0\) 變成 \(1\)。

發(fā)現(xiàn)只有 \((1,1)\) 可能會(huì)卡住，考慮 \((0,1)\) 改掉一個(gè) \(0\) 會(huì)變成 \((1,1)\)，并不會(huì)有貢獻(xiàn)，\((1,0)\) 同理，只有 \((0,0)\) 可以消掉一個(gè)。

設(shè) \((1,1)\) 的貢獻(xiàn)為 \(1\)，\((0,0)\) 的貢獻(xiàn)是 \(0\)，因?yàn)榇笥?\((1,1)\) 個(gè)數(shù)的 \((0,0)\) 不會(huì)有貢獻(xiàn)，于是問(wèn)題變成了從前往后依次加，動(dòng)態(tài)對(duì) \(0\) 取 \(max\)。

這是一個(gè)經(jīng)典問(wèn)題，考慮 沖刺CSP聯(lián)訓(xùn)模擬2——星空遺跡 的做法，將對(duì) \(0\) 取 \(\max\) 拆掉，問(wèn)題變成最后是依次加的歷史最小值，可以線段樹(shù)上二分，也可以維護(hù)前綴和后區(qū)間加區(qū)間 \(\min\)。