SDUT 3308 最长01串

本文主要是介绍SDUT 3308 最长01串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最长01串

Time Limit: 2666 ms; Memory Limit: 65536 KiB

Problem Description

给定一个0-1串，请找到一个尽可能长的连续子串，其中包含的0与1的个数相等。
组数很多，注意常数优化。。。

Input

 一个字符串，只包含01，长度不超过1000000

Output

 一行一个整数，最长的0与1的个数相等的子串的长度。

Sample Input

1011
1111
1010

Sample Output

2
0
4

题目链接：http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/3308.html

题目分析：记录0和1个数差出现的位置

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const CON = 1000000;
char s[1000005];
int mp[2000005];int main() {while (scanf("%s", s) != EOF) {int diff = 0, ans = 0;memset(mp, -1, sizeof(mp));for (int i = 0; i < strlen(s); i++) {diff += (s[i] == '1');if (diff == 0) {ans = max(ans, i + 1);} else {if (mp[diff + CON] == -1) {mp[diff + CON] = i;} else {ans = max(ans, i - mp[diff + CON]);}}}printf("%d\n", ans);}
}

 

这篇关于SDUT 3308 最长01串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---