题解：AT_abc381_d [ABC381D] 1122 Substring

daitangchen2008 · 2024-11-23 13:22:39 · 题解

分析：

分成两种情况：从 1 开始和从 2 开始，分类讨论。
记以每个 i 位置为最后位置的串的开头为 j，那答案即为最大的 i-j。
每次更新 j 时，先判断相邻的两个位置是否相同。如果不同就更新；再判断是否出现过，出现过再更新 j。每次操作结束后更新位置。
时间复杂度 O(n)，可以通过。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fi first
#define se second
#define ce continue
const int N=5e5+10;
const int mod=998244353;
priority_queue<int> q;
set<int> s;
stack<int> sta;
int n;
int a[N];
string st;
int mhash[N];
signed main()
{
    int n;
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int last=0;
    int duan=0;
    for(int i=2;i<=n;i+=2)
    {
        if(a[i]!=a[i-1])
        {
            duan=i;
            continue;
        }
        ans=max(ans,i-max(duan,mhash[a[i]]));
        if(mhash[a[i]]!=0)
        duan=max(duan,mhash[a[i]]);
        mhash[a[i]]=i;
    }
    for(int i=1;i<=N-300;i++)
        mhash[i]=0;
    duan=1;
    for(int i=3;i<=n;i+=2)
    {
        if(a[i]!=a[i-1])
        {
            duan=i;
            continue;
        }
        ans=max(ans,i-max(duan,mhash[a[i]]));
        if(mhash[a[i]]!=0)
        duan=max(duan,mhash[a[i]]);
        mhash[a[i]]=i;
    }
    cout<<ans<<endl;
    return 0;
 }