[JOI 2013 Final]彩灯

[JOI 2013 Final]彩灯

题意

给出一个 \(01\) 序列，可以把一段区间反转。

求反转后序列最长的交替子段，即 \(010101 \ldots\) 或 \(101010 \ldots\)。

思路

首先发现一个性质，反转的一定是一段交替子段。

因为反转不交替子段对答案的贡献不优。

枚举反转哪一段交替子段，统计左右两边的子段和它连起来的长度，取最大值即可。

具体实现时维护从某个数向前和向后的连续 \(0101\) 长度，连续 \(1010\) 长度。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int n, a[N], ans;
int p0[N], p1[N], s0[N], s1[N];

int main() {
	freopen("deng.in", "r", stdin);
	freopen("deng.out", "w", stdout);
	
	cin >> n;
	for (int i = 1; i <= n; i ++)
		cin >> a[i];
	
	for (int i = 1; i <= n; i ++) {
		if (a[i] != a[i - 1]) {
			p0[i] = p0[i - 1] + 1;
			p1[i] = p1[i - 1] + 1;
		}	else {
			p0[i] = 1;
			p1[i] = 1;
		}
	}
	for (int i = 1; i <= n; i ++) {
		if (a[i] == 1) p0[i] = 0;
		else p1[i] = 0;
	}
	
	for (int i = n; i >= 1; i --) {
		if (a[i] != a[i + 1]) {
			s0[i] = s0[i + 1] + 1;
			s1[i] = s1[i + 1] + 1;
		} else {
 			s0[i] = 1;
			s1[i] = 1;	
		}
	}
	for (int i = 1; i <= n; i ++) {
		if (a[i] == 1) s0[i] = 0;
		else s1[i] = 0;
	}
	
	for (int i = 1; i <= n; i ++) {
		if (i + s0[i + 1] <= n && a[i + s0[i + 1]] == 0) 
			ans = max(ans, p0[i] + s0[i + 1] + s0[i + s0[i + 1] + 1]);
		if (i + s0[i + 1] <= n && a[i + s0[i + 1]] == 1)
			ans = max(ans, p0[i] + s0[i + 1] + s1[i + s0[i + 1] + 1]);
		if (i + s1[i + 1] <= n && a[i + s1[i + 1]] == 0)
			ans = max(ans, p1[i] + s1[i + 1] + s0[i + s1[i + 1] + 1]);
		if (i + s1[i + 1] <= n && a[i + s1[i + 1]] == 1)
			ans = max(ans, p1[i] + s1[i + 1] + s1[i + s1[i + 1] + 1]);
		ans = max(ans, p0[i] + s1[i + 1]);
		ans = max(ans, p1[i] + s0[i + 1]);
	}
	
	cout << ans << "\n";
	return 0;
}