CF1392G-Omkar and Pies【dp】

正题

题目链接:https://www.luogu.com.cn/problem/CF1392G

---

题目大意

两个长度为$k$的起始和目标01串。
$n$个操作交换起始串的两个位置，选择一段长度至少为$m$的连续操作序列使得相同的位数最多。
$1\le m\le n\le 10^6,1\le k\le 20$

---

解题思路

因为是从前往后操作，所以可以拆成两个后缀$[l,n]$和$[r+1,n]$。

对$S$执行$l\sim n$然后对$T$执行$r+1\sim n$之后比较就好了。

额考虑怎么做这个东西，我们可以$O(nk)$的处理出一个$s_i$表示对$S$执行了$i\sim n$之后的序列，$t_i$表示对$T$执行了$i\sim n$之后的序列，当然要用二进制压起来。

然后我们要找到一对$l,r$使得$r-l\ge m$且$s_{l}xor{t}_r$的$1$最多。

有个做法是考虑$sandt$的$1$数，因为$s$和$t$的$1$数固定。设$sandt$有$z$个$1$，$s$有$x$个$1$，$t$有$y$个$1$，那么他们相同的位数有$z+(k-x-y+z)=2z+k-x-y$个，所以其实是要最大化$z$就好了。

设$f_i$表示一个最小的$k$使得$s_{k}andi=i$，$g_i$则是表示对于$t$来说最大的$k$。

然后求出这两个就可以搞定这题了，因为是最值所以不需要用到$\text{FWT}$，直接$dp$就好了。

时间复杂度$O(nk)$

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1<<20;
int k,n,m,s,t,zx[N],zy[N],f[N],g[N],bit[N],rev[N][20];
char st[30];
int swp(int s,int p){
	int ans=0;
	for(int i=0;i<k;i++)
		ans|=(((s>>rev[p][i])&1)<<i);
	return ans;
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	scanf("%s",st);
	for(int i=0;i<k;i++)
		s|=(st[i]-'0')*(1<<i);
	scanf("%s",st);
	for(int i=0;i<k;i++)
		t|=(st[i]-'0')*(1<<i);
	for(int i=1;i<=n;i++){
		int x,y;
		scanf("%d%d",&x,&y);x--;y--;
		for(int j=0;j<k;j++)rev[i][j]=j;
		swap(rev[i][x],rev[i][y]);
	}
	for(int i=n-1;i>=1;i--){
		int tmp[k];
		for(int j=0;j<k;j++)
			tmp[j]=rev[i][rev[i+1][j]];
		for(int j=0;j<k;j++)rev[i][j]=tmp[j];
	}
	memset(f,0x3f,sizeof(f));
	for(int i=n;i>=1;i--){
		int x=swp(s,i);f[x]=min(f[x],i);
		x=swp(t,i);
		g[x]=max(g[x],i);
	}
	g[t]=n+1;int MS=(1<<k);
	for(int i=1;i<MS;i++)
		bit[i]=bit[i-(i&-i)]+1;
	int ans=-1,ansl=0,ansr=0;
	for(int i=MS-1;i>=0;i--){
		for(int j=0;j<k;j++){
			f[i]=min(f[i],f[i|(1<<j)]);
			g[i]=max(g[i],g[i|(1<<j)]);
		}
		if(bit[i]>ans&&g[i]-f[i]>=m)
			ans=bit[i],ansl=f[i],ansr=g[i];
	}
	printf("%d\n%d %d\n",2*ans+k-bit[s]-bit[t],ansl,ansr-1);
	return 0;
}