我们只需要枚举
[1,
],[
+1,
],[
+1,
]三个区间即可,设
为第一个和第三个区间中出现最多的数字的次数,
为第二个区间中出现最多数字的次数,则
=
(
,
∗2+
)。我们可以维护一个前缀和数组
,令
[
][
]为前
位数字中
数字出现的次数,这样就可以方便的找到出现次数最多的数字。然后枚举第一个和第三个区间即可,中间区间数字的个数也可以通过前缀和来计算
#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long ll;
const int N=2020;
const int M=1e6+10;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
int cnt[N][30];
void solve(){
mst(cnt,0);
int n;cin>>n;
rep(i,1,n+1){
int x;cin>>x;
rep(j,1,27) cnt[i][j]=cnt[i-1][j];
cnt[i][x]++;
}
int ans=0;
rep(i,1,27) ans=max(ans,cnt[n][i]);
rep(i,1,n+1){
rep(j,i+1,n+1){
int lenlr=-1,lenmd=-1;
rep(k,1,27){
int l=cnt[i][k];
int r=cnt[n][k]-cnt[j-1][k];
lenlr=max(lenlr,min(l,r));
}
rep(k,1,27){
int m=cnt[j-1][k]-cnt[i][k];
lenmd=max(lenmd,m);
}
ans=max(ans,lenlr*2+lenmd);
}
}
cout<<ans<<endl;
}
int main(){
IOS;
int t;cin>>t;
while(t--){
solve();
}
return 0;
}
参考博客:1335hard版本 可以使用一个
数组来记录每个数字的下标,然后枚举位于两侧的数字的种类。首先考虑如果回文串的数字只有一个种类,则
=
(
,
[
].
()),如果该数字出现的次数少于
2次,则表明该数字不能放在两侧,可以跳过。否则就对左右两侧各拥有多少个数字进行枚举,在中间的区间中找到出现次数最多的数字,设
为左右两侧出现的数字个数,
为中间区间的最多次数,则代价为
∗2+
。我们可以发现,枚举的中间区间一定是连续的,以
[1,1,1,2,1,2,1,1]为例,见下图
我们发现,当两侧数字从小往大递增时,区间长度减少,而递减时,区间长度增加,所以我们可以在枚举两侧数字出现的次数时,记录下状态的改变。因为状态改变时,中间区间的长度是固定的,我们只需要处理左右区间即可。假设当前数字出现的次数为
,则两侧最多有
/2个数字。如果
是偶数,则中位数有两个:
/2和
/2−1。如果
是奇数,那么中位数只有一个:
/2,但要保证两侧数字出现的次数相同,所以我们只能取
/2−1和
/2+1。我们可以发现,如果取
/2和
−
/2的话,对于奇偶来说是相同的,所以不用对奇偶进行判断。 核心代码
int uu=u/2;
int cnt[300]={0},mx=-1;
rep(j,v[i][uu-1]+1,v[i][u-uu]){
cnt[a[j]]++;
}
然后我们对两侧出现的数字从大到小进行枚举,假设
为两侧出现的数字,当
减小时,两边增加的区间分别为
[
−1,
]和
[
−
−1,
−
],我们可以直接统计次数即可。
#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long ll;
const int N=2020;
const int M=1e6+10;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
/*注意边界
清空每个case的影响
注意数据范围
注意证明*/
int a[N];
vector<int> v[300];
void solve(){
int n;cin>>n;
rep(i,0,300) v[i].clear();
rep(i,1,n+1){
cin>>a[i];
v[a[i]].PB(i);
}
int ans=0;
rep(i,1,257){
int u=v[i].size();
ans=max(ans,u);
if(u<2) continue;
int uu=u/2;
int cnt[300]={0},mx=-1;
rep(j,v[i][uu-1]+1,v[i][u-uu]){
cnt[a[j]]++;
}
rep(j,1,257) mx=max(mx,cnt[j]);
ans=max(ans,uu*2+mx);
rrep(j,uu-1,1){
rep(k,v[i][j-1]+1,v[i][j]) cnt[a[k]]++;
rep(k,v[i][u-j-1]+1,v[i][u-j]) cnt[a[k]]++;
rrep(k,1,257) mx=max(mx,cnt[k]);
ans=max(ans,(int)j*2+mx);
}
}
cout<<ans<<endl;
}
int main(){
IOS;
int t;cin>>t;
while(t--){
solve();
}
return 0;
}