算法复习之前缀和【备战蓝桥杯】
一维前缀和
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]
二维前缀和
S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
练习题
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e6 + 10;
int n;
int s[N];
char str[N];
int main()
{
int T;
scanf("%d", &T);
for (int x = 1; x <= T; x ++ )
{
scanf("%d", &n);
scanf("%s", str + 1);
memset(s, 0, sizeof s);
for (int i = 1; i <= n; i ++ )
s[i] += s[i - 1] + str[i] - '0';
int k = (n - 1) / 2 + 1;
int sum = 0;
for (int i = k; i <= n; i ++ )
sum = max(sum, s[i] - s[i - k]);
printf("Case #%d: %dn", x, sum);
}
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int s[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &s[i]);
s[i] += s[i - 1];
}
while (m -- )
{
int l, r;
scanf("%d%d", &l, &r);
printf("%dn", s[r] - s[l - 1]);
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n, m, q;
const int N = 1010;
int s[N][N];
int main()
{
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
scanf("%d", &s[i][j]);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
while(q -- )
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
printf("%dn", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
}
return 0;
}
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, k;
LL s[N], cnt[N];
int main()
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &s[i]);
s[i] += s[i - 1];
}
// for (int i = 1; i <= n; i ++ ) printf("%d ", s[i]);
LL res = 0;
cnt[0] ++;
for (int i = 1; i <= n; i ++ )
{
res += (LL)cnt[s[i] % k];
cnt[s[i] % k] ++;
}
printf("%lldn", res);
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 510;
int n, m, k;
int s[N][N];
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
scanf("%d", &s[i][j]);
s[i][j] += s[i - 1][j];
}
LL res = 0;
// 枚举上下边界
for (int i = 1; i <= n; i ++ )
for (int j = i; j <= n; j ++ )
// 双指针降低一层循环来枚举左右边界
for (int l = 1, r = 1, sum = 0; r <= m; r ++ )
{
sum += s[j][r] - s[i - 1][r];
while (sum > k)
{
sum -= s[j][l] - s[i - 1][l];
l ++;
}
res += r - l + 1;
}
printf("%lldn", res);
return 0;
}
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
二维码