首页 > 代码库 > Codeforces 604C Alternative Thinking
Codeforces 604C Alternative Thinking
题目链接：http://codeforces.com/problemset/problem/604/C
题意：给一个01串，你可以指定起点，终点，翻转此区间一次。要求翻转后，0，1交替出现的子串长度最长，输出长度。
思路：头开始想想，感觉很麻烦，其实多写几个例子，想一想，就那么三种情况。
想要使翻转后，符合题意的子串长度增加。要么就是有连续相同的元素（11：增加1，111：增加2），要么就是可以交换的类型（0011：增加2）。
连续的元素大于3也只能增加2。
×××要注意的一点是：11000011×××（当有两个相同元素时，翻转其中一个可以增加 1，当有两对的时候。。。）
#include <iostream>#include <stdio.h>#include <cstring>#include <queue>#include <set>#include <cmath>#include <time.h>#include <cstdlib>#include <algorithm>#define lson (i<<1)#define rson (lson|1)using namespace std;typedef long long LL;const int N = 100007;const int INF = 0x7fffffff;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, flag, flag2, flag3, flagex; char str[N]; while (cin >> n) { cin >> str; int cnt = 0; flag = str[0] - ‘0‘; flag2 = 0, flag3 = 0, flagex = 0; for (int i = 0; i < n; i++) { if (str[i] - ‘0‘ == flag) { cnt++; flag = !flag; } if (i > 1 && str[i] == str[i-1] && str[i-1] == str[i-2]) flag3 = 1; if (i > 0 && str[i] == str[i-1]) flag2++; if (i > 2 && str[i] == str[i-1] && str[i-2] == str[i-3] && str[i-1] != str[i-2]) flagex = 1; } if (flag3) cnt += 2; else if (flagex) cnt += 2; else if (flag2) { if (flag2 > 1) cnt += 2; else cnt++; } cout << cnt << endl; } return 0;}
Codeforces 604C Alternative Thinking
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。