CF1392G

給定一個長度為 (k) 的 01 串 (s,t)，給定 (n) 個操作，第 (i) 個操作為交換 (s) 中的 (u_i) 和 (v_i)

然后你選擇一個區間的操作依次執行，這個區間的長度不能小于 (m)。

最大化 (s) 和 (t) 相同的位置數量。

(m,nle 10^6,kle 20)

Solution

神仙題。

設 (w(s,t)) 表示 (s) 和 (t) 得到的答案。

(p(l,r)) 表示順序操作 (l o r)

(p(r,l)) 表示順序操作 (r o l)

性質 1

若 (sxrightarrow{p(l,r)}s',txrightarrow{p(l,r)}t',w(s,t)=w(s',t'))

注意到每一位是獨立被操作了相同的，不會改變。

所以設 (sxrightarrow{p(l,r)}s')，那么若 (s'xrightarrow{p(r+1,n)}s'',txrightarrow{p(r+1,n)}t'')，則 (w(s',t)=w(s'',t''))

同理，答案也等價于 (s'xrightarrow{p(l-1,1)}s'',txrightarrow{p(r,1)}t'') 情況下的答案。

所以我們得到了 (n) 個字符串 (s') 和 (n) 個字符串 (t')，我們發現問題等價于選兩個下標差大于等于 (m) 的字符串并得到答案。

還是不好做。

然后觀察到，所有 (s/t) 的二進制下 (1) 的個數固定，設 ( extrm{bit}(s)) 為 (a)，( extrm{bit}(t)=b)，( extrm{bit}(s~mathbf{and}~t)=c)，那么有答案為 (k-(a-c)-(b-c)=k-a-b+2c)，所以問題等價于最大化 (c)

然后維護 (f_{0,x}) 表示所有 (s_i=x) 中最小的 (i)，維護 (f_{1,x}) 表示所有 (t_i=x) 中最大的 (i)

然后將他們進行子集轉移，對于某個 (x)，如果 (f_{1,x}-f_{0,x}ge m)，那么就可以更新答案，即存在兩個字符串滿足其并大于等于 ( extrm{bit}(x))。

復雜度為 (mathcal O(nk+2^kk))

總結

以上是生活随笔為你收集整理的CF1392G的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。