acwing算法提高之数据结构-爱代码爱编程
目录 1 专题介绍2 训练 1 专题介绍 本专题用来汇总使用树状数组算法求解的题目。 应用场景：给你长度为n的数组nums，可以改变第i个数的大小，求数组下标区间[left, right]内的前缀
5396. 棋盘 差分-爱代码爱编程
#include<iostream> using namespace std; const int N = 2010; int b[N][N]; int n, m; void insert(int x1, int y1, int x2, int y2) { b[x1][y1] ++; b[x1][y2 + 1] --;
acwing 788. 逆序对的数量——算法基础课题解-爱代码爱编程
AcWing 788. 逆序对的数量 题目描述 给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。 逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j且 a[i]>a[j]
acwing算法提高之图论-爱代码爱编程
目录 1 介绍2 训练 1 介绍 本专题用来记录使用。。。。 2 训练 题目1：1137选择最佳线路 C++代码如下， #include <iostream> #include
acwing算法提高之图论-爱代码爱编程
目录 1 介绍2 训练 1 介绍 本专题用来记录使用spfa算法来求负环的题目。 2 训练 题目1：904虫洞 C++代码如下， #include <cstring> #incl
acwing算法基础之搜索与图论-爱代码爱编程
目录 1 基础知识2 模板3 工程化 1 基础知识 对于单源最短路问题，且存在负权重的边时，使用bellman-ford算法来进行求解。但，如果图中存在负权环，那该最短路问题可能无解（如果最短路径上
acwing算法基础之搜索与图论-爱代码爱编程
目录 1 基础知识2 模板3 工程化 1 基础知识 存在负权边时，使用spfa算法来求解最短路问题，它的时间复杂度为O(m)。 spfa算法求最短路问题的关键步骤： 初始化距离数组dist为正无
acwing算法基础之搜索与图论-爱代码爱编程
目录 1 基础知识2 模板3 工程化 1 基础知识 假设有n个结点，m条边（边的长度或者权重不一致），最短路问题的分类及求解方法如下： 1 单源最短路问题，例如求结点1到结点n的最短距离。 1.1
acwing算法基础之搜索与图论-爱代码爱编程
目录 1 基础知识2 模板3 工程化 1 基础知识 floyd算法的时间复杂度为O(n^3)，它用来解决多源最短路问题。它的原理是基于动态规划。 floyd算法的关键步骤： k从1到n。i从1到
acwing算法提高之图论-爱代码爱编程
目录 1 介绍2 训练 1 介绍 本专题介绍使用floyd算法求解的题目。 使用floyd算法，可以求解如下问题： 最短路。传递闭包。找图中的距离总和最小的环路。求恰好经过k条边的最短路。 f
acwing算法提高之图论-爱代码爱编程
目录 1 介绍2 训练 1 介绍 本专题用来记录使用最小生成树算法（prim或kruskal）解决的扩展题目。 2 训练 题目1：1146新的开始 C++代码如下， #include <
0507滑动窗口+子矩阵_4964. 子矩阵-爱代码爱编程
154.滑动窗口 给定一个大小为 n≤106 的数组。 有一个大小为 k的滑动窗口，它从数组的最左边移动到最右边。 你只能在窗口中看到 k个数字。 每次滑动窗口向右移动一个位置。 以下是一个例子： 该数组为 [1
acwing算法提高之图论-爱代码爱编程
目录 1 介绍2 训练 1 介绍 本专题用来介绍使用最短路算法（spfa或dijkstra）与其它算法（dfs等等）结合起来解题。 2 训练 题目1：1135新年好 C++代码如下， //版
acwing算法提高之图论-爱代码爱编程
目录 1 介绍2 训练 1 介绍 本博客用来记录使用dijkstra算法或spfa算法求解最短路问题的题目。 2 训练 题目1：1129热浪 C++代码如下， #include <io
acwing 796. 子矩阵的和-爱代码爱编程
这个题的重点是仿照一维的数组，所以a[N][N]也是从1索引开始的。画个图举个例子就非常清晰了 之所以不好理解是因为没画格子，一个格子代表一个点，就很好理解了。 java代码： import java.io.*; public class Main{ static int N = 1010; static int[][] ar
acwing算法基础之数学知识-爱代码爱编程
目录 1 基础知识2 模板3 工程化 1 基础知识 题目：给定n个0和n个1，它们将按照某种顺序排成长度为2n的序列，求它们能排成的所有序列中，能够满足任意前缀序列中0的个数都不少于1的个数的序列有
acwing算法提高之搜索-爱代码爱编程
目录 1 专题说明2 训练 1 专题说明 本专题用来计算使用多源BFS和双端队列BFS求解的题目。 2 训练 题目1：173矩阵距离 考点：多源bfs C++代码如下， #include
796. 子矩阵的和-爱代码爱编程
Problem: 796. 子矩阵的和 文章目录 思路解题方法复杂度Code 思路 这是一个二维前缀和的问题。二维前缀和的主要思想是预处理出一个二维数组，使得每个位置(i, j)上
797. 差分-爱代码爱编程
Problem: 797. 差分 文章目录 思路解题方法复杂度Code 思路 这是一个差分数组的问题。差分数组的主要适用场景是频繁对原始数组的某一个区间进行增减操作。这种操作是区间
acwing 103. 电影（map、pair连用or离散化）-爱代码爱编程
题目 方法一（map+pair） 其实上面这么长巴拉巴拉就是在说 首先，每个科学家会的语言都不同。但是呢每部电影的字幕和语言是不一样的（字幕和语言一定不相同） 要求找到一部电影使得在场能听懂的科学家最多（如果存在两部及以上的电影的语言听懂人数相同的话，再去查找更多能看懂字幕的那部电影） 思路分析