题解：AT_abc381_c [ABC381C] 11/22 Substring

Hughpig · 2024-11-23 10:50:54 · 题解

观察发现，每个 11/22 字符串都可以看作一个 \texttt{/} 字符，前面跟着若干个 1，后面跟着若干个 2 构成。为了最大化答案，前后的 1 和 2 的个数要尽可能多，可以取到前面 1 个数和后面 2 个数的较小值。

先预处理出两个数组 a,b。a_i 表示以 s_i 结尾最多有多少个 \texttt{1}，b_i 表示以 s_i 开头最多有多少个 \texttt{2}。

根据数组 a 的定义显然，如果 s_i 为 1，那么 a_i=a_{i-1}+1，否则 a_i=0。可以通过扫一遍 s 预处理出 a 数组。b 数组同理。

然后对于每个 s_i，如果 s_i=\texttt{/}，根据上文的分析，以 s_i 作为中间的 11/22 字符串最长长度可以取到 2\times \min(a_{i-1},b_{i+1})+1，更新答案即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define up(l,r,i) for(int i=(l);(i)<=(r);++i)

constexpr int N=2e5+9;

int n;string s;
int a[N],b[N],ans;

int main()
{
    cin>>n>>s;
    up(0,n-1,i){
        if(s[i]=='1')a[i]=a[i-1]+1;
        else a[i]=0;
    }
    for(int i=n-1;~i;--i){
        if(s[i]=='2')b[i]=b[i+1]+1;
        else b[i]=0;
    }
    up(0,n-1,i){
        if(s[i]=='/'){
            ans=max(ans,min(a[i-1],b[i+1])*2+1);
        }
    }
    cout<<ans;
    return 0;
}