题意抽象:找一个连续的子串, 使得子串中‘0’和‘1’的个数能抵消
做法:
$\quad$$\quad$(1) 前缀和a[i]统计前i个字符中有多少个‘1’, 前缀和b[i]统计前i个字符中有多少个‘0’
$\quad$$\quad$(2) 记该最大连续子串开始地方为 $i$, 结束地方为 $j$, 则有
$\quad$$\quad$$\quad$$\quad$$a[j] - a[i - 1] == b[j] - b[i - 1]$
$\quad$$\quad$$\quad$$\quad$$变形为 a[j] - b[j] == a[i - 1] - b[i - 1]$
$\quad$$\quad$(3) 从前往后统计, 记 $c[i]$ 为 $a[i] - b[i]$ 的差值, 用哈希表找到在 $i$之前的最小$a[j]$即可
小声bb, 这题放周赛都能当T2了, 却打了Easy的tag
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], b[N];
int c[N];
int n;
unordered_map<int, int> st;
int main()
{
string x;
cin >> x;
n = x.size();
for(int i = 1; i <= n; i ++ ){
a[i] = a[i - 1], b[i] = b[i - 1];
if(x[i - 1] == '1') a[i] ++ ;
else b[i] ++ ;
}
int res = 0;
st[0] = 0; //初始化哈希表头, 将从0开始, 到0结束的子串记为0
for(int i = 1; i <= n; i ++ ){
c[i] = a[i] - b[i];
if(st.count(c[i]) != 0) res = max(res, a[i] - a[st[c[i]]]);
else st[c[i]] = i;
}
printf("%d", res * 2);
return 0;
}
st[0] = 0; //初始化哈希表头, 将从0开始, 到0结束的子串记为0
这一步真的好容易被忽略
前缀和 和当前索引 刚好一半一半。
移项变形,然后用哈希记录与查找是真的巧妙。我就傻傻的用前缀和还有滑动窗口,然后TLE了
翻了一圈题解终于懂了
hh这题不是上周ccpc的签到题吗
你们都是卷皇
%%%1点还在卷的光头哥
正常操作正常操作