526互联

4 前缀和与差分 参考代码

发布时间 2023-07-28 16:58:21作者: RonChen

P8218 [深进1.例1] 求区间和

数列 \(\{a_n\}\) 的前缀和为 \(S_n = \sum_{i=1}^{n} a_i = a_1 + a_2 + \cdots + a_n\)
则区间 \([l,r]\) 的区间和为 \(a_l + a_{l+1} + \cdots + a_r = S_r - S_{l - 1}\)
预处理出前缀和，则单次区间和的查询就做到了 \(O(1)\) 复杂度

#include <cstdio>
const int MAXN = 100005;
int a[MAXN], sum[MAXN];
int main()
{
	int n, m;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		sum[i] = sum[i - 1] + a[i];
	}
	scanf("%d", &m);
	while (m--) {
		int l, r;
		scanf("%d%d", &l, &r);
		printf("%d\n", sum[r] - sum[l - 1]);
	}
	return 0;
}

P5638 [CSG Round 2] 光骓者的荣耀

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 1000005;
LL a[MAXN], sum[MAXN];
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n - 1; i++) {
        scanf("%lld", &a[i]);
        sum[i] = sum[i - 1] + a[i];
    }
    if (k == 0) {
        printf("%lld\n", sum[n - 1]);
    }
    LL ans = sum[n - 1];
    for (int i = 1; i <= n - k; i++) {
        LL cur = sum[n - 1] - (sum[i + k - 1] - sum[i - 1]);
        ans = min(ans, cur);
    }
    printf("%lld\n", ans);
    return 0;
}

P1115 最大子段和

#include <cstdio>
const int MAXN = 200005;
const int INF = 2e9;
int a[MAXN];
int main()
{
	int n;
	scanf("%d", &n);
	int sum = 0, ans = -INF, pre = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		sum += a[i];
		// sum 为以i位置结尾的前缀和
		// pre 为i位置之前的最小前缀和
		// 则sum-pre为以i位置为结尾的最大子段和
		if (sum - pre > ans) ans = sum - pre;	
		if (sum < pre) pre = sum;
	}
	printf("%d\n", ans);
	return 0;
}
  • 注意到结果可能是个负数，因此记录最大子段和的变量初始值应设成一个很小的负数

P1719 最大加权矩形

先求出每一列的前缀和，固定要选的矩形的上下边界，此时将每一列的总和压成一个数，则问题被转化为最大子段和问题

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 125;
int a[MAXN][MAXN], sumc[MAXN][MAXN];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
            sumc[i][j] = sumc[i - 1][j] + a[i][j];
        }
    int ans = -2e6;
    for (int i = 1; i <= n; i++) { // 枚举上边界
        for (int j = i; j <= n; j++) { // 枚举下边界
			// 计算最大子段和
            int maxsum = 0;
            int cur = 0;
            for (int k = 1; k <= n; k++) {
                if (cur < 0) cur = 0;
				// 将第i行到第j行在k这一列的和压成一个数
                cur += sumc[j][k] - sumc[i - 1][k]; 
                maxsum = max(maxsum, cur);
            }
            ans = max(ans, maxsum);
        }
    }
    printf("%d\n", ans);
    return 0;
}
  • 结果可能是个负数，记录结果的变量初始值应设成一个很小的负数

P3131 [USACO16JAN] Subsequences Summing to Sevens S

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 50005;
int a[MAXN];
int f[7]; // f数组记录1~6这七种前缀和（对7取余）第一次出现的位置
// 原理：如果i位置的前缀和（对7取余）等于j位置的前缀和（对7取余），说明i+1到j这一段区间加起来是7的倍数
// 特殊地：当前缀和本身就是7的倍数时，说明整个区间加起来是7的倍数
int main()
{
    int n;
    scanf("%d", &n);
    int sum = 0, ans = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        sum = (sum + x) % 7;
        if (sum == 0) ans = i;
        else if (f[sum] != 0) ans = max(ans, i - f[sum]);
        if (f[sum] == 0) f[sum] = i;
    }
    printf("%d\n", ans);
    return 0;
}

P3397 地毯

#include <cstdio>
const int MAXN = 1005;
int d[MAXN][MAXN], a[MAXN][MAXN];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        d[x1][y1]++;
        d[x1][y2 + 1]--;
        d[x2 + 1][y1]--;
        d[x2 + 1][y2 + 1]++;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + d[i][j];
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
    return 0;
}

P2367 语文成绩

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 5000005;
const int INF = 2e9;
int a[MAXN], d[MAXN];
int main()
{
	int n, p;
	scanf("%d%d", &n, &p);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		d[i] = a[i] - a[i - 1];
	}
	while (p--) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		d[x] += z; d[y + 1] -= z;
	}
	int ans = INF;
	for (int i = 1; i <= n; i++) {
		d[i] += d[i - 1]; // 对差分数组求前缀和还原出原数组
		ans = min(ans, d[i]);
	}
	printf("%d\n", ans);
	return 0;
}

P2004 领地选择

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 1005;
int sum[MAXN][MAXN];
int main()
{
    int n, m, c;
    scanf("%d%d%d", &n, &m, &c);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int x;
            scanf("%d", &x);
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + x;
        }
    int ans = sum[c][c];
    int ansi = 1, ansj = 1;
    for (int i = 1; i <= n - c + 1; i++)
        for (int j = 1; j <= m - c + 1; j++) {
            int x = i + c - 1;
            int y = j + c - 1;
            int cur = sum[x][y] - sum[i - 1][y] - sum[x][j - 1] + sum[i - 1][j - 1];
            if (cur > ans) {
                ans = cur;
                ansi = i;
                ansj = j;
            }
        }       
    printf("%d %d\n", ansi, ansj);
    return 0;
}

P2280 [HNOI2003] 激光炸弹

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 5005;
int a[MAXN][MAXN];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        int x, y, v;
        scanf("%d%d%d", &x, &y, &v);
        a[x + 1][y + 1] = v;
    }
    for (int i = 1; i <= 5001; ++i)
        for (int j = 1; j <= 5001; ++j) {
            a[i][j] += a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1];
        }
    int ans = 0;
    for (int i = m; i <= 5001; ++i)
        for (int j = m; j <= 5001; ++j) {
            ans = max(ans, a[i][j] - a[i - m][j] - a[i][j - m] + a[i - m][j - m]);
        }
    printf("%d\n", ans);
    return 0;
}
  • 注意题目中的 n 是目标的数量，坐标本身的取值范围是 0~5000，可以对其 +1 将值域平移到 1~5001

P3406 海底高铁

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 100005;
LL d[MAXN];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    int pre = 0;
    for (int i = 1; i <= m; i++) {
        int p;
        scanf("%d", &p);
        if (i > 1) {
            d[min(p, pre)]++;
            d[max(p, pre)]--;
        } 
        pre = p;
    }
    LL sum = 0, ans = 0;
    for (int i = 1; i <= n - 1; i++) {
        LL a, b, c;
        scanf("%lld%lld%lld", &a, &b, &c);
        sum += d[i];
        ans += min(b * sum + c, a * sum);
    }
    printf("%lld\n", ans);
    return 0;
}

P6067 [USACO05JAN] Moo Volume S

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 100005;
LL a[MAXN];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    sort(a + 1, a + n + 1);
    LL ans = 0;
    LL sum = 0;
    for (int i = 1; i <= n; i++) {
        ans += a[i] * (i - 1) - sum;
        sum += a[i];
    }
    printf("%lld\n", ans * 2);
    return 0;
}
  • 这里的前缀和需要 long long 类型才够存下
  • 注意 \((i-1)*a_i\) 的计算结果需要保证是 long long 类型