18075 0还有1

该题有题解

时间限制:1000MS 内存限制:65535K
提交次数:18 通过次数:0

题型: 编程题语言: 不限定

Description

     0和1在程序猿眼中是重要的东西，Alice给了Bob一个长度为n的只含有数字0和1的串。然后
Alice希望Bob求得 此串的 子序列 中 的最长的 010101... 或 10101... 串的长度是多少 ？
      010101... 或 10101... 串为（ 如 0,1,01,10,101,010,1010,0101,10101,等等 ）
     hl感觉这个题目对于Bob来说有点简单，于是加了一个操作：
Bob可以把这个这个串截出一部分连续的前缀（长度>=0），一部分连续的后缀（长度>=0），然后将它们
水平翻转后，分别连回原串的“尾部”，“首部”。

操作前：     ( a[0] ... a[i] ) a[i+1] ... a[j-1] ( a[j] ... a[n-1] ) 
操作后：     ( a[n-1] ... a[j] ) a[i+1] ... a[j-1] ( a[i] ... a[0] ) 
注意： （ 0 <= i < j < n ）

然后再问， 此串的 子序列 中 的最长的01...或10... 串最长长度是多少？
如果这个操作没有得到更好的答案的话，Bob可以不进行。

输入格式

一个正整数 n ( 2 <= n <= 1000000 ) , 下一行是一个长度为n只含0还有1的数字串。

输出格式

Bob求得的最长的 01...或101...串的长度。

输入样例

输出样例

4
6

提示

第一个样例不需要进行操作
第二个样例：（10）01（10） ， 把括号中的串翻转后交换得到 （01）01（01） 。

tips:分清楚子串和子序列的区别

来源

作者

201330330210

这题真是无敌思维题。

考虑3种情况。

1、只有00，现在这是有一个0是用不上的，但是如果str[1] == '1' || str[n] == '1'，就可以从00中间断开。接上去，ans+1

例子：100.

那为什么不两边断开，接去一个1那里呢，001010，但是此时候的1是饱和状态，不存在浪费。101001，可以为这个0增加1.

2、只有11.一样

3、存在00 && 11.无条件+2、因为总可以使得一pair01饱和。现在是浪费了两个，1个1,1个0.他们对接即可。

00010111 --- 11010100

其实就是把中间的翻转，然后从右往左看。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
#define MY "H:/CodeBlocks/project/CompareTwoFile/DataMy.txt", "w", stdout
#define ANS "H:/CodeBlocks/project/CompareTwoFile/DataAns.txt", "w", stdout


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>

const int maxn = 1000000 + 20;
int n;
char str[maxn];
void work() {
    scanf("%s", str + 1);
    int now = 0;
    int ans = 1;
    for (int i = 2; i <= n; ++i) {
        if (str[i] == str[i - 1]) {
            now |= (1 << (str[i] - '0'));
        } else ans++;
    }
//    cout << ans << endl;
    if (now == 3) ans += 2;
    else if (now == 2 && (str[n] == '0' || str[1] == '0')) ans++;
    else if (now == 1 && (str[n] == '1' || str[1] == '1')) ans++;
    cout << ans << endl;
}
int main() {
#ifdef local
    freopen("data.txt","r",stdin);
    freopen(MY);
#endif
    while (scanf("%d", &n) != EOF )
        work();
    return 0;
}

View Code