本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-17 14:00:54

题意

给定 $s,t$ 两个 $01$ 串，有以下两种操作：

• 若 $s_i=0$ 且 $s_{i+2}=0$，可将 $t_{i+1}$ 赋为 $1$。
• 若 $t_i=1$ 且 $t_{i+2}=1$，可将 $s_{i+1}$ 赋为 $1$。

求经过若干次操作后 $s$ 中 $1$ 的最大个数。

思路

考虑一个区间的最优操作方案，发现先用 $s$ 中的 $0$ 把 $t$ 中所有能变 $1$ 的变完，再把 $s$ 中所有能变 $1$ 的变完，这样一定是最优的，因为这样保证了第一步之后 $t$ 中的 $1$ 最多，从而最终 $s$ 中的 $1$ 也最多。

接着考虑每一位会怎样被改变。若 $s_i$ 被变为 $1$，需要 $t_{i-1}=1$ 且 $t_{i+1}=1$，$t$ 的这两位又会受到 $s_{i-2},s_i,s_{i+2}$ 的影响，所以对于每一位 $s_i$，都只会受到 $[i-2,i+2]$ 区间内的影响。

因此可以提前对整个区间进行操作，并对最终的 $s$ 求前缀和。询问长度不超过 $4$ 时直接暴力操作求解。超过 $4$ 时由于 $[l+2,r-2]$ 只受区间 $[l,r]$ 内的影响，答案不变，直接记录下原来的答案，再单独对 $[l,l+4]$ 操作并记录前两位的答案，对 $[r-4,r]$ 操作并记录后两位的答案，把三部分相加即可。

代码

#include<iostream>
using namespace std;
const int N=2e5+10;
int n,q,pre[N],s[N],t[N],ts[N],tt[N];
char ss[N],st[N]; 
void solv(int l,int r)
{
	int len=r-l+1;
	for(int i=l;i<=r;i++) ts[i-l+1]=s[i],tt[i-l+1]=t[i];
	for(int i=1;i+2<=len;i++) if(!ts[i]&&!ts[i+2]) tt[i+1]=1;
	for(int i=1;i+2<=len;i++) if(tt[i]&&tt[i+2]) ts[i+1]=1;
	for(int i=1;i<=len;i++) ts[i]+=ts[i-1];
}
void sol()
{
	cin>>n>>ss>>st>>q;
	for(int i=1;i<=n;i++) s[i]=ss[i-1]-'0',t[i]=st[i-1]-'0';
	solv(1,n);
	for(int i=1;i<=n;i++) pre[i]=ts[i];
	while(q--)
	{
		int l,r; cin>>l>>r;
		if(r-l<4) solv(l,r),cout<<ts[r-l+1]<<'\n';
		else
		{
			int res=pre[r-2]-pre[l+1];
			solv(l,l+4),res+=ts[2];
			solv(r-4,r),res+=(ts[5]-ts[3]);
			cout<<res<<'\n';
		}
	}
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T; cin>>T;
	while(T--) sol();
	return 0;
}