【算法经典题集】前缀和与数学(持续更新~~~)

😽PREFACE
🎁欢迎各位→点赞👍 + 收藏⭐ + 评论📝
📢系列专栏：算法经典题集
🔊本专栏涉及到的知识点或者题目是算法专栏的补充与应用
💪种一棵树最好是十年前其次是现在

前缀和

一维前缀和

k倍区间

给定一个长度为 N 的数列，A1,A2,…AN，如果其中一段连续的子序列 Ai,Ai+1,…Aj之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。
你能求出数列中总共有多少个 K 倍区间吗？
输入格式
第一行包含两个整数 N 和 K。
以下 N 行每行包含一个整数 Ai。
输出格式
输出一个整数，代表 K 倍区间的数目。
数据范围
1≤N,K≤100000
1≤Ai≤100000

输入样例：
5 2
1
2
3
4
5
输出样例：
6

分析：求区间[l,r]的和是k的倍数的个数。求区间和，我们可以通过前缀和来求出。我们规定sum[i]表示第1个元素到第i个元素的和。那么sum[r] - sum[l-1]就是区间[l,r]的和。区间[l,r]的和是k的倍数即(sum[r] - sum[l-1])%k == 0 即sum[r]%k == sum[l-1]%k。对前缀和取模之后，两个相等的前缀和就能组成一个k倍区间。

总共出现了3次模为1的情况，而每两次模为1组合起来可以模0，比如1,2加起来模为1，1,2,3,4,5加起来模为1，那么这两种情况组合起来（区间做减）是3,4,5就是模为0的情况。所以一共出现了3次模为1的情况，那么两两组合的情况一共有三种，再加上本来模为0的情况有3次，一共就6次模为0的情况。“k倍区间就加上cnt[sum[i]]”只是实现了计算模不为0的时候的情况两两组合的组合数量。

按前缀和做差来想

①1=1②1+2=3③1+2+3=6④1+2+3+4=10⑤1+2+3+4+5=15

3次模为1的情况是①②⑤

两两组合后模为0，即：②-①=2；⑤-①=2+3+4+5=14；⑤-②=3+4+5=12

本来模为0的情况有③④，组合后得到4，即一共3种情况

3+3=6

#include <iostream>
#include <cstdio>
using namespace std;
int n, k;
int sum[100005], cnt[100005];
long long ans = 0;
int main()
{scanf("%d%d", &n, &k);for (int i = 1; i <= n; i++){int x;scanf("%d", &x);sum[i] += (sum[i - 1] + x) % k;//   求前缀和 ans += cnt[sum[i]];//    加上在此之前与它同余的前缀和（模k后） cnt[sum[i]]++;//    对前缀和模k后的余数统计出现次数 }printf("%lld", ans + cnt[0]);return 0;
}

二维前缀和

激光炸弹

地图上有 N 个目标，用整数 Xi,Yi表示目标在地图上的位置，每个目标都有一个价值 Wi。
注意：不同目标可能在同一位置。
现在有一种新型的激光炸弹，可以摧毁一个包含 R×R个位置的正方形内的所有目标。
激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 x，y轴平行。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。
输入格式
第一行输入正整数 N 和 R，分别代表地图上的目标数目和正方形包含的横纵位置数量，数据用空格隔开。
接下来 N 行，每行输入一组数据，每组数据包括三个整数 Xi,Yi,Wi，分别代表目标的 x 坐标，y 坐标和价值，数据用空格隔开。
输出格式
输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。

数据范围
0≤R≤10^9
0<N≤10000
0≤Xi,Yi≤5000
0≤Wi≤1000
输入样例：
2 1
0 0 1
1 1 1
输出样例：
1

#include <bits/stdc++.h>using namespace std;const int N = 5e3 + 10; int s[N][N];
int n, r;int main() {cin >> n >> r;r = min(5001, r); // 因为r最大可以取 10^9for (int i = 0; i < n; i++) {int x, y, w;cin >> x >> y >> w;s[++x][++y] += w; //右移一位, 就不需要考虑边界了, 并且必须是+=, 不能是=, 因为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 ans = 0;for (int i = r; i <= 5001; i++) {for (int j = r; j <= 5001; j++) {ans = max(ans, s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r]);}}cout << ans << endl;return 0;
}

数学

买不到的数目

小明开了一家糖果店。
他别出心裁：把水果糖包成4颗一包和7颗一包的两种。
糖果不能拆包卖。
小朋友来买糖的时候，他就用这两种包装来组合。
当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。
你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。
大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。
输入格式
两个正整数 n,m，表示每种包装中糖的颗数。
输出格式
一个正整数，表示最大不能买到的糖数。

数据范围
2≤n,m≤1000，
保证数据一定有解。
输入样例：
4 7
输出样例：
17

#include <bits/stdc++.h>
using namespace std;
int main()
{int p,q;cin>>p>>q;cout<<(p-1)*(q-1)-1<<endl;return 0;
}

蚂蚁感冒

长 100 厘米的细长直杆子上有 n 只蚂蚁。
它们的头有的朝左，有的朝右。
每只蚂蚁都只能沿着杆子向前爬，速度是 1 厘米/秒。
当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。
这些蚂蚁中，有 1 只蚂蚁感冒了。
并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。
请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。
输入格式
第一行输入一个整数 n, 表示蚂蚁的总数。
接着的一行是 n 个用空格分开的整数 Xi, Xi 的绝对值表示蚂蚁离开杆子左边端点的距离。
正值表示头朝右，负值表示头朝左，数据中不会出现 0 值，也不会出现两只蚂蚁占用同一位置。
其中，第一个数据代表的蚂蚁感冒了。
输出格式
输出1个整数，表示最后感冒蚂蚁的数目。

数据范围
1<n<50,
0<|Xi|<100
输入样例1：
3
5 -2 8
输出样例1：
1
输入样例2：
5
-10 8 -20 12 25
输出样例2：
3

#include <bits/stdc++.h>using namespace std;const int N = 55;int n;
int x[N];int main()
{cin >> n;for (int i = 0; i < n; i ++ ) cin >> x[i];int left = 0, right = 0;    // 分别表示左边向右走的蚂蚁数量，和右边向左走的蚂蚁数量for (int i = 1; i < n; i ++ )if (abs(x[i]) < abs(x[0]) && x[i] > 0) left ++ ;else if (abs(x[i]) > abs(x[0]) && x[i] < 0) right ++ ;if (x[0] > 0 && right == 0 || x[0] < 0 && left == 0) cout << 1 << endl;else cout << left + right + 1 << endl;return 0;
}

饮料换购

乐羊羊饮料厂正在举办一次促销优惠活动。乐羊羊C型饮料，凭3个瓶盖可以再换一瓶C型饮料，并且可以一直循环下去(但不允许暂借或赊账)。
请你计算一下，如果小明不浪费瓶盖，尽量地参加活动，那么，对于他初始买入的 n 瓶饮料，最后他一共能喝到多少瓶饮料。
输入格式
输入一个整数 n,表示初始买入的饮料数量。
输出格式
输出一个整数，表示一共能够喝到的饮料数量。
数据范围
0<n<10000
输入样例：
100
输出样例：
149

#include <iostream>using namespace std;int main()
{int n;cin >> n;int res = n;while (n >= 3){res += n / 3;n = n / 3 + n % 3;}cout << res << endl;return 0;
}