题意
给定两个长度为 \(k\) 的字符串 \(s, t\)。
设两个字符串的相似度为 \(\sum_{i = 1} ^ {k} [s_i = t_i]\)。
给定 \(n\) 个操作，每次操作交换 \((s_{x}, s_{y})\)，你需要求出对于所有 \(\forall l, r, r - l + 1 \ge m\) 的相似度最大的 \(l, r\)。
\(n \le 10 ^ 6, k \le 20\)
Sol
显然直接从 \(l \to r\) 是不好做的。
手玩一下这个操作可以发现若 \(s, t\) 同时做某些操作，相似度是不变的。
其次显然这个操作是可逆的，用 \(t\) 从 \(r\) 做到 \(l\) 与 \(s\) 从 \(l\) 做到 \(r\) 是等价的。
因此我们可以构造出一种方式，让 \(s\) 从 \(l\) 操作到 \(n\)，\(t\) 从 \(r + 1\) 操作到 \(n\)，然后再求两串的相似度。
集中注意力，考虑怎么让相似度好算一点。
发现使相似度最大等价于两串相同为 \(1\) 的位数最多，因为两串 \(1\) 的个数确定，拆开过后就之和相同 \(1\) 的位数有关了。
发现值域很小，直接暴力上 \(\text{dp}\)，设 \(f_{0, S}\) 表示 \(S \subseteq s\) 的最小左端点， \(f_{1, S}\) 表示 \(S \subseteq t\) 的最大右端点，\(S\) 的含义是 \(S\) 集合中的这些位有相同的 \(1\)。
简单 \(\text{dp}\) 一下，判断左右端点的长度，最后输出最大的 \(\text{popcount}\) 即可。
标签：le,20240706,省选,text,T2,相似,端点,操作,两串 From： https://www.cnblogs.com/cxqghzj/p/18299464