本文主要是介绍CodeForces 603A Alternative Thinking 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Kevin has just recevied his disappointing results on the USA Identification of Cows Olympiad (USAICO) in the form of a binary string of length n. Each character of Kevin's string represents Kevin's score on one of the n questions of the olympiad—'1' for a correctly identified cow and '0' otherwise.
However, all is not lost. Kevin is a big proponent of alternative thinking and believes that his score, instead of being the sum of his points, should be the length of the longest alternating subsequence of his string. Here, we define an alternating subsequence of a string as anot-necessarily contiguous subsequence where no two consecutive elements are equal. For example, {0, 1, 0, 1}, {1, 0, 1}, and{1, 0, 1, 0} are alternating sequences, while {1, 0, 0} and {0, 1, 0, 1, 1} are not.
Kevin, being the sneaky little puffball that he is, is willing to hack into the USAICO databases to improve his score. In order to be subtle, he decides that he will flip exactly one substring—that is, take a contiguous non-empty substring of his score and change all '0's in that substring to '1's and vice versa. After such an operation, Kevin wants to know the length of the longest possible alternating subsequence that his string could have.
The first line contains the number of questions on the olympiad n (1 ≤ n ≤ 100 000).
The following line contains a binary string of length n representing Kevin's results on the USAICO.
Output a single integer, the length of the longest possible alternating subsequence that Kevin can create in his string after flipping a single substring.
8 10000011
5
2 01
2
In the first sample, Kevin can flip the bolded substring '10000011' and turn his string into '10011011', which has an alternating subsequence of length 5: '10011011'.
In the second sample, Kevin can flip the entire string and still have the same score.
【分析】：
采用找规律的方法。
首先，如何求原序列的最长substring长度。方法是求0,1块的块数，例如001110011，最长序列长度就是4。
现在考虑：
1）：如果其中含有一个“11”或者“00”，其答案为原来的最长序列长度加上1，例如10010 可以变成 10101，即把右边的数字其之后的所有数都取反即可。（如上图颜色和下划线部分区别所示，改变部分用下划线和加粗区别表示）不过，注意特殊处理含有三个‘0’或‘1’连续的情况，这种情况的答案为原来的最长序列长度加上2。（方案就是将非两边的数取个反）
2）：如果含有两个或更多的“11”或者“00”，其答案为原来的最长序列长度加上2。例如1001011 可以变成 1010101，即只需要把其中两个的最靠近对方的那个数与两数中间所夹的所有数都取反即可。（如上图颜色和下划线部分区别所示，改变部分用下划线和加粗区别表示）。
【代码】：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int N,number,ans=0,last=-1,cnt=0,upper_two=0;
bool exist_three_or_upper=false;
int main()
{
#ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
#endif scanf("%d",&N);for(int i=1;i<=N;i++){scanf("%1d",&number);if(number!=last){ans++;last=number;if(cnt>=2) upper_two++; if(cnt>=3) exist_three_or_upper=true;cnt=1;}else cnt++;}if(cnt>=2) upper_two++; if(cnt>=3) exist_three_or_upper=true;if(upper_two>=2) ans+=2;else if(upper_two==1 && !exist_three_or_upper) ans++;else if(upper_two==1 && exist_three_or_upper) ans+=2;printf("%d\n",ans);return 0;
}这篇关于CodeForces 603A Alternative Thinking 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
