题解：AT_abc381_d [ABC381D] 1122 Substring

将数组

a

变成元素加个数的形式，元素数组为

b

，个数为

c

，如

\mathtt{1,1,2,2,3,3,3}

，

b

就是

\mathtt{1,2,3}

，

c

就是

{2,2,3}

。用双指针来做。用

v

统计是否出现，

j

表示左指针，

i

表示右指针。统计答案就是

i-j+1

。

当 $c_i=1$ 时，说明 $i$ 不能贡献，直接将 $j$ 移动到 $i+1$ 。
当 $c_i>2$ 时， $i$ 只能作为开头或结尾，若 $b_i$ 没出现过，统计一次答案。然后将 $j$ 移动到 $i$ ，标记 $b_i$ 出现。
当 $c_i=2$ 时，若 $b_i$ 出现过，则一直移动 $j$ 直到 $v_{b_i}=0$ 。然后标记 $b_i$ 出现。

移动

j

时要将

v_{b_j}

变为

0

。

CPP

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=2e5+5;
int n;
int a[N],b[N],c[N];
int v[N];
void solve()
{
    cin>>n;
    int tot=0;
    for(int i=1;i<=n;i++) 
    {
        cin>>a[i];
        if(a[i]!=a[i-1]) b[++tot]=a[i],c[tot]=1;
        else c[tot]++;
    }
    int j=1,ans=0;
    for(int i=1;i<=tot;i++)
    {
        if(c[i]<2) while(j<=i) v[b[j++]]=0;
        else if(c[i]>2) 
        {
			if(!v[b[i]]) ans=max(ans,(i-j+1)*2);
            while(j<i) v[b[j++]]=0;
            v[b[i]]=1;
        }
        else 
        {
            while(j<=i&&v[b[i]]) v[b[j++]]=0;
            v[b[i]]=1;
        }
        if(j<=i) ans=max(ans,(i-j+1)*2);
    }
    cout<<ans<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

题解：AT_abc381_d [ABC381D] 1122 Substring

文章操作

相关推荐

评论

题解：AT_abc381_d [ABC381D] 1122 Substring