CF1392G Omkar and Pies 题解

考虑如果把同样的一段操作序列同时给两个串做，对答案是没有影响的。所以考虑把每个区间差分成后缀（不能是前缀，因为这样相同的操作序列在前面没法抵消），这样就可以表示区间了。两个串分别的对每个后缀操作之后得到的串可以 \(O(nk)\) 算出来，就是记录每个位置最终会被换到哪里就可以从右向左递推。

算出两个串前后缀之后（设为 \(a_i,b_i\)），考虑如何计算答案：设 \(a,b\) 中 \(1\) 的个数分别为 \(p,q\)，\(a,b\) 重合的 \(1\) 的个数为 \(r\)，那么答案为 \(k-p-q+2r\)。\(k,p,q\) 都是常数，现在只需要使 \(r\) 最大。注意到最终的情况只有 \(2^k\) 种，考虑直接枚举答案。设 \(f_S=\min\{i|S\subset a_i\},g_S=\max\{i|S\subset b_i\}\)，对于每个 \(S\) 判断 \(g_S-f_S\) 是否 \(\geq m\) 即可更新答案。对于 \(f,g\) 值只需要从大到小递推一下就可以了，这部分复杂度是 \(O(2^k\cdot k)\)。

所以总的复杂度为 \(O(nk+k2^k)\)，可以通过此题。

const int N=1e6+13,M=(1<<20)+13,K=20+1;
int n,m,k,l[N],r[N],a[N],b[N],f[M],g[M];
int pos[N][K];
char ina[K],inb[K];
int main(){
//file();
	read(n),read(m),read(k);
	read(ina),read(inb);
	for(int i=1;i<=n;++i){
		read(l[i]),read(r[i]);
		--l[i],--r[i];
	}
	int x=0,y=0,p=0,q=0;
	for(int i=0;i=0;--s){
		int cnt=0;
		for(int i=0;i>i)&1);
		if(cnt>ans&&g[s]-f[s]>=m) ans=cnt,ansl=f[s],ansr=g[s]-1;
		for(int i=0;i>i)&1)) continue;
			f[s^(1<