526互联

Day2 前缀和 差分 双指针

发布时间 2023-10-14 11:37:12作者: Gmor_cerr

前缀和

Luogu P2004 领地选择

二维前缀和板题，注意开 long long

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int n, m, c, x, y;
long long ans, a[1005][1005], s[1005][1005];


int main() {
	scanf("%d%d%d", &n, &m, &c);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			scanf("%lld", &a[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] + a[i][j];
	for (int i = 1; i <= n - c + 1; i++) {
		for (int j = 1; j <= m - c + 1; j++) {
			long long val = s[i+c-1][j+c-1] - s[i+c-1][j-1] - s[i-1][j+c-1] + s[i-1][j-1];
			if (val > ans) ans = val, x = i, y = j;
		}
	}
	cout << x << ' ' << y;
	return 0;
}

Luogu P3397 地毯

前缀和 + 差分

实际上枚举也是可以过的

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int n, m, a[1005][1005], s[1005][1005];
int x1, y1, x2, y2;

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		for (int l = x1; l <= x2; l++)
			for (int r = y1; r <= y2; r++)
				a[l][r]++;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			cout << a[i][j] << ' ';
		cout << '\n';
	}
	return 0;
}

Luogu P8772 [蓝桥杯 2022 省 A] 求和

对于 \(a_i\)，计算 \(a_i\) * \((a_{i+1} + ... + a_n)\)，可以使用前缀和

#include <iostream>
#include <cstdio>

using namespace std;

int n, a[200005], s[200005];
long long ans;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]), s[i] = s[i-1] + a[i];
	for (int i = 1; i <= n; i++) {
		ans += 1LL * a[i] * (s[n] - s[i]);
	}
	cout << ans;
	return 0;
}