Three Blocks Palindrome (easy version)[暴力-预处理]

给定一个数组，找出最长的子序列，满足

a,a,..a,b,b,..b,a,a,..a

前面的a和后面的a都要是x个，中间的b是y个。

其中,x>=0且y>=0.

\(\color{Red}{---------------------华丽分割线w(ﾟДﾟ)w------------------------}\)

看到这数据，就觉得暴力无疑。

\(三种情况\)

\(Ⅰ.当x=0,也就是只有中间部分，答案就是出现次数最多的那个数字。\)

\(Ⅱ.当y=0,也就是只有两边的部分，那就要枚举前半部分区间和后半部分区间，设区间为[1,L]和[R,n]\)

\(再枚举a的取值(1-26),答案是区间[1,L]a出现次数和[R,n]a出现次数的较小值\)。

\(Ⅲ.当x和y都不为0，怎么办?其实和2差不多，只不过现在因为y的存在,在区间[L,R]要计算最大的y,也就是出现次数最多的。\)

具体实现，需要维护几个数组降低复杂度，具体看代码。

暴力代码

\(但是上面的方法对于这题的hard版本n=2e5实在不够看，所以有了下面的方法。\)

\(\color{Orange}{---------------------O(∩_∩)O分割分割分割------------------------}\)

这种数据，枚举区间的办法是行不通了，只有\(a[i]<=200\&\&a[i]>=1\)这个范围还算友好

我们可以枚举数字作为a。

比如3出现了5次，可行的枚举就是左右各一次，左右各两次。

在这个基础上，要使空出来的区间最大(因为可能要放b),显然应该选最左边的几个和最右边的几个。

\(那我们开个vector装每个数字出现的位置，枚举就是了。\)

\(那空出来的区间呢?如何快速知道哪个数在区间次数最多作为b?\)

\(其实在枚举的过程中，空出来的区间总是连续减少的，所以可以动态维护1-200的出现次数\)

#include <bits/stdc++.h>

using namespace std;

const int maxn=2e5+9;

vector<int>vec[209];

int a[maxn],t,n,vis[201];

int main()

{

	cin>>t;

	while(t--)

	{

		for(int i=1;i<=200;i++)	vec[i].clear();

		cin>>n;

		int ans=0;

		for(int i=1;i<=n;i++)

		{

			cin>>a[i];

			vec[a[i]].push_back(i);

		}

		//处理x为0

		for(int i=1;i<=200;i++)

		{

			int tt=vec[i].size();

			ans=max(ans,tt);

		}

		//处理两头夹中间

		for(int i=1;i<=200;i++)

		{

			int k=vec[i].size(),temp=0;

			if(k<2)	continue;

			memset(vis,0,sizeof(vis));

			int l=vec[i][0]+1,r=vec[i][k-1]-1;

			for(int j=l;j<=r;j++)	vis[a[j]]++;//预处理拿1个的时候

			for(int j=1;j<=200;j++)	temp=max(temp,vis[a[j]]);

			ans=max(ans,2+temp);

			for(int j=2;j<=k/2;j++)//左边拿j,右边拿j

			{

				int l=vec[i][j-1]+1,r=vec[i][k-j]-1;

				for(int q=vec[i][j-2]+1;q<l;q++)	vis[a[q]]--;

				for(int q=r+1;q<=vec[i][k-j+1]-1;q++)	vis[a[q]]--;

				temp=0;

				for(int q=1;q<=200;q++)

					ans=max(ans,vis[q]+j*2);

			}

		}

		cout<<ans<<endl;

	}

}

巴特西

Three Blocks Palindrome (easy version)[暴力-预处理]

最新文章

热门文章