原题链接 (Hard
Version)
思路:
设数组 \(sum(c,r)\) 表示数字 \(c\) 在区间 \([1,r]\) 的个数，数组 \(cnt(c,k)\) 表示第 \(k\) 个 \(c\) 的位置.
经过分析可知，若第一个区间 (和第三个区间) 有 \(k\) 个数字 \(a\), 若要使区间最长，这 \(k\) 个数字是最左边 (和最右边) 的 \(k\) 个 \(a\).
假设第一个区间 (和第三个区间) 为 \(k\) 个数字 \(a\), 则第二个区间的左端点 \(l=cnt(a,k)+1\), 右端点 \(r=cnt(a,sum(a,n)-k+1)-1\),
则第二个区间长度的最大值为 \(m =
\max\limits_{c=1}^{200} \{ sum(c,r)-sum(c,l-1) \}\),
序列总长度为 \(2k + m\).
枚举 \(k\) 与数字 \(a\) 即可得到最大长度，时间复杂度 \(O(an)\)(\(a\) 为原数组 \(a_i\) 的最大值), 空间复杂度 \(O(an+n)\).
原先写了个 O (an^2) 的代码交 easy ver. 结果被 hack 了 QAQ
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <cstring>
#include <cstdio>
#include <vector>
using std::vector;
const int Mn(200500),Ma(205);
int sum[Mn][Ma];
vector<int> cnt[Ma];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
for(vector<int>& a:cnt)
a.clear();
int mxa(0);
for(int i(1);i<=n;++i)
{
int a;
scanf("%d",&a);
memcpy(sum[i],sum[i-1],sizeof sum[i]);
++sum[i][a];
cnt[a].push_back(i);
if(mxa<a) mxa = a;
}
int ans(1);
for(int i(1);i<=mxa;++i)
{
int jmx = cnt[i].size()/2;
for(int j(1);j<=jmx;++j)
{
int l(cnt[i][j-1]+1),r(cnt[i][cnt[i].size()-j]-1);
for(int k(1);k<=mxa;++k)
ans = ans<(2*j+sum[r][k]-sum[l-1][k]) ? (2*j+sum[r][k]-sum[l-1][k]) : ans;
}
}
printf("%d\n",ans);
}
return 0;
}
|