前缀和相关题型

1230. K倍区间

题目描述

给定一个长度为 $N$ 的数列，$A_1, A_2, … A_N$，如果其中一段连续的子序列 $A_i,A_{i+1},… A_j$ 之和是 $K$ 的倍数，我们就称这个区间 $[i,j]$ 是 $K$ 倍区间。
你能求出数列中总共有多少个 $K$ 倍区间吗？

输入格式

第一行包含两个整数 $N$ 和 $K$。
以下 $N$ 行每行包含一个整数 $A_i$。

输出格式

输出一个整数，代表 $K$ 倍区间的数目。

数据范围

$1 \leqslant N, K\leqslant 100000$
$1 \leqslant A_i \leqslant 100000$

输入样例：

5 2
1
2
3
4
5

输出样例：

6

思路

翻译：求区间 $[l,r]$ 的和是 $k$ 的倍数的个数。

求区间和，我们可以通过 前缀和 来求出。
定义 sum[i] 表示第 $1$ 个元素到第 $i$ 个元素的和，那么 s[r] - s[l-1] 就是区间 $[l,r]$ 的和。
若满足条件：区间 $[l,r]$ 的和是k的倍数，即 (s[r] - s[l-1]) % k == 0 ，等价于 s[r] % k == s[l-1] % k 。

说人话，这也就意味着：

如果 s[r] mod k 和 s[l - 1] mod k 的余数相等，那么 s[r] - s[l - 1] 的差值必然是 $k$ 的倍数。

比如：13 % 7 == 20 % 7，则 (20 - 7) % 7 == 0

那么题目就是要我们求 前缀和%k==0 的组合有多少种。

用 cnt[i] 存储目前为止前缀和相同的个数，$i$ 表示这个前缀和的值。
每次用 res 来递加 cnt[i] 相同的个数，前面有几个 前缀和的值 和 当前前缀和 相等，那么这个前缀和就能和前面每一个组成一个组合，所以要 res += cnt[s[i]] ，然后再加上现在的前缀和，即 cnt[s[i]]++ 。
初始化 cnt[0] = 1 ，因为当 s[i] == 0 时，这个前缀和本身就是 $k$ 的倍数，不需要再跟别的前缀和组合，计算结果时就要加上这一个。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 1e5 + 10;

int n, k;
ll s[N];
ll cnt[N];

int main()
{
    cin >> n >> k;
    
    ll res = 0;
    cnt[0] = 1;
    for (int i = 1; i <= n; i++){
        cin >> s[i];
        s[i] = (s[i] + s[i - 1]) % k;   // 每次前缀和都取模
        
        res += cnt[s[i]];   // 和前面每一个都组合一下
        cnt[s[i]]++;        // 现在又多了一个
    }
    
    cout << res << endl;
    
    return 0;
}

3956. 截断数组

题目描述

给定一个长度为 $n$ 的数组 $a_1, a_2, …, a_n$ 。
现在，要将该数组从中间截断，得到三个非空子数组。
要求，三个子数组内各元素之和都相等。
请问，共有多少种不同的截断方法？

输入格式

第一行包含整数 $n$。
第二行包含 $n$ 个整数 $a_1, a_2, …, a_n$ 。

输出格式

输出一个整数，表示截断方法数量。

数据范围

前六个测试点满足 $1 \leqslant n \leqslant 10$。

所有测试点满足 $1 \leqslant n \leqslant 10^5, −10000 \leqslant a_i \leqslant 10000$。

输入样例1：

4
1 2 3 3

输出样例1：

1

输入样例2：

5
1 2 3 4 5

输出样例2：

0

输入样例3：

2
0 0

输出样例3：

0

思路

先预处理前缀和，先判断如果 s[n] % 3 != 0，则不能被均分为三份，输出 0.

然后从 i = 3 开始枚举前缀和数组，以 $i$ 作为切割点，s[i - 2] 为第一段，s[n] - s[i - 1] 为第三段，如果 第一段 = 第三段 = $\frac{s[n]}{3}$​，则第二段也一定相等，都符合条件。

先判断第一段是否符合，记录个数，如果第三段不符合，则表示该切割点不行，继续后移，每次当第三段符合时，都加上第一段符合的个数即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 1e5 + 10;

int n;
ll s[N];

int main()
{
    cin >> n;
    
    for (int i = 1; i <= n; i++){
        cin >> s[i];
        s[i] += s[i - 1];
    }
    
    if (s[n] % 3){
        cout << 0 << endl;
        return 0;
    }
    
    ll cnt = 0, res = 0;
    for (int i = 3; i <= n; i++){
        if (s[i - 2] == s[n] / 3) cnt++;
        if (s[n] - s[i - 1] == s[n] / 3) res += cnt;
    }
    
    cout << res << endl;
    
    return 0;
}

99. 激光炸弹

题目描述

地图上有 $N$ 个目标，用整数 $X_i, Y_i$ 表示目标在地图上的位置，每个目标都有一个价值 $W_i$ 。

注意：不同目标可能在同一位置。

现在有一种新型的激光炸弹，可以摧毁一个包含 $R×R$ 个位置的正方形内的所有目标。
激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 $x, y$ 轴平行。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。

输入格式

第一行输入正整数 $N$ 和 $R$，分别代表地图上的目标数目和正方形包含的横纵位置数量，数据用空格隔开。
接下来 $N$ 行，每行输入一组数据，每组数据包括三个整数 $X_i, Y_i, W_i$ ，分别代表目标的 $x$ 坐标，$y$ 坐标和价值，数据用空格隔开。

输出格式

输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。

数据范围

$0 \leqslant R \leqslant 10^9$
$0 < N \leqslant 10000$
$0 \leqslant X_i, Y_i \leqslant 5000$
$0 \leqslant W_i \leqslant 1000$

输入样例：

2 1
0 0 1
1 1 1

输出样例：

1

思路

递推求出二维前缀和 。

因为题目的内存限制，我们直接用二维数组读入数据，边读边加。
然后我们再求其前缀和，再从地图右下角枚举边长为 $R$​ 的正方形，通过下式

s[i][j] - s[i - R][j] - s[i][j - R] + s[i - R][j - R]

即可计算出该正方形内所有目标的价值之和。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 5e3 + 10;  // 不能开到 1e5 + 10，二维会爆栈

int n, r;
int s[N][N];

int main()
{
    cin >> n >> r;
    r = min(5001, r);  // 因为r最大可取到10^9,但地图没有这么大
    
    for (int i = 1; i <= n; i++){
        int x, y, w;
        cin >> x >> y >> w;
        s[++x][++y] += w;   // 因为数据范围是从0开始的
    }
    
    //如果i从0开始那么i-1会导致数组越界
    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 res = 0;
    for (int i = r; i <= 5001; i++){
        for (int j = r; j <= 5001; j++){
            res = max(res, s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r]);
        }
    }
    
    cout << res << endl;
    
    return 0;
}