CF-634E1/2 Three Blocks Palindrome (easy/hard version) 题解

题目大意

定义一个三段串为一种序列，每一个序列为x个a，y个b，x个a组成，x，y大于等于0.

可以是全为a这样一种数字，或者是2个x个a夹着y个b，也就是一种对称的数字夹着另一种数字。

求这种序列的最长长度。

（说实话，我写的时候可能题目都没看懂。。

导致往最长回文子序列去想了。。。以后还是要注意看题。

有一次div2的A，光看懂题就看了半个多小时。

解题思路

用vector数组去记录每一个数字的位置。

分两种情况去考虑：

第一种：全为一种数字

很简单，只用判断哪一种数字的v.size()最大即可。

第二种：一种数字夹着另一种数字

设每一种数字的数量为cnt=v.size()。

那么左右两边最大长度为c=cnt/2。

如果c<=1，那么就不用考虑，直接continue。

cnt分为奇数和偶数。

当cnt为奇数的时候，左区间为0 ~ c-1，右区间为c+1 ~ cnt-1。

当cnt为偶数的时候，左区间为0 ~ c-1，右区间为c ~ cnt-1。

但实际上，我们可以将他们都表示为左区间为0 ~ c-1，右区间为cnt-c ~ cnt-1。

论证如下：(其实看规律也看得出)

当cnt为奇数的时候，cnt-c=2*c+1-c=c+1。

当cnt为偶数的时候，cnt-c=2*c-c=c。

第一个状态就是从区间[v.[c-1]+1~v.[cnt-c]-1]中找出出现最多次数的数字的个数为M。

用n数组表示大小为i的数字的个数。

那么答案为M+2*c。

之后的状态便是枚举长度，从j = c-1开始，枚举到1。

不断更新答案，答案为M+2*j。

完整代码

主要还是看代码吧。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;

const int N = 2e5+5;
int num[N];
vector<int>v[220];

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		for (int i = 1; i <= 200; i++)	v[i].clear();
		for (int i = 1; i <= n; i++) {
			cin >> num[i];
			v[num[i]].push_back(i);
		}
		int ans = -1e9;
		for (int i = 1; i <= 200; i++) {
			int cnt = v[i].size(), c;
			ans = max(ans, cnt);
			c = cnt / 2;
			if (cnt <= 1)	continue;
			int n[220] = { 0 }, M = -1e9;
			for (int j = v[i][c - 1] + 1; j < v[i][cnt - c]; j++) {
				n[num[j]]++;
			}
			for (int j = 1; j <= 200; j++)	M = max(M, n[j]);
			ans = max(ans, M + 2 * c);
			for (int j = c - 1; j > 0; j--) {
				for (int g = v[i][j - 1] + 1; g < v[i][j]; g++)	n[num[g]]++;
				for (int g = v[i][cnt - j - 1] + 1; g < v[i][cnt - j]; g++)	n[num[g]]++;
				for (int g = 1; g <= 200; g++)	M = max(M, n[g]);
				ans = max(ans, M + 2 * j);
			}
		}
		cout << ans << endl;
	}
}