水题笔记_ 前缀和合集 [前缀和]

看上去不起眼的算法如果应用灵活可以解决很多问题

懵逼的 题目

初级入门: 传送至 CrossFire(w)

中级进阶: 传送至BZOJ

↑难度纯瞎排的

扯淡的 题解

纯粹是为了陪(给)学长打(垫)比(排)赛(名)才打开的CF, 然后就抱着比赛前总得刷几道的觉悟看了看873B, 题目大意: 给一个长度为n的01串, 求最长 [01个数相等的子串] 长度
看看数据范围我以为是 [前缀和 × 二分查找] 即设0-1, 求序列前缀和, 二分查找前面有没有出现过这个前缀和的值的相反数, 说明这两个位置之间的子串是合法的, 取最大值即可, 后来学长说并不用二分, 我也发现woc 这™怎么二分,于是就空间换时间开数组记录每个前缀和出现的最早位置然后乱搞就好了
然后学长就推荐了中位数那道题, 大概和上个题思路相似, 不过不能只记录一个前缀和是否出现, 而应该记录一个前缀和出现过几次, 然后继续乱搞就好了
后来学长又说如果没有b, 或者b有多个应该怎么处理…没想出来…

沙茶的 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//873B

#include <iostream>
#include <cstdio>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN (100000)
int n;
char c[MAXN + 5];
int a[MAXN + 5];
int left[(MAXN << 1) + 5];
int fr[MAXN + 5];
int ans = 0;
void init();
int main()
{
scanf("%d", &n);
scanf("%s", c);
init();
printf("%d", ans);
return 0;
}
void init()
{
fr[0] = MAXN;
left[MAXN] = 0;
for (int i = 0; i < n;)
{
bool ok = false;
if (c[i] == '0')
{
a[i + 1] = -1;
ok = true;
}
else if (c[i] == '1')
{
a[i + 1] = 1;
ok = true;
}
if (ok)
{
fr[i + 1] = fr[i] + a[i + 1];
if (!left[fr[i + 1]] && fr[i + 1] != MAXN)
{
left[fr[i + 1]] = i + 1;
}
else
{
ans = std::max(ans, i + 1 - left[fr[i + 1]]);
}
i++;
}
}
}

/*
18
011010101110111101
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//BZOJ1303

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100000)
int n;
int a[MAXN + 5];
int c[MAXN + 5];
int b;
int ans;
int fr[MAXN + 5];
int left[(MAXN << 1) + 5];
void init();
int main()
{
init();
printf("%d", ans);
return 0;
}
void init()
{
scanf("%d%d", &n, &b);
if (b > n)
{
puts("0");
exit(0);
}
fr[0] = MAXN;
int ok = false;
left[MAXN] = 1;
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
if (a[i] > b)
{
c[i] = 1;
}
else if (a[i] < b)
{
c[i] = -1;
}
else if (a[i] == b)
{
c[i] = 0;
ok = true;
}
fr[i] = fr[i - 1] + c[i];
if (!ok)
{
left[fr[i]]++;
}
else
{
ans += left[fr[i]];
}
}
}
/*
7 4
5 7 2 4 3 1 6
*/

By 停课一时爽的 Cansult