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))