贾汪区建设局网站,网页制作与设计是什么,湖南省长沙市官网,怎么去掉wordpress底部ACM- 其他算法 一、前缀和模板例题1、区间余数求K倍区间个数#xff1a;AcWing 1230. K倍区间例题2、前缀和哈希求最长个数平分子串:Leetcode 面试题 17.05 字母与数字 二、差分1、一维差分2、二维差分 一、前缀和
模板
//一维前缀和
S[i] a[1] a[2] ... a[i]
a[l] ... … ACM- 其他算法 一、前缀和模板例题1、区间余数求K倍区间个数AcWing 1230. K倍区间例题2、前缀和哈希求最长个数平分子串:Leetcode 面试题 17.05 字母与数字 二、差分1、一维差分2、二维差分 一、前缀和
模板
//一维前缀和
S[i] a[1] a[2] ... a[i]
a[l] ... a[r] S[r] - S[l - 1]//二维前缀和
S[i, j] 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角(x2, y2)为右下角的子矩阵的和为
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] S[x1 - 1, y1 - 1]例题1、区间余数求K倍区间个数AcWing 1230. K倍区间
原题链接: https://www.acwing.com/problem/content/1232/
(原题来源: 第八届蓝桥杯省赛CB组,第八届蓝桥杯省赛JAVAB组)
import java.util.Scanner;public class Main{public static int[] sum new int[100010]; //前缀和取模后public static int[] cnt new int[100010]; //个数public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int k sc.nextInt();long ans 0;cnt[0] 1;for (int i 1; i n; i) {sum[i] sum[i - 1] sc.nextInt(); //计算前缀和sum[i] % k; //求出k的整数次倍剩下的数ans cnt[sum[i]]; //相当于减去前面的余数,得出以i为终点的合法子序列的种数 cnt[sum[i]]; //更新}System.out.println(ans);}
}例题2、前缀和哈希求最长个数平分子串:Leetcode 面试题 17.05 字母与数字
原题链接:https://leetcode-cn.com/problems/find-longest-subarray-lcci/
思路
字母1,数字-1,获得array的前缀和数组arr,同时记录和维护当前的sum的最远索引位置,比如对于A 1 A A 1 1 A 1 1 1 A 1 1 A,可以获得前缀和数组:1 0 1 2 1 0 1 0 -1 -2 -1. 我们可以发现对于第一个A来说,能和它匹配的最长子数组是最后一个0的位置. 以此类比,假如当前位置是字母,其前缀和为a,那么最远能匹配的位置一定是最远的前缀和为a-1的地方; 反之,假如当前位置是数字,其前缀和为a,那么最远能匹配的位置一定是最远的前缀和为a1的地方.
class Solution {
public:static const int N 100000;int book[N * 2 20], arr[N 20];vectorstring findLongestSubarray(vectorstring array) {int num 0, length array.size();for (int i 0; i length; i) {if (isNum(array[i][0])) -- num;else num;book[num N] i;arr[i] num;}vectorstring ans;int maxx 0, l -1, r -1;for (int i 0; i length; i) {if (isNum(array[i][0])) { int a book[N arr[i] 1];if (a i a - i maxx) {maxx a - i;l i, r a;}}else {int a book[N arr[i] - 1];if (a i a - i maxx) {maxx a - i;l i, r a;}}}if (maxx 0) return ans;else {for (int i l; i r; i) {ans.push_back(array[i]);}return ans;}}bool isNum(char c) {return c 0 c 9;}
};二、差分
1、一维差分
AcWing 797. 差分
原题链接https://www.acwing.com/problem/content/799/ 差分定义
首先给定一个原数组aa[1], a[2], a[3]……a[n];
然后我们构造一个数组b b[1] ,b[2] , b[3]…… b[i];
使得 a[i] b[1] b[2 ] b[3] …… b[i]
也就是说a数组是b数组的前缀和数组反过来我们把b数组叫做a数组的差分数组。 换句话说每一个a[i]都是b数组中从头开始的一段区间和。
解法
给区间[l, r]中的每个数加上cB[l] c, B[r 1] - c
代码
#includebits/stdc.husing namespace std;const int N 100010;//add为差分数组表示当前位置的变化
int nums[N], add[N];int main() {int n, m;cin n m;for (int i 1; i n; i) cin nums[i];while (m --) {int l, r, c;cin l r c;add[l] c;add[r 1] - c;}for (int i 1; i n; i) {add[i] add[i - 1];nums[i] add[i];cout nums[i] ;}return 0;
}2、二维差分
AcWing 798. 差分矩阵 原题链接https://www.acwing.com/problem/content/800/ 看代码应该就差不多了。
#include bits/stdc.husing namespace std;const int N 1010;int nums[N][N], add[N][N]; //add为差分矩阵void insert(int x1, int y1, int x2, int y2, int c) {add[x1][y1] c;add[x1][y2 1] - c;add[x2 1][y1] - c;add[x2 1][y2 1] c;
}int main() {int n, m, q;cin n m q;for (int i 1; i n; i) {for (int j 1; j m; j) {cin nums[i][j];}}while (q --) {int x1, y1, x2, y2, c;cin x1 y1 x2 y2 c;insert(x1, y1, x2, y2, c);}for (int i 1; i n; i) {for (int j 1; j m; j) {add[i][j] add[i - 1][j] add[i][j - 1] - add[i - 1][j - 1];nums[i][j] add[i][j];cout nums[i][j] ;}cout endl;}return 0;
}
