CF1978E 题解

KSCD_ · 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;
}