51Nod－1393－0和1相等串

ACM模版

描述

题解

前缀和+Hash记录，复杂度为O(N)。这里需要强调的是要考虑到01这种最长的情况是打头开始的串，所以需要对dif[MAXN] = 0;初始化。

代码

#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int MAXN = 1e6 + 10; const int INF = 0x3f3f3f3f; char S[MAXN]; int SUM[MAXN] = {0}; // 0化作-1 int dif[MAXN * 2]; int main(int argc, const char * argv[]) { memset(dif, 0x3f, sizeof(dif)); dif[MAXN] = 0; scanf("%s", S + 1); int len = (int)strlen(S + 1); int ans = 0; for (int i = 1; i <= len; i++) { if (S[i] == '0') { SUM[i] = SUM[i - 1] - 1; } else { SUM[i] = SUM[i - 1] + 1; } if (dif[SUM[i] + MAXN] == INF) // 防止下标越界 { dif[SUM[i] + MAXN] = i; } else { ans = max(ans, i - dif[SUM[i] + MAXN]); } } cout << ans << '\n'; return 0; }