Codeforces Round #634 (Div. 3) 比赛人数11922 慢慢的对Div. 3难度有了些感觉
[codeforces 1335E2] Three Blocks Palindrome (hard version) 从中间位置向两边扩散
总目录详见https://blog.csdn.net/mrcrack/article/details/103564004
在线测评地址https://codeforces.com/contest/1335/problem/E2
手工算法部分如下
8
1 1 2 2 3 2 1 1
数组位置 1 2 3 4 5 6 7 8
数组数值 1 1 2 2 3 2 1 1
1放两边的情况如下：
1的左右边界l=2,r=7
在位置区间[2+1,7-1],即在位置区间[3,6]寻找中间数据，发现2的数量最多，是3
此时对应的值是2*2+3=7
AC代码如下。代码中，注明的关键之处，都是在测试样例数据的过程中，调试出来的。
#include <cstdio>
#include <algorithm>
#define maxn 200010
using namespace std;
int cnt[205],a[maxn],loc[205][200010],ln[205];
int main(){
int t,n,l,r,i,j,b,mid,ans;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=1;i<=200;i++)ln[i]=0;//初始化，别忘了,关键之处
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
b=a[i];
ln[b]++,loc[b][ln[b]]=i;//loc[][]记录a[i]出现的位置i
}
ans=1;//关键之处
for(i=1;i<=200;i++){//i<=200
if(ln[i]<=1)continue;//特判,关键之处
if(ln[i]%2==0)l=ln[i]/2,r=l+1;//偶数
else l=ln[i]/2,r=l+2;//奇数
for(j=1;j<=200;j++)cnt[j]=0;
mid=0;
for(j=loc[i][l]+1;j<=loc[i][r]-1;j++)//中间区间
cnt[a[j]]++,mid=max(mid,cnt[a[j]]);
ans=max(ans,mid+l*2);
while(1){
l--,r++;//向两边扩散
if(l<=0)break;//关键之处
for(j=loc[i][l]+1;j<=loc[i][l+1];j++)//左区间腾出的空间
cnt[a[j]]++,mid=max(mid,cnt[a[j]]);
for(j=loc[i][r-1];j<=loc[i][r]-1;j++)//右区间腾出的空间
cnt[a[j]]++,mid=max(mid,cnt[a[j]]);
ans=max(ans,mid+l*2);
}
}
printf("%d\n",ans);
}
return 0;
}