✨ 海压竹枝低复举，风吹山角晦还明 🌏
🔥个人专栏：算法训练
🚀 欢迎关注：👍点赞 👂🏽留言 😍收藏 💞 💞 💞
目录
🚀 前言：
前面我们已经通过 【算法/学习】前缀和&&差分-CSDN博客 学习了前缀和&&差分的效相关知识，现在我们开始进行相关题目的练习吧
1. 校门外的树
思路：给[0, n]的数组都标记为1，然后输出m行范围，[l, r]都标记为0。
AC代码如下：
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main()
{
int n, m;
cin>>n>>m;
for(int i = 0; i <= n; i++) a[i] = 1;
int l, r;
for(int i = 1; i <= m; i++)
{
cin>>l>>r;
for(int j = l; j <= r; j++) a[j] = 0;
}
int cnt = 0;
for(int i = 0; i <= n; i++) {
if(a[i] == 1) cnt++;
}
cout<<cnt<<endl;
return 0;
}2. 值周
思路：
该题与上题意思相同，但是数据范围更大，因此我们不能使用上面的方法，我们可以使用前缀和，使让数组a内的数据先初始化为0，然后对[ l, r ]进行操作，a[l]--, a[r + 1]++，然后操作M次后，再 a[i] += a[i - 1];这样可以使得每个区域内的数都小于0.
AC代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e7 + 10;
int a[N];
int main()
{
int n, m;
cin >> n >> m;
int l, r;
for (int i = 0; i < m; i++){
cin >> l >> r;
a[l]--, a[r + 1]++; //前缀和，l-r标记为-1，r + 1又标记为1
}
for (int i = 1; i <= n; i++)
{
a[i] += a[i - 1];
}
int ans = 0;
for (int i = 0; i <= n; i++)
{
if (a[i] >= 0) ans++;
}
cout << ans << endl;
return 0;
}3. 中位数图
思路：
🔥1.由于是求中位数是b的连续子序列，那么我们只要找到一串连续的数，里面包含数b，且大于b的数的数目与小于b的数的数目相等，才是我们要找的序列。
🔥2.由于数据范围给的比较大，我们可以简化一下，把比b大的数直接赋值为1，小的就赋值为-1.
同时，我们再用一个sum来求和，sum往一边统计的时候，当sum==0的时候说明大于b的数的数目与小于b的数的数目相等，也就是我们找到了一个序列。
🔥3.那么两边都有的情况怎么考虑呢？我们可以往一边记录，用一个num数组来记录sum的加减情况。
我们可以来看一下题目的样例：
{5，7，2，4，3，1，6}->{1，1，-1，4，-1，-1，1}
🔥往左遍历：
1.sum+=-1-->sum==-1,可以这样，num[n+sum]+=1,也就是左边有一个比b小的情况加1.
2.sum+=1->sum==0,num[n+sum]+=1，左边刚好找到一个成功的序列，ans++.
3.sum+=1-->sum==1,num[n+sum]+=1,左边有一个比b大的情况加一。
🔥现在往右遍历：
先初始化sum=0.
然后sum+=-1->sum==-1,右边找到了一个比b小的数，而num[n+1]表示左边有一个比b小的情况的数目，也就是num[n-sum],我们可以用ans+=num[n-sum]。
后面同理，最后ans==4.（ans初始值为1，因为自己本身也是一个序列）
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
ll a[N], s[N];
int main()
{
int n, b;
cin >> n >> b;
int pos, x;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
if (a[i] > b)a[i] = 1;
else if (a[i] < b) a[i] = -1;
else pos = i;//标记中位数的位置
}
ll sum = 0, ans = 1; //自己也算一个
for (int i = pos - 1; i >= 1; i--) {
sum += a[i];
s[n + sum]++; //记录左边和为sum的数量
if (!sum) ans++; //sum为零就说明小于b的数的数量于大于b的数量相同
}
sum = 0; //再往右遍历，同时与左边比较
for (int i = pos + 1; i <= n; i++) {
sum += a[i];
ans += s[n - sum]; //加上左边与其互补的数量
if (!sum) ans++;
}
cout << ans << endl;
}4. 激光炸弹
思路：
先用二维前缀和的公式，求出g[x][y]的矩阵内的价值，然后就开始记录哪个正方形内的价值最大即可
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
int n, R;
int g[5005][5005];
int main()
{
cin >> n >> R;
memset(g, 0, sizeof g);
int xx = R, yy = R; //xx和yy表示边界，初始化为最小的R
for (int i = 0; i < n; i++)
{
int x, y, v;
cin >> x >> y >> v;
g[x][y] = v;
xx = max(xx, x); //记录输入的最大边
yy = max(yy, y);
}
for (int i = 1; i <= xx; i++){
for (int j = 1; j <= yy; j++){
g[i][j] = g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1] + g[i][j];
}
}
int ans = 0;
for (int i = R; i <= xx; i++){
for (int j = R; j <= yy; j++) {
ans = max(ans, g[i][j] - g[i - R][j] - g[i][j - R] + g[i - R][j - R]);
}
}
cout << ans << endl;
return 0;
}5. 二分
思路：
题意是求裁判最多说对了几次。
对于每次猜数，如果猜的数是𝑎a，那么根据题目有三种情况：
数大了：说对的范围是(−inf,𝑎](−inf,a]
数小了：说对的范围是[𝑎,+inf)[a,+inf)
数相等：说对的范围是[𝑎,𝑎+1)[a,a+1)
序列上操作，那么差分可以满足；然后把上面这些区间中，重叠次数最多的区间求出来，就是数所在的区间；这个区间重叠的次数就是我们要的答案。
由于数字较大，所以用了map搞离散化。
#include <iostream>
#include <map>
#include <limits.h>
using namespace std;
const int inf = INT_MAX;//int型数据最大值，因为是对每个数进行统计
const int N = 1e7 + 10;
int a[N];
char s[N];
map<int, int> mp;
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i] >> s[i];
for (int i = 1; i <= n; i++){
if (s[i] == '.') mp[a[i]]++, mp[a[i] + 1]--;
if (s[i] == '+') mp[a[i]]--, mp[-inf]++;
if (s[i] == '-')mp[inf]--, mp[a[i] + 1]++;
}
int ans = -inf, h = 0;
for (auto e : mp){
h += e.second;
ans = max(h, ans);
}
cout << ans << endl;
}6. 货仓选址
思路：
如下图，选择n个仓库位置得中位数即可，
该问题的本质就是求
的最小总和即可，当我们以后遇到该类问题时，只要使得p为所有ai的中位数即可
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> a;
for (int i = 0; i < n; i++){
int x;
cin >> x;
a.push_back(x);
}
sort(a.begin(), a.end());
int p = a[a.size() / 2];
int ans = 0;
for (int i = 0; i < n; i++) ans += abs(a[i] - p);
cout << ans << endl;
return 0;
}7. 最大子矩阵
思路：
求出其对应的前缀和矩阵，然后由于数据 是从 1- 109，直接枚举即可。
int getMaxMatrix(vector<vector<int>>& matrix) {
int n = matrix.size();
// 1.预处理前缀和
vector<vector<int>> s(n + 1, vector<int>(n + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
vector<int> ans(4);
int ret = -1e6 + 10;
// 2.找最大子矩阵 (四重for循环)
for (int x1 = 1; x1 <= n; x1++) {
for (int y1 = 1; y1 <= n; y1++) {
for (int x2 = x1; x2 <= n; x2++) {
for (int y2 = y1; y2 <= n; y2++) {
ret = max(ret, s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
}
}
}
}
return ret;
}
int main()
{
int n;
cin >> n;
vector<vector<int>> a(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
}
}
cout << getMaxMatrix(a) << endl;
return 0;
}
8. 主持人调度（二)
思路：
差分数组，题目等同于求当前位置最大被多少个区间包围。
//方法一：差分数组的映射
int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
map<int, int> mp;
for (int i = 0; i < startEnd.size(); i++) {
mp[startEnd[i][0]]++; //左边 ++
mp[startEnd[i][1]]--; //右边 --
}
int ans = 0, res = 0;
for (auto ip : mp) {
res += ip.second;
ans = max(ans, res);
}
return ans;
}
9. 寻找数组的中心下标
题目描述：给你一个整数数组 nums ，请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1
思路：
假设 两个 数组 f，g
f [ i ] 表示：[0, i - 1] 区间内所有元素的和 （前缀和数组）
- f [ i ] = f [ i - 1 ] + nums[ i - 1 ]
g[ i ] 表示：[i + 1, n - 1] 区间内所有元素的和（后缀和数组）
- g[ i ] = g[ i + 1] + nums[ i + 1 ]
则此时问题转化为求 [0, n] 内存在 i 使得 f [ i ] = g[ i ]
注：为避免越界访问，则 f [ 0 ] = g[ n - 1 ] = 0
填表顺序：f 表从左往右，g表从右往左
10. 除自身以外数组的乘积
题目描述：给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
思路：
该题与上题思路相同。
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n);
vector<int> f(n, 1), g(n, 1);
for (int i = 1; i < n; i++)
f[i] = f[i - 1] * nums[i - 1];
for (int i = n - 2; i >= 0 ; i--)
g[i] = g[i + 1] * nums[i + 1];
for (int i = 0; i < n; i++)
{
ans[i] = f[i] * g[i];
}
return ans;
}
};11. 和为 K 的子数组
题目描述：给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。（注：子数组内的数字可能是负数）
思路：
以 i 位置内为结尾的所有子数组，在[0，i - 1] 区间内，找有多少个前缀和等于 sum[ i ] - k
我们可以用一个哈希 <前缀和，该前缀和出现次数>来记录。
细节处理：
- 在计算 i 位置之前，哈希表里面只保存 [0，i - 1] 位置的前缀和
- 用一个变量 sum 标记前一个位置的前缀和
- 假设枚举到 0 位置时此时的整个前缀和为 k，那么就会去[0，-1]区间内找前缀和为0的，因此先需要初始化：hash[ 0 ] = 1
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> hash; // 统计前缀和出现次数
hash[0] = 1;
int sum = 0, ret = 0;
for (auto x : nums)
{
sum += x; // 计算当前位置前缀和
if (hash.count(sum - k)) // 如果在当前位置，哈希表内存在某个和等于 sum - k
ret += hash[sum - k]; //统计个数
hash[sum]++;
}
return ret;
}
};12. 和可被 K 整除的子数组
题目描述：给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的非空 子数组 的数目。子数组 是数组中 连续 的部分。
思路：
该题与上题思路类型。
我们先来补充几个知识。
同余定理：
- （a - b）% p = 0 --- > a % p = b % p
【负数 % 正数】的结果以及修正：
- 负数 % 正数 = 负数 --> (修正) a % p + p --> (正负统一) （a % p + p） % p
看完上面两个补充知识之后，只需在[0，i - 1] 区间内，找有多少个前缀和余数等于 sum % k，注：需要避免为负数要记得修正。
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
unordered_map<int, int> hash;
hash[0] = 1;
int sum = 0, ret = 0;
for (auto x : nums)
{
sum += x;
int r = (sum % k + k) % k; //修正后余数
if (hash.count(r))
ret += hash[r];
hash[r]++;
}
return ret;
}
};13. 连续数组
题目描述：给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
思路：
我们可以数组中所有的 0 修改成 -1，这题就转化成找出最长的子数组，使得子数组的所有元素的和为0即可，那么该题就与 和为 K 的子数组类似，和为K的子数组 --> 和为0的子数组
但是我们这题需要求的是长度。
那么我们这里的哈希表应该是<前缀和，前缀和下标>
细节处理：
- 当前位置使用完之后就丢进哈希表。
- 如果出现了重复的 <sum，i>，只保留前面的那一对<sum，i>
- 规定空的前缀的结束下标为 −1，由于空的前缀的元素和为 0，因此在遍历之前，首先在哈希表中存入键值对 (0,−1)：hash[ 0 ] = -1
- 长度计算：在遍历过程中，对于每个下标 i，如果 sum 的值在哈希表中已经存在，则取出 sum 在哈希表中对应的下标 j，nums 从下标 j + 1 到下标 i 的子数组中有相同数量的 0 和 1，因此该子数组的长度为 i − j，（不包括 j 那个格子）使用该子数组的长度更新最长连续子数组的长度；如果 counter 的值在哈希表中不存在，则将当前余数和当前下标 i 的键值对存入哈希表中。
class Solution {
public:
int findMaxLength(vector<int>& nums) {
// 哈希<前缀和，前缀和下标>
unordered_map<int, int> hash;
hash[0] = -1; //默认有一个前缀和为 0 的情况
int sum = 0, ret = 0;
for (int i = 0; i < nums.size(); i++)
{
//计算当前位置的前缀和
sum += nums[i] == 0 ? -1 : 1; //为 0 时则处理为 -1
if (hash.count(sum)) //判断当前前缀和是否存在
ret = max(ret, i - hash[sum]);
else hash[sum] = i; // 不存在才存，因为要存该前缀和对应的最小的下标
}
return ret;
}
};14. 矩阵区域和
题目描述：给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：
思路：
用二维前缀和求法：sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[ i ][ j ];求得该矩阵的前缀和
answer[ i ][ j ] 的求法：则相当于是以[i，j]为中心从[i - k，j - k] 到 [i + k，j + k] 的矩阵，注意越界的问题，因此 我们应该做一些特殊处理 如 x1 = max (0，i - k) ，x2 = min (m - 1，i + k)
还要注意下标的映射问题：我们在填前缀和表时，需要多加一行一列，此时前缀和上的下标[i,，j] 在mat矩阵上的映射应该为[i - 1，j - 1]，然后我们使用前缀和表去填answer时，answer表上的下标[i，j]在 前缀和 表上的映射应该为[i + 1，j + 1]
class Solution {
public:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> sum(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
vector<vector<int>> answer(m, vector<int>(n));
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
int x2 = min(m - 1, i + k) + 1, y2 = min(n - 1, j + k) + 1;
// 填表
answer[i][j] = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
}
}
return answer;
}
};15. 求x路径上最大和值
题目描述：
有一张网格地图，我们使用(i, j)表示网格中从上往下数第i行和从左往右数第 j 列的单元格。地图的每一个格子中都有一些怪物，我们使用 a(i, j) 表示坐标(i,j)处的怪物数量。
现在有条龙，它可以对着地图的任意一个坐标吐出火焰来打败怪物。火焰会打败坐标 (x,y) 内的所有怪物，并向4个方向：(x - 1,y - 1),(x - 1,y + 1), (x + 1,y - 1),(x + 1,y + 1)，并且一直延申即火焰会在矩形中会形成一个"X'形状。火焰会打败经过的每个坐标中的所有怪物。
例如，有一个图，数据如下：
9 6 3 2 2 8 5 10 2 8 2 2 8 5 3 9 6 10 5 2
我们对坐标(2,3)使出 火焰，能打败6+2+10+2+5+9+2= 36 只怪物。
现在释放一次火焰最多能打败多少只怪物？
输入描述:
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1 ≤ T ≤ 10^4)代表数据组数，每组测试数据描述如下:
第一行输入两个整数 n,m(1 ≤ n,m ≤ 10^3)代表地图的大小。
此后 n 行，第 i 行输入 m 个整数 a(i, 1),a(i,2),…..,a(i,m) (1 ≤ a(i,j) ≤ 10^9)，代表地图中每个坐标上的怪物数量。
除此之外，保证单个测试文件的 n * m之和不超过 10^6.
输出描述:
对于每一组测试数据，新起一行。输出一个整数，代表一次“龙之吐息"最多能打败的怪物数量。
样例输入
3
4 5
9 6 3 2 2
8 5 10 2 8
2 2 8 5 3
9 6 10 5 2
1 3
1 2 3
3 1
3
2
1样例输出
41
3
3思路：
利用前缀和即可
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 1005;
ll dp1[N][N], dp2[N][N], dp3[N][N], dp4[N][N];
void solve()
{
int n, m;
cin >> n >> m;
// 前缀和，需要多出上下左右各一行一列
vector<vector<ll>> a(n + 2, vector<ll>(m + 2, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) cin >> a[i][j];
}
// 初始化
for (int i = 0; i <= n + 1; i++) {
for (int j = 0; j <= m + 1; j++) {
dp1[i][j] = dp2[i][j] = dp3[i][j] = dp4[i][j] = 0;
}
}
// 左上角
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp1[i][j] = a[i][j] + dp1[i - 1][j - 1];
}
}
// 右上角
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 1; j--) {
dp2[i][j] = a[i][j] + dp2[i - 1][j + 1];
}
}
// 左下角
for (int i = n; i >= 1; i--) {
for (int j = 1; j <= m; j++) {
dp3[i][j] = a[i][j] + dp3[i + 1][j - 1];
}
}
// 右下角
for (int i = n; i >= 1; i--) {
for (int j = m; j >= 1; j--) {
dp4[i][j] = a[i][j] + dp4[i + 1][j + 1];
}
}
ll cnt = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
ll t = dp1[i][j] + dp2[i][j] + dp3[i][j] + dp4[i][j] - 3 * a[i][j];
cnt = max(cnt, t);
}
}
cout << cnt << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}