企业官网建设流程全解析

题目引用牛客BGN51

对于给定的长度为 𝑛的数组a{a1,a2,a3......},你需要构建一个能够维护区间和信息的数据结构，使得其能支持： 区间和查询：输出输出 [𝑙,𝑟] 这个区间中的元素之和.

输入描述：第一行输入两个整数 𝑛,𝑞(1≦𝑛,𝑞≦1^6) 代表数组中的元素数量、操作次数。第二行输入 𝑛个整数 𝑎1,𝑎2,…,𝑎𝑛(−10^9≦𝑎𝑖≦10^9)代表初始数组。此后 𝑞 行，每行输入两个整数 𝑙,𝑟(1≦𝑙≦𝑟≦𝑛)
代表区间和查询。

输出描述：
对于每一次询问，输出一行一个整数代表区间和。

这个题用循环可解，但在数据量大的时候会超时，所以我学习了前缀和，先看代码：

import java.util.*; public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int n = input.nextInt(); int q = input.nextInt(); int []arr = new int[n + 1];//开数组n+1,可以防止越界 for (int i = 1; i <= n; i++) { arr[i] = input.nextInt(); } long []brr = new long[n + 1];//用long应对数据量大的情况 brr[0] = 0; for (int j = 1; j <= n; j++) { brr[j] = brr[j - 1] + arr[j];// 构建前缀和：brr[j] = 前 j 个数的和 } while (q-- > 0) { int l = input.nextInt(); int r = input.nextInt(); System.out.println(brr[r] - brr[l - 1]);//少用一个循环，用空间换时间 } input.close(); } }

有了一维就有二维

引用：牛客BGN56:(二维前缀和）

给定一个由n行m列整数组成的矩阵{ai,j}（下标均从1开始）。
现有q次独立查询，第k次查询给定四个整数x1,y1,x2,y2x1,y1,x2,y2，表示左上角坐标(x1,y1)(x1,y1)与右下角坐标(x2,y2)(x2,y2)满足1≦x1≦x2≦n1≦x1≦x2≦n且1≦y1≦y2≦m1≦y1≦y2≦m。请你计算矩阵中全部元素之和，你需要依次查询对应子矩阵的元素和。在一行上输入三个整数n,m,q(1≦n,m≦pow(10,3); 1≦q≦pow(10,5)n,m,q(1≦n,m≦pow(10,3); 1≦q≦pow(10,5)，依次表示矩阵的行数、列数与查询次数。此后n行，每行输入m个整数ai,1,ai,2,…,ai,m(−pow(10,9)≦ai,j≦pow（10,9)ai,1​,ai,2​,…,ai,m​(−pow(10,9)≦ai,j≦pow(10,9)，表示矩阵第ii行的元素；共计n×m个整数。
此后q行，每行输入四个整数x1,y1,x2,y2x1​,y1​,x2​,y2​，所有变量均满足
1≦x1≦x2≦n,1≦y1≦y2≦m1≦x1≦x2≦n,1≦y1≦y2≦m。

输出描述：

对于每一次查询，在一行上输出一个整数，表示对应子矩阵元素之和。

代码如下：

import java.io.*; import java.util.*; public class Main { // 存储原始矩阵（全局变量，方便方法调用） static int[][] matrix; // 存储二维前缀和数组（用 long 防止数据溢出） static long[][] sum; public static void NumMatrix() { // 矩阵真实行数（因为从 1 开始存，所以长度 -1） int n = matrix.length - 1; // 矩阵真实列数 int m = matrix[0].length - 1; // 初始化前缀和数组，开大一点防止越界 sum = new long[n + 2][m + 2]; // 填充前缀和数组 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { // 二维前缀和核心公式 sum[i][j] = sum[i - 1][j] // 上方区域和 + sum[i][j - 1] // 左方区域和 - sum[i - 1][j - 1] // 重复区域和（减重复） + matrix[i][j]; // 当前位置的值 } } } public static long getSum(int a, int b, int c, int d) { // 子矩阵和公式（容斥原理） return sum[c][d] // 大矩形总和 - sum[a - 1][d] // 减去上部分 - sum[c][b - 1] // 减去左部分 + sum[a - 1][b - 1]; // 加回多减的重复部分 } public static void main(String[] args) throws IOException { // 快速读取输入 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 快速输出结果 PrintWriter out = new PrintWriter(System.out); // 字符串分割器：把一行的多个数字分开读取 StringTokenizer st; // 读取第一行：n 行 m 列 q 次查询 st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); // 初始化矩阵，从 1 开始存储（方便前缀和计算） matrix = new int[n + 2][m + 2]; // 读取矩阵的每一行数据 for (int i = 1; i <= n; i++) { st = new StringTokenizer(br.readLine()); for (int j = 1; j <= m; j++) { matrix[i][j] = Integer.parseInt(st.nextToken()); } } // 构建前缀和数组 NumMatrix(); // 处理 q 次查询 while (q-- > 0) { st = new StringTokenizer(br.readLine()); // 读取查询的子矩阵坐标 int x1 = Integer.parseInt(st.nextToken()); int y1 = Integer.parseInt(st.nextToken()); int x2 = Integer.parseInt(st.nextToken()); int y2 = Integer.parseInt(st.nextToken()); // 查询并输出结果 out.println(getSum(x1, y1, x2, y2)); } // 刷新输出缓冲区，保证内容输出 out.flush(); // 关闭流 br.close(); out.close(); } }

引用牛客BGN57(二位差分）

描述：
给定一个 n × m 的整数矩阵 b，矩阵的下标从 1 开始记作 bi,j。现在需要支持 q 次操作，第 t 次操作给定五个整数 x1, y1, x2, y2, k，表示将以左上角 (x1,y1)、右下角 (x2,y2) 为边界的子矩阵内的每个元素都增加 k。全部操作执行完毕后，请输出最终矩阵。
【名词解释】
子矩阵：从矩阵中连续选取若干行与若干列得到的矩形区域。
输入描述：
在一行上输入三个整数 n, m, q（1 ≤ n, m ≤ 1000；1 ≤ q ≤ 10^5），依次表示矩阵行数、列数与操作次数。
此后 n 行，第 i 行输入 m 个整数 bi,1, bi,2, …, bi,m（-10^9 ≤ bi,j ≤ 10^9），描述矩阵初始元素。
再之后 q 行，每行输入五个整数 x1, y1, x2, y2, k（1 ≤ x1 ≤ x2 ≤ n；1 ≤ y1 ≤ y2 ≤ m；-10^9 ≤ k ≤ 10^9），描述一次矩阵加法操作。
输出描述：
输出 n 行，每行 m 个整数，表示所有操作结束后矩阵的最终状态。同行相邻元素之间使用一个空格分隔。

代码如下：

#include <bits/stdc++.h> using namespace std; // 原矩阵（从 1 开始下标，方便差分计算） vector<vector<long>> matrix; // 二维差分数组（核心：所有区间修改都只操作这个数组，开long防止数据量过大） vector<vector<long>> diff; // 矩阵的行数 n，列数 m int n, m; // 功能：根据原矩阵 matrix，初始化二维差分数组 diff // 对应一维：crr[i] = arr[i] - arr[i-1] void getDiff() { for (int i = 1; i <= n; i++) { // 遍历每一行 for (int j = 1; j <= m; j++) { // 遍历每一列 // 二维差分核心公式：当前值 - 左边 - 上边 + 左上角（抵消重复减） diff[i][j] = matrix[i][j] - matrix[i][j-1] - matrix[i-1][j] + matrix[i-1][j-1]; } } } // 功能：对矩形区域 (a,b) → (c,d) 内所有数统一加 k // 二维差分标准操作：只修改 4 个点，O(1) 完成区间修改 void getNum(int a,int b,int c,int d,int k) { diff[a][b] += k; // 矩形左上角 +k diff[a][d+1] -= k; // 矩形右上角右边 -k diff[c+1][b] -= k; // 矩形左下角下边 -k diff[c+1][d+1] += k; // 矩形右下角右下角 +k（抵消前面的减法） } // 功能：对差分数组 diff 求二维前缀和，还原成最终的答案矩阵 // 对应一维：arr[i] = arr[i-1] + crr[i] void getSum() { for (int i = 1; i <= n; i++) { // 遍历每一行 for (int j = 1; j <= m; j++) { // 遍历每一列 // 二维前缀和公式：当前值 + 左边 + 上边 - 左上角（去重） diff[i][j] = diff[i][j] + diff[i][j-1] + diff[i-1][j] - diff[i-1][j-1]; } } } int main() { cin >> n >> m; // 2. 初始化原矩阵：开 (n+1)行 (m+1)列（从 1 开始存） matrix.resize(n+1, vector<long>(m+1)); // 3. 初始化差分数组：开 (n+2)行 (m+2)列，防止修改时越界 diff.resize(n+2, vector<long>(m+2)); // 4. 输入操作次数 q int q; cin >> q; // 5. 输入原矩阵的每个元素 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> matrix[i][j]; } } // 6. 根据原矩阵，生成初始差分数组 getDiff(); // 7. 处理 q 次矩形区间加法操作 while (q-->0) { int x1, y1, x2, y2, k; // 输入：矩形左上角(x1,y1)、右下角(x2,y2)、要加的值 k cin >> x1 >> y1 >> x2 >> y2 >> k; // 执行差分修改 getNum(x1, y1, x2, y2, k); } // 8. 对差分数组求前缀和，得到最终修改后的矩阵 getSum(); // 9. 输出最终答案（diff 数组此时就是答案矩阵） for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cout << diff[i][j] << " "; } cout << endl; } return 0; }

题目描述

某基金每日收益有正有负，求​连续一段日子的最大总收益​。

允许只选某一天，必须至少选一天。

输入格式

第一行 n

第二行 n 个整数

输出格式

最大连续和

同样用到前缀和，代码如下：

import java.util.*; public class Main{ public static void main(String[] args){ Scanner input=new Scanner(System.in); int n=input.nextInt(); long []arr=new long[n+1]; for(int i=1;i<=n;i++){ arr[i]=input.nextInt(); } long []brr=new long[n+1]; brr[0]=0; for(int j=1;j<=n;j++){ brr[j]=brr[j-1]+arr[j];//创建一个前缀和数组 } long Max=brr[1];//将最大值暂定为第二个元素 long Min=brr[0];//最小值为第一个元素 for(int i=1;i<=n;i++){ Max=Math.max(Max,brr[i]-Min);//更新最大值 Min=Math.min(Min,brr[i]);//不断选出前缀和数组中的最小值 }//这里的前缀和最小值和前缀和最大值不是单纯的，因为最大值要在最小值的前面 System.out.println(Max); input.close(); } }

其实1.Max 记录当前找到的最大子数组和。
2.Min 记录遍历到当前位置之前的最小前缀和。
3.brr[i] - Min 表示以 i 结尾的子数组中，最大的那一段和。
因为 brr[i] 是从头到 i 的总和，减去前面出现过的最小前缀和，就得到了一个“中间段”的最大和 这样可以保证 Max 始终是所有可能子数组和中的最大值。

如果只求顺序，不求连序，那么是改为洛谷的p3637

题目描述

这是一个简单的动规板子题。

给出一个由 n(n≤5000) 个不超过 106 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。

最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。

输入格式

第一行，一个整数 n，表示序列长度。

第二行有 n 个整数，表示这个序列。

输出格式

一个整数表示答案。

这个需要动态规划了，我也不是很熟，没有系统学过

#include <bits/stdc++.h> using namespace std; int main() { int n; cin>>n; vector<int> v; for (int i=0;i<n;i++) { int num; cin>>num; v.push_back(num); } vector<int>dp(n,1);//初始化状态全为1 int maxlen=1;//初始化为1，因为最短就是1 for (int i=0;i<n;i++) { for (int j=0;j<i;j++) { if (v[i]>v[j]) {//如果当前数字大于前面某个数字 说明可以接在它后面形成更长的上升序列 dp[i]=max(dp[i],dp[j]+1);//原来的 dp[i] 和 接在 j 后面的长度 dp[j]+1取更大的那个 } } maxlen=max(maxlen,dp[i]);更新全局的最大值 } cout<<maxlen<<endl; return 0; }

再看洛谷p2367:

题目背景

语文考试结束了，成绩还是一如既往地有问题。

题目描述

语文老师总是写错成绩，所以当她修改成绩的时候，总是累得不行。她总是要一遍遍地给某些同学增加分数，又要注意最低分是多少。你能帮帮她吗？

输入格式

第一行有两个整数 n，p，代表学生数与增加分数的次数。

第二行有 n 个数，a1​∼an​，代表各个学生的初始成绩。

接下来 p 行，每行有三个数，x，y，z，代表给第 x 个到第 y 个学生每人增加 z 分。

输出格式

输出仅一行，代表更改分数后，全班的最低分。

同样的我想道了循环暴力解，但数据量有过大的情况，我学习了差分后写了这个题，其实差分到原数组是进行了前缀和的操作，所以要在[x,y]加z分，其实可以对差分数组的brr[x]+z,brr[y+1]-z;

再前缀和得到原数组，从 x 开始，每个 brr[i] 都会多算一次 +z,到 y+1 再用 -z 抵消掉，后面就恢复正常，可以防止误加，只在区间加上一个数。

说明/提示

对于 40% 的数据，有 n≤pow(10,3)。

对于 60% 的数据，有 n≤pow(10,4)。

对于 80% 的数据，有 n≤pow(10,5)。

对于 100% 的数据，有 n≤5×pow(10,5)，p≤n，学生初始成绩 ≤100，z≤100。

#include <bits/stdc++.h> using namespace std; int main(){ int n,p; cin>>n>>p; int* arr=new int[n+1];//类似于C里的malloc开出一个空间，开n+1防止越界 for(int i=1;i<=n;i++){ cin>>arr[i]; } int *crr=new int[n+2];//从纯减的角度来说，在第2项才会有值的出现 crr[1]=arr[1]; for(int i=2;i<=n;i++){ crr[i]=arr[i]-arr[i-1]; } while(p-->0){ int x,y,z; cin>>x>>y>>z; crr[x]+=z; crr[y+1]-=z; arr[0]=0; } for(int i=1;i<=n;i++){ arr[i]=arr[i-1]+crr[i];//差分后在前缀和得到原数组 } sort(arr+1,arr+n+1);//排序时注意区间，我们的原数组从1开始初始化的。 cout<<arr[1]<<endl; }

洛谷p1567

题目描述

炎热的夏日，KC 非常的不爽。他宁可忍受北极的寒冷，也不愿忍受厦门的夏天。最近，他开始研究天气的变化。他希望用研究的结果预测未来的天气。

经历千辛万苦，他收集了连续 N(1≤N≤106) 天的最高气温数据。

现在，他想知道最高气温一直上升的最长连续天数。

输入格式

第 1 行：一个整数 N 。1≤N≤pow(10,6)

第 2 行：N个空格隔开的整数，表示连续 N 天的最高气温。0≤ 最高气温 ≤pow(10,9)。

输出格式

1 行：一个整数，表示最高气温一直上升的最长连续天数。

在没学滑动窗口之前我并没有什么思路，而这个题是一个最简单的滑动窗口，也可以是一个动态标记maxlen的过程。

#include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> v;//开创一个空间 for(int i=0;i<n;i++){ int num; cin>>num; v.push_back(num); } int count=1;//初始化天数为1 int Max=1;//初始化的最大值就是count for(int i=0;i<n;i++){ if(v[i+1]>v[i]){ count++;//当大于时，我去++天数 }else{ count=1;//如果严格递增断了，就重置count } Max=max(Max,count);//更新我们的最大天数 } cout<<Max; return 0; }

洛谷p1614

题目背景

（本道题目隐藏了两首歌名，找找看哪~~~）

《爱与愁的故事第一弹·heartache》第一章。

《我为歌狂》当中伍思凯神曲《舞月光》居然没赢给萨顶顶，爱与愁大神心痛啊~~~而且最近还有一些令人伤心的事情，都让人心痛（最近真的很烦哈)……

题目描述

最近有 n 个不爽的事，每句话都有一个正整数刺痛值（心理承受力极差）。爱与愁大神想知道连续 m 个刺痛值的和的最小值是多少，但是由于业务繁忙，爱与愁大神只好请你编个程序告诉他。

输入格式

第一行有两个用空格隔开的整数，分别代表 n 和 m。

第 2 到第 (n+1) 行，每行一个整数，第 (i+1) 行的整数 ai​ 代表第 i 件事的刺痛值 ai​。

输出格式

输出一行一个整数，表示连续 m 个刺痛值的和的最小值是多少。

这也是以个滑动窗口的题，我朋友在写的时候，用了双重循环标记，也是可以过，但数据量更大其实在我学习了后，就用了滑动窗口了。

#include <bits/stdc++.h> using namespace std; int main(){ int n,m; cin>>n>>m; vector<int> v;//开容器储存 for(int i=0;i<n;i++){ int num; cin>>num; v.push_back(num); } int current=0; for(int i=0;i<m;i++){ current+=v[i];//我们可以现标记前0~m-1个数的和 } int min=current;//将最小值暂定为它 for(int i=m;i<n;i++){ current=current-v[i-m]+v[i];在前面吐出一个元素，向后面容纳进一个元素，相当于我们的窗口在向后移动。 if(current<min){ min=current;//不断更新最小值 } } cout<<min<<endl; return 0; }

在听了左神的课，我接触到了这个题

左神的思路很清析，如果代码全写的话：

#include <bits/stdc++.h> using namespace std; int main() { int n,target; cin>>n>> target; vector<int> v; for (int i=0;i<n;i++) { int num; cin>>num; v.push_back(num); } int left=0; int sum=0; int minlen=INT_MAX; for (int right=0;right<n;right++) { sum+=v[right];//先不断加和右☞针，的元素 while (sum-v[left]>=target) {但它减去左☞针的元素后还能大于target，那么我们吐出这个元素，同时随着right的移动，右边的内容还在加和进来 sum-=v[left++]; } if (sum>=target) {//只要它大于等于target，更新minlen minlen=min(minlen,right-left+1);//数组从0开始，所以要加1 } } if (minlen==INT_MAX) { cout<<"0"; }else { cout<<minlen; }//可以用三目运算符的 return 0; }

引用：洛谷P5788(单调栈）

题目描述

给出项数为 n 的整数数列 a1…n​。

定义函数 f(i) 代表数列中第 i 个元素之后第一个大于 ai​ 的元素的下标，即 f(i)=mini<j≤n,aj​>ai​​{j}。若不存在，则 f(i)=0。

试求出 f(1…n)。

输入格式

第一行一个正整数 n。

第二行 n 个正整数 a1…n​。

输出格式

一行 n 个整数表示 f(1),f(2),…,f(n) 的值。

#include <bits/stdc++.h> using namespace std; const long N = 10000010; // 数据最大范围（1000万） int arr[N]; // 存储原始数组 int Mystack[N]; // 单调栈：存储数组下标 int ans[N]; // 存储答案：每个元素右侧第一个更大数的下标 int r, n; // r：栈顶指针；n：数组长度 // 单调栈核心函数：求每个数右侧第一个比它大的数的下标 void compute() { r = 0; // 栈初始化，栈为空 int cur; // 从左到右遍历每个元素 for (int i = 1; i <= n; i++) { // 栈不为空 且 栈顶元素 < 当前元素 // 说明当前元素 i 就是栈顶元素的「右侧第一个更大数」 while (r > 0 && arr[Mystack[r - 1]] < arr[i]) { cur = Mystack[--r]; // 弹出栈顶下标 ans[cur] = i; // 记录答案：右侧更大数下标是 i } Mystack[r++] = i; // 当前下标入栈 } // 遍历结束后，栈中剩下的元素：没有更大的数 while (r > 0) { cur = Mystack[--r]; // 弹出 ans[cur] = 0; // 没有更大数，答案记为 0 } } int main() { // 加速 cin/cout 输入输出 ios::sync_with_stdio(false); cin.tie(nullptr); // 输入数组长度 cin >> n; // 输入数组元素（从 1 开始存） for (int i = 1; i <= n; i++) { cin >> arr[i]; } // 单调栈计算答案 compute(); // 输出答案 for (int i = 1; i <= n; i++) { cout << ans[i] << " "; } return 0; }

其实这个题可以用upper_bound来写：

#include <bits/stdc++.h> using namespace std; const int N = 10000010; int a[N], ans[N], n; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++){ cin >> a[i]; } vector<int> v; for (int i = n; i >= 1; i--) { // 用 upper_bound 找第一个更大的 auto it = upper_bound(v.begin(), v.end(), a[i], greater<int>()); // 记录答案 ans[i] = it == v.end() ? 0 : *it; // 插入当前下标，保持序列有序 v.insert(it, i); } for (int i = 1; i <= n; i++) { cout << ans[i] << ' '; } return 0; }

有很多是没有掌握的，我记录典型题，就是要总解思路，当没有思路的时候，我就回来看我看我写过的代码（时间一久确实会忘），我的水平不够，希望看客老爷多提建议，我接下来怎么走过算法的苦海，谢谢