CF1335E2 Three Blocks Palindrome (hard version)

本题解也可通过CF1335E1 Three Blocks Palindrome (easy version)。做法值域很小。只有200考虑从这里入手。我们设q[i][j]表示数i第j次出现的位置sum[i][j]表示种类i在1到j范围内出现过多少次。枚举 a,b 具体的值枚举 x答案就是 22xnumnum 是第x 个 a 出现的位置加一到倒数第 x 个 a 出现的位置减一区间里边 b 的数量。这题卡空间所以我们不能#define int long long不然你会Memory limit exceeded on test 1不嘻嘻。代码(求赞)#includebits/stdc.h using namespace std; const int N2e55,M2e25; int T,n,ans1,a[N],sum[M][N];//q[i][j]表示数i第j次出现的位置sum[i][j]表示种类i在1到j范围内出现过多少次。 vectorint q[M]; int main(){ scanf(%d,T); while(T--){ ans1; scanf(%d,n); for(int i0;i200;i){ sum[i][0]0; q[i].clear(); q[i].push_back(0); } for(int i1;in;i){ scanf(%d,a[i]); q[a[i]].push_back(i); for(int j0;j200;j){ sum[j][i]sum[j][i-1]; } sum[a[i]][i]sum[a[i]][i-1]1; } if(n1){ printf(1\n); continue; } for(int i1;i200;i) q[i].push_back(n1); for(int i1;i200;i){ if(q[i].size()2) continue; for(int j1;j200;j){ if(q[j].size()2) continue; for(int k0;2*kq[i].size()-2;k){ ansmax(ans,2*ksum[j][q[i][q[i].size()-k-1]-1]-sum[j][q[i][k]]); } } } printf(%d\n,ans); } return ~(-1); }