题解：P14412 [JOISC 2015] AAQQZ

感觉吃了一坨。

题意

给定一个长为

n

的数组，选择一个区间

[l,r]

进行排序，最大化排序后最长回文子串的长度。

1\leq n\leq 3000

。

题解

首先令答案对原串最长回文子串和众数个数取

\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";
}

题解：P14412 [JOISC 2015] AAQQZ

文章操作

题意

题解

相关推荐

评论

题解：P14412 [JOISC 2015] AAQQZ