1.DP34[模板]一维前缀和

一维前缀和

#include <iostream>
#include <vector>
using namespace std;int main()
{int n,q;cin>>n>>q;vector<long long> v(n+1);for(int i=1;i<=n;i++){cin>>v[i];}//1.维护一个前缀和数组vector<long long> dp(n+1);for(int i=1;i<=n;i++){dp[i]=dp[i-1]+v[i];}//2.使用前缀和数组int l,r;while(q--){cin>>l>>r;cout<<dp[r]-dp[l-1]<<endl;}return 0;
}

2.DP35[模板]二维前缀和

二维前缀和

#include <iostream>
#include <vector>
using namespace std;int main()
{int n,m,q;cin>>n>>m>>q;vector<vector<long long>>arr(n+1,vector<long long>(m+1));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>arr[i][j];}}vector<vector<long long>>dp(n+1,vector<long long>(m+1));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){dp[i][j] = dp[i-1][j]+dp[i][j-1]+arr[i][j]-dp[i-1][j-1];}}int x1,y1,x2,y2;while(q--){cin>>x1>>y1>>x2>>y2;cout<<dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]<<endl;}return 0;
}

3.寻找数组的中心下标

寻找数组的中心下标

class Solution {
public:int pivotIndex(vector<int>& nums) {int n = nums.size();//1.维护一个前缀和和后缀和数组vector<int> f(n);for(int i=1;i<n;i++){f[i] = f[i-1]+nums[i-1];}vector<int> g(n);for(int i=n-2;i>=0;i--){g[i] = g[i+1]+nums[i+1];}//2.使用前缀和和后缀和数组for(int i=0;i<n;i++){if(f[i] == g[i]){return i;}}return -1;}
};

4.除自身以外数组的乘积

除自身以外数组的乘积

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> f(n);f[0] = 1;for(int i=1;i<n;i++){f[i] = f[i-1]*nums[i-1];}vector<int> g(n);g[n-1] = 1;for(int i = n-2;i>=0;i--){g[i] = g[i+1]*nums[i+1];}vector<int> ret(n);for(int i=0;i<n;i++){ret[i] = f[i]*g[i];}return ret;}
};

5.和为K的子数组

和为K的子数组

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)) ret+=hash[sum-k];hash[sum]++;}return ret;}
};

6.和可被K整除的子数组

和可被K整除的子数组

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {//前缀和+哈希表unordered_map<int,int> hash;hash[0%k] = 1;int ret = 0,sum = 0;for(auto x:nums){sum+=x;int r = (sum%k+k)%k;if(hash.count(r)) ret+=hash[r];hash[r]++;}return ret;}
};

7.连续数组

连续数组

class Solution {
public:int findMaxLength(vector<int>& nums) {//前缀和+哈希表//哈希表里面存储的是前缀和和对应的下标unordered_map<int,int> hash;hash[0] = -1;int sum = 0,ret = 0;for(int i=0;i<nums.size();i++){sum+=nums[i]==0?-1:1;if(hash.count(sum)) ret = max(ret,i-hash[sum]);else hash[sum] = i;}return ret;}
};

8.矩阵区域和

矩阵区域和

class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {int m = mat.size(),n = mat[0].size();//二维前缀和+dp数组vector<vector<int>> dp(m+1,vector<int>(n+1));for(int i = 1;i<=m;i++){for(int j=1;j<=n;j++){dp[i][j] = dp[i-1][j]+dp[i][j-1]+mat[i-1][j-1]-dp[i-1][j-1];}}//使用前缀和数组dpvector<vector<int>> ret(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;ret[i][j] = dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];}}return ret;}
};