codeforces #334 div 2 C. Alternative Thinking

2015-12-02 · 1 min read

题意：给定一个01串。要进行一次变换：选一段连续的非空的字串，将这段串的0和1反转（0变成1,1变成0）然后问能得到的最长的0,1交替的序列的长度是多少（不一定连续）

比赛的时候想出来两种会将答案增加的可能情况。一种是10000001 中间有大于等于3个的连续字符，这样可以把中间反转一下，答案会+2 另外一种是 1001001 这样。。有至少两段的连续两个以上的相同字符被另一个字符隔开的情况。只要将1001001变成1010101。答案还是会+2。。。然后发现这两种情况实际上可以统一起来。即：有至少两段的连续相同字符。注意000 也算有两段。如果有两段或者以上，那么答案+2.

/* ***********************************************
Author :111qqz
Created Time :2015年12月02日 星期三 00时36分47秒
File Name :code/cf/#334/C.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;

1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E5+7;
7char a[N];
8int n;

 1char tow(char ch)
 2{
 3    if (ch=='0') return '1';
 4    if (ch=='1') return '0';
 5}
 6int main()
 7{
 8	#ifndef  ONLINE_JUDGE 
 9	freopen("code/in.txt","r",stdin);
10  #endif

1	scanf("%d",&n);
2	scanf("%s",a);
3	int cnt =  0;
4	for ( int i = 0  ; i < n-1 ; i++) 
5	    if (a[i]==a[i+1])
6		cnt++;

    if (cnt>=2) cnt = 2;

 1    char tar = a[0];
 2	tar = tow(tar);
 3	int ans = 1;
 4	for ( int i = 1 ; i < n ; i++ )
 5	{
 6//	    printf("%d %c\n",i,tar);
 7	    if (a[i]==tar)
 8	    {
 9		ans++;
10		tar = tow(tar);
11	    }
12	}

	printf("%d\n",ans+cnt);

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}