题解：P14412 [JOISC 2015] AAQQZ
george0929
·
·
题解
感觉吃了一坨。
题意
给定一个长为 n 的数组，选择一个区间 [l,r] 进行排序，最大化排序后最长回文子串的长度。
### 题解
首先令答案对原串最长回文子串和众数个数取 $\max$，这两种情况是平凡的。
之后有两种情况：
- 回文中心在排序区间外。
- 回文中心在排序区间的开头（或结尾）极长相等连续段内（例如 $443322\color{red}1\color{blue}1\color{red}1223344$）
对于第一种情况，设排序区间在右，枚举回文中心，向两侧扩展后枚举排序区间，当然你可以平衡树维护哈希，但是有简单做法：对左侧最长不升子序列开桶，由于排序后区间是上升的，所以可以维护值域指针 $ptr$ 表示匹配到了哪个值，最后判断能否向外扩展即可。
对于第二种情况，枚举回文中心不好做，考虑枚举排序区间起点 $l$，对以 $l-1$ 结尾的最长不升子序列开桶，此时往后枚举 $r$，当遇到 $<a_{l-1}$ 的数时开始记贡献，匹配方式与第一种情况相同，唯一区别是不匹配最小值。
$O(n^2)$。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,V,ans;
int a[3005];
int cnt[3005];
int lcp[3005][3005];
int cntl[3005],cntr[3005];
void solve1(int l,int r){
if(l<1||r>n) return;
memset(cntl,0,sizeof(cntl));
memset(cntr,0,sizeof(cntr));
cntl[a[l]]++;
int Lpos=l-1;
for(int i=l-1;i>=1;i--){
if(a[i]>=a[i+1]){
cntl[a[i]]++;
Lpos=i;
}else break;
}
int ptr=0,len=0,mx=0;
for(int R=r;R<=n;R++){
cntr[a[R]]++;
mx=max(mx,a[R]);
if(a[R]<=ptr){
while(ptr>=a[R]){
len-=cntl[ptr];
ptr--;
}
}
while(ptr<=V&&cntl[ptr+1]==cntr[ptr+1]) len+=cntl[ptr+1],ptr++;
if(len==R-r+1&&len==l-Lpos+1) ans=max(ans,(R-r+1)*2+r-l-1+2*lcp[l-(R-r+1)][R+1]);
else ans=max(ans,r-l-1+2*len+2*min(cntl[ptr+1],cntr[ptr+1]));
}
}
void solve2(int l){
memset(cntl,0,sizeof(cntl));
memset(cntr,0,sizeof(cntr));
int mn=a[l],Lpos=l-1;
cntl[a[l-1]]++;
for(int i=l-2;i>=1;i--){
if(a[i]>=a[i+1]){
Lpos=i;
cntl[a[i]]++;
}else break;
}
cntr[a[l]]++;
int ptr=0;
int cntmn=0,len=0,mx=0;
if(a[l]<a[l-1]){
mn=a[l];
cntmn++;
}
for(int r=l+1;r<=n;r++){
mx=max(mx,a[r]);
cntr[a[r]]++;
if(a[r]<=ptr&&a[r]!=mn){
while(ptr>=a[r]){
if(ptr!=mn){
len-=cntl[ptr];
}
ptr--;
}
}
if(a[r]<mn&&mn<a[l-1]){
break;
}
mn=min(mn,a[r]);
if(mn>=a[l-1]) continue;
if(a[r]==mn) cntmn++;
while(ptr<=V&&(cntl[ptr+1]==cntr[ptr+1]||ptr+1==mn)){
if(ptr+1!=mn) len+=cntl[ptr+1];
ptr++;
}
if(len==l-1-Lpos+1&&r-l+1-cntmn==l-1-Lpos+1) ans=max(ans,r-Lpos+1+2*lcp[Lpos-1][r+1]);
else{
ans=max(ans,2*len+cntmn+2*min(cntl[ptr+1],cntr[ptr+1]));
}
}
}
void work(){
for(int i=1;i<=n;i++){
for(int j=n;j>=1;j--){
if(a[i]==a[j]) lcp[i][j]=1+lcp[i-1][j+1];
else lcp[i][j]=0;
}
}
for(int i=1;i<=n;i++){
ans=max(ans,lcp[i][i]*2-1);
ans=max(ans,lcp[i][i+1]*2);
}
if(ans==n){
cout<<ans<<"\n";
exit(0);
}
for(int i=1;i<=n;i++){
int l=lcp[i][i];
solve1(i-l,i+l);
l=lcp[i][i+1];
solve1(i-l,i+1+l);
}
for(int l=2;l<=n;l++){
solve2(l);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>V;
for(int i=1;i<=n;i++){
cin>>a[i];
cnt[a[i]]++;
}
for(int i=1;i<=V;i++) ans=max(ans,cnt[i]);
work();
reverse(a+1,a+1+n);
for(int i=1;i<=n;i++) a[i]=V-a[i]+1;
work();
cout<<ans<<"\n";
}
```