CodeForces 1025C Plasticine zebra

题目大意

题目链接
给定一个由w和b组成的字符串，可以操作任意次，每次操作（0次或多次）可以将字符串分割成左右两个子串，左、右侧子串均前后颠倒。
问最终字符串中最多可以有多少个w和b交错（w和b无所谓顺序）。

题解

构造，比较好想。
总述：

1. 当最左端字符与最右端字符不同时， max(左侧最长交错子串+右侧最长交错子串, 原最长交错子串)
2. 当最左端字符与最右端字符相同时，原最长交错子串

详解：
首先推断出试出最多操作一次，操作多了也没用。（这个我是通过试着造样例发现的这个特点）
当第一个字符和最后一个字符一样的时候，无论从哪里分割都没什么用，因为左右子串颠倒完，分割处的两个字符还是同为w或b，即无效操作。此时，我们就统计整个字符串中最长即可。
当第一个字符和最后一个字符不一样的时候 ，进行分割、颠倒属于有效操作。我们应当注意到，在操作完成之后，有可能更新最大长度的一定是包含分割处的一个交错子串。这个交错子串在分割处的左半部分是原字符串的最左端的若干字符，交错子串在分割处的右半部分是原字符串的最右端的若干字符串。因此我们要先求出，①原字符串中以第一个字符开始的交错子串长度，②原字符串中以最后一个字符结尾的交错子串长度。枚举分割处，分割处左侧能贡献的交错子串长度为min(分割处左侧子串的长度, ①)，分割处右侧能贡献的交错子串长度为min(分割处右侧子串的长度, ②)，二者之和与原字符串（即未进行操作）中的最长交错子串取个最大值即为答案。
注意：一个字符时最长交错子串长度为1（坑了我一发）

代码

#include<bits/stdc++.h>
using namespace std;
string str;
int a[100010];
int main()
{
	cin>>str;
	int n = str.length();
	
	for(int i = 0;i < n;i ++) a[i+1] = (str[i] == 'b'?1:0);
	
	int len  = 1, maxlen = 1;
	for(int i = 1;i < n;i ++) {
		if(a[i] ^ a[i+1]) len ++;
		else maxlen = max(maxlen, len), len = 1;
	}
	maxlen = max(maxlen, len);
	
	if(a[1] == a[n]) {
		cout << maxlen << endl; 
	} else {
		int ans = maxlen, maxlenleft = 0, maxlenright = 0;
		
		len = 1;
		for(int i = 1;i < n;i ++) 
			if(a[i] ^ a[i+1]) len ++;
			else break;
		maxlenleft = max(maxlenleft, len);
		
		len = 1;
		for(int i = n-1;i > 0;i --) 
			if(a[i] ^ a[i+1]) len ++;
			else break;
		maxlenright = max(maxlenright, len);
		
//		cout << maxlenleft << ' ' << maxlenright << endl;
		
		for(int i = 1;i < n;i ++) 
			ans = max(ans, min(i, maxlenleft) + min(n-i, maxlenright));
		cout << ans <<endl;
	}
	return 0;
}