概念
前缀和为一种预处理,可理解为数列前 \(n\)
项的和。可降低查询某些信息的所需时间。
1 2 3 4 5 6
| int sum[MAXN]; sum[0] = a[0]; for (int i = 1; i < n; i++) { sum[i] = sum[i - 1] + a[i]; }
|
STL 中的前缀和
C++ 标准库中提供了 std::partial_sum
前缀和函数,定义于头文件 <numeric>
中
用法为
partial_sum(InputIt first, InputIt last, OutputIt d_first)
例题
洛谷 P3131
[USACO16JAN]Subsequences Summing to Sevens S
本题直接处理前缀和存储余数,在前缀和中取头尾两余数相等的数坐标相减即可。
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
| #include <iostream> #include <cstring>
const int MAXN = 50000;
int main() { int n, maxn = 0; static int a[MAXN + 1]; std::cin >> n; for (int i = 1; i <= n; i++) { std::cin >> a[i]; }
static int sum[MAXN + 1]; sum[1] = a[1] % 7; for (int i = 2; i <= n; i++) { sum[i] = (sum[i - 1] + a[i]) % 7; } static int first[7], last[7]; memset(first, 0, sizeof(first)); memset(last, 0, sizeof(last)); for (int i = 0; i < 7; i++) for (int j = 1; j <= n; j++) if (sum[j] == i) { first[i] = j; break; } for (int i = 0; i < 7; i++) for (int j = n; j >= 1; j--) if (sum[j] == i) { last[i] = j; break; } maxn = last[0]; for (int i = 0; i < 7; i++) { if (last[i] - first[i] > maxn) { maxn = last[i] - first[i]; } }
std::cout << maxn << std::endl; return 0; }
|
二维/多维前缀和
RT
例题
洛谷 P1387
最大正方形
本题可通过前缀和处理矩形,利用 sum
数组存储可组成正方形的最大值。
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
| #include <iostream> #include <cstring>
const int MAXN = 100;
int main() { int n, m; static int squ[MAXN + 1][MAXN + 1];
std::cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { std::cin >> squ[i][j]; } }
int ans = 0; static int sum[MAXN + 1][MAXN + 1]; memset(sum, 0, sizeof(sum)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (squ[i][j] == 1) { sum[i][j] = std::min(std::min(sum[i - 1][j] , sum[i][j - 1]), sum[i - 1][j - 1]) + 1; if (sum[i][j] > ans) { ans = sum[i][j]; } } } }
std::cout << ans << std::endl; return 0; }
|