codeforces Three Blocks Palindrome题解

先看看数据范围,1≤t≤104,1≤n≤2⋅105,1≤ai≤200注意到ai很小是吧?那么我们就可以dp[i][j]预处理它们的值i到当前j位子有多少个.
然后暴力就没了..3个for 200n的复杂度

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
typedef long long ll;
const ll inf=132913423200339;
const ll mod=998244353676776;
const int N=2e5+2;
const ll M=10+5;
const double eps=1e-7;
using namespace std;
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b) { return a*b/gcd(a,b);    }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a = (a*a)%p;b >>= 1;}return ans%p;}
ll Inv(ll x)          { return qp(x,mod-2,mod);}
ll C(ll n,ll m){if (m>n) return 0;ll ans = 1;for (int i = 1; i <= m; ++i) ans=ans*Inv(i)%mod*(n-i+1)%mod;return ans%mod;}
ll A(ll n,ll m,ll mod){ll sum=1; for(int i=n;i>=n-m+1;i--) sum=(sum*i)%mod; return sum%mod;}
ll lowbit(ll x) {return x&(-x);}
ll c[N],sum1[N],sum2[N],b[N],lsh[N],n,m,fa[13];
void add1(ll i,ll k){ while(i<=n) {c[i]+=k;i+=lowbit(i);}}//预处理ai单点修改 区间查询***预处理a[i]-a[i-1]区间修改单点查询
ll  Sum1(ll i) {ll res=0; while(i>0) res+=c[i],i-=lowbit(i);return res;}//预处理ai单点修改 区间查询***预处理a[i]-a[i-1]区间修改单点查询
void add2(ll i,ll k){ ll x=i;while(i<=n) {sum1[i]+=k;sum2[i]+=k*(x-1);i+=lowbit(i);}}//区间修改,区间查询
ll  Sum2(ll i) {ll res=0,x=i;while(i>0){ res+= x * sum1[i]-sum2[i]; i -= lowbit(i);}return res;}//区间修改,区间查询
//oid ls(){ll cnt; for(ll i=1;i<=n;i++) lsh[i]=a[i]; sort(lsh+1,lsh+n+1);cnt = unique(lsh+1,lsh+n+1)-lsh-1; for(int i=1;i<=n;i++)a[i]=lower_bound(lsh+1,lsh+cnt+1,a[i])-lsh;}
ll lca(ll x) { if(x==fa[x]) return x;else return fa[x]=lca(fa[x]); }//找祖先.
int dp[202+5][N+5];//记录当前位子每个数从1开始到i的个数
int a[N+5];
vector<int>v[205];
int main()
{
    int t,ans;
    scanf("%d",&t);
    while(t--)
    {
        ans=1;
        for(int j=1;j<=200;j++)  v[j].clear();
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=200;j++)
                dp[j][i]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=200;j++) dp[j][i]=dp[j][i-1];
            scanf("%d",&a[i]);v[a[i]].pb(i);
            dp[a[i]][i]++;
        }
        for(int i=1;i<=200;i++)//枚举每个点作为左右两区间的情况
        {
            if(v[i].size()<2) continue;//假如值还没有2,那肯定没有枚举的必要了啊
            for(int j=0;j<=v[i].size()/2-1;j++)//从最小的位子开始枚举向中间靠拢,中间单着的那个肯定没有选取的必要,因为要么前面已经记录,要么但凡中间出现一个数也与它相等
            {
                int l=v[i][j];int r=v[i][v[i].size()-j-1];
                for(int k=1;k<=200;k++)//枚举中间填哪个点..
                    ans=max(ans,dp[k][r-1]-dp[k][l]+2*(j+1));
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}