Codeforces Round #627 (Div. 3) B

题意：

问一个数组中是否存在至少长为3的回文子数组（按下标排列，可不连续）。

思路：

找三个相同数或两个不连续的相同数。

#include <bits/stdc++.h>
using namespace std;
 
const int M=5500;
 
void solve(){
    int last[M]={0},cnt[M]={0};
 
    int n;cin>>n;
    int a[n+1];for(int i=1;i<=n;i++) cin>>a[i];
 
    for(int i=1;i<=n;i++){
        if((++cnt[a[i]]==3)||(last[a[i]]&&last[a[i]]!=i-1)){
            cout<<"YES
";
            return;
        }
        last[a[i]]=i;
    }
    
    cout<<"NO
";
}
 
int main(){
    int t;cin>>t;
    while(t--)
        solve();
    return 0;
}

更新 ：

二者实为一种情况。

#include <bits/stdc++.h>
using namespace std;
 
const int M=5500;
 
void solve(){
    int first[M]={0};
 
    int n;cin>>n;
    int a[n+1];for(int i=1;i<=n;i++) cin>>a[i];
 
    for(int i=1;i<=n;i++){
        if(first[a[i]]==0){
            first[a[i]]=i;
        }
        else if(first[a[i]]<i-1){
            cout<<"YES
";
            return;
        }
    }

    cout<<"NO
";
}
 
int main(){
    int t;cin>>t;
    while(t--)
        solve();
    return 0;
}