算法竞赛进阶指南——基本算法（前缀和与差分）

一维前缀和：
S[i] = a[1] + a[2] + … a[i]
a[l] + … + a[r] = S[r] - S[l - 1]

二维前缀和：
S[i, j] = 第i行j列格子左上部分所有元素的和
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

一维差分：
给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

二维差分：
给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

1.激光炸弹

https://www.acwing.com/problem/content/101/

#include<iostream>
using namespace std;
const int N = 5005;
int s[N][N];

int main(){
    int n, r;
    cin>>n>>r;
    //防止炸弹范围超过地图面积
    r = min(r, 5001);
    int x, y, z;
    while(n--){
        cin>>x>>y>>z;
        //要用前缀和，所以下标从1开始
        x++;
        y++;
        //不同目标可能出现在同一位置
        s[x][y] += z;
    }
    for(int i = 1; i <= 5001; i++){
        for(int j = 1; j <= 5001; j++){
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; 
        }
    }
    int ans = 0, cnt = 0;
    for(int i = r; i <= 5001; i++){
        for(int j = r; j <= 5001; j++){
            cnt = s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r];
            ans = max(ans, cnt);
        }
    }
    cout<<ans;
    return 0;
}
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

2.增减序列

https://www.acwing.com/problem/content/102/

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int n;

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
        b[i] = a[i] - a[i - 1];
    }
    //p为正数的总和，q为负数的总和
    long long p = 0, q = 0;
    for(int i = 2; i <= n; i++){
        if(b[i] > 0){
            p += b[i];
        }else if(b[i] < 0){
            q -= b[i];
        }
    }
    //cnt是操作数，ans是方案数
    long long cnt = 0, ans = 0;
    cnt = min(p, q) + abs(p - q);
    ans = abs(p - q) + 1;
    cout<<cnt<<endl<<ans;
    return 0;
}
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

3.最高的牛

https://www.acwing.com/problem/content/103/

#include<iostream>
#include<map>
using namespace std;
const int N = 1e4 + 10;
map<pair<int, int>, bool> mp;
int n, p, h, m;
int c[N], d[N];

int main(){
    cin>>n>>p>>h>>m;
    int a, b;
    for(int i = 1; i <= m; i++){
        cin>>a>>b;
        if(a > b) swap(a, b);
        if(!mp[pair(a, b)]){
            mp[make_pair(a, b)] = true;
            d[a + 1]--;
            d[b]++;
        }
    }
    for(int i = 1; i <= n; i++){
        c[i] = c[i - 1] + d[i];
        cout<<c[i] + h<<endl;
    }
    return 0;
}
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