CF1335E1 Three Blocks Palindrome (easy version)

思路

发现一个进阶回文序列仅包含三个部分：\(x\) 个连续的 \(a\)，\(y\) 个连续的 \(b\)，\(x\) 个连续的 \(a\)。

对于一个 \(a\)，我们一定会取最外面的两个 \(a\)，如果不取，则答案一定不小或不变，所以我们枚举到 \(a\) 的时候，一定是确定了最外围的两个 \(a\) 的位置。

接下来再枚举 \(x\) 并算出最内层的 \(a\) 的位置，统计这两个位置之间其他数字的最大个数，也就是 \(y\) 然后更新答案即可。

可提前用 vector 储存每个数字出现的位置，用前缀和统计 \([1,i]\) 中某个数字出现的次数。

AC code

#include<bits/stdc++.h>
using namespace std;
int T,n,a[2005],ans,num[2005][27],res;
vector<int>v[27];
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		for(int i=1;i<=26;++i) v[i].clear();
		memset(num,0,sizeof(num));
		scanf("%d",&n),ans=1;//答案至少为1
		for(int i=1;i<=n;++i)
		{
			for(int j=1;j<=26;++j) num[i][j]=num[i-1][j];
			scanf("%d",&a[i]),v[a[i]].push_back(i),++num[i][a[i]];//前缀和统计出现次数
		}
		for(int i=1;i<=26;++i)
			if(v[i].size()>1)
			{
					res=0;
					for(int j=0;j<=(int)ceil(1.0*(v[i].size()-2)/2);++j)//枚举x
					{
						int l=v[i][j],r=v[i][v[i].size()-j-1];//找到最中间两个的位置
						if(l==r) ans=max(ans,res+1);//如果一样，则没有y，直接更新答案
						else
						{
							res+=2;
							for(int k=1;k<=26;++k) if(k!=i) ans=max(ans,res+num[r-1][k]-num[l][k]);//枚举每个数字作为b的情况，并更新答案
						}
					}
			}
		printf("%d\n",ans);
	}
	return 0;
}