行业知识
Acwing算法基础课学习笔记
Acwing学习笔记
- 第一章 基础算法
- 快速排序
- 归并排序
- 二分查找
- 前缀和与差分
- 差分
- 位运算
- 离散化
- 第二章 数据结构
- 单链表
- 双链表
- 栈
- 队列
- 单调栈
- 单调队列
- KMP算法
- Trie
- 并查集
- 堆
- 哈希表
- 第三章 搜索与图论
- DFS
- BFS
- 树与图的深度优先遍历
- 树与图的广度优先遍历
- 拓扑排序
- 图论
- 朴素dijkstra
- 堆优化版dijkstra
- bellman-ford
- spfa(求最短路)
- spfa(判断负环)
- Floyd
- 最小生成树
- Prim求最小生成树
- Kruskal 求最小生成树
- 二分图
- 染色法判断二分图
- 二分图最大匹配
- 第四章 数学知识
- 质数
- 第五章 动态规划
- 背包问题
- 01背包问题
- 第六章 贪心
- 区间问题：
- Hufman树：
- 排序不等式 :
- 绝对值不等式:
- 推公式:
第一章 基础算法
快速排序
- AcWing 785. 快速排序
给定你一个长度为 n 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼ 1 0 9 10^9 109 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围：1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
解析：
- 找到一个值x作为划分点，这个值可以是q[l]，q[r], q[l+r/2],也可以是区间的随机值
- 定义两个指针i,j，分别指向区间的两侧
- 当指针i指向的值q[i] > x时，指针i向右移动一位；指针j指向的值q[j] > x，指针j向左移动一位
- 对于任意时刻，都存在q[l,i] 的值小于等于x，区间q[j,r]的值大于等于x
- 当i和j各找到一个不符合条件的值的时候，交换i,j指向的值
- 递归对两个子区间进行排序
代码：
class Quick_sort: def qs(self,nums,l,r): if l == r:return # 当区间为1时，退出递归 x = nums[l + r >> 1] # 选择一个用于划分区间的值 i = l - 1 # 将左指针指向l的左侧 j = r + 1 # 将右指针指向r的右侧 while i x: j -= 1 # 当j指向的值不大于x的时候，停止循环 if i = x和nums[j] > 1] # 2.如果选择[l,i-1][i,r]时，x的取值就不能包含左端点；x = nums[l + r + 1 >> 1] self.qs(nums,l,j) self.qs(nums,j+1,r) def main(self): n = int(input()) self.line = list(map(int,input().split())) self.qs(self.line,0,n-1) for i in self.line: print(i, end=' ')if __name__ == '__main__': quicksort = Quick_sort() quicksort.main()
- AcWing 786. 第k个数
给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n 个整数（所有整数均在 1∼ 1 0 9 10^9 109 范围内），表示整数数列。
输出格式
输出一个整数，表示数列的第 k 小数。
数据范围
1≤n≤100000,
1≤k≤n
输入样例：
5 3
2 4 1 5 3
输出样例：
3
解析：
- 找到一个值x作为划分点，这个值可以是q[l]，q[r], q[l+r/2],也可以是区间的随机值
- 定义两个指针i,j，分别指向区间的两侧
- 当指针i指向的值q[i] > x时，指针i向右移动一位；指针j指向的值q[j] > x，指针j向左移动一位
- 对于任意时刻，都存在q[l,i] 的值小于等于x，区间q[j,r]的值大于等于x
- 当i和j各找到一个不符合条件的值的时候，交换i,j指向的值
- 计算左区间的长度：sl = j - l + 1 (或者：l = i - l)
- 如果k小于等于sl,则第k小的数在左区间，递归处理左区间即可；反之递归处理右区间
class Quickcheck: def quickcheck(self,l,r,k): if l == r:return self.nums[l] # 当区间只剩下一个数的时候，这个数就是第k小的数 x = self.nums[l + r >> 1] # 选取任意一个值作为分界点，小于这个值的点划分到左区间，大于这个值的点划分到右区间 i,j = l-1,r+1 while i x:j -= 1 if i = k: return self.quickcheck(l,j,k) else:return self.quickcheck(j+1,r,k-sl) def main(self): n,k = map(int,input().split()) self.nums = list(map(int,input().split())) print(self.quickcheck(0,n-1,k))if __name__ == '__main__': quickcheck = Quickcheck() quickcheck.main()
归并排序
- AcWing 787. 归并排序
给定你一个长度为 n 的整数数列。请你使用归并排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1 ∼ 1 0 9 1∼10^9 1∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
解析：
- 找到区间的中点mid = l + r >> 1
- 对左右区间进行递归排序
- 定义两个指针i,j，分别指向左右区间的起点
- 对两个区间的每个值进行比较大小，需要定义一个额外的结果数组，用来存放排序后的值
- 当i指向的值小于j指向的值，就将i指向的值加入到结果数组中，并将指针i向后移动一位
- 当j指向的值小于等于i指向的值，就将j指向的值加入到结果数组中，并将指针j想左移动一位
- 对于任意时刻，指针j指向的值都满足大于等于i指向的值
- 判断i和j是否移动到子数组的末尾，如果没有移动到末尾，则说明子数组中存在剩余元素，直接加入到结果列表中即可
class Mergesort: def mergesort(self,nums): if len(nums) == 1:return # 当区间长度为1时直接返回 mid = len(nums) >> 1 # 获取区间的中点 L = nums[:mid] # 将当前区间以中点划分左右两个区间 R = nums[mid:] self.mergesort(L) # 对左右区间进行递归排序 self.mergesort(R) i = j = k = 0 # 定义三个指针，分别指向左区间、右区间、结果数组的起点 while i
- AcWing 788. 逆序对的数量
给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，
如果满足 ia[j]，则其为一个逆序对；否则不是。
输入格式
第一行包含整数 n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
1≤n≤100000，
数列中的元素的取值范围 [1, 1 0 9 10^9 109]。
输入样例：
6
2 3 4 5 6 1
输出样例：
5
解析：
- 找到区间的中点mid，mid将整个区间划分为[:mid][mid:]两个区间
- 分别递归处理两个区间
- 当逆序对a,b同时出现在左区间或者右区间，直接在递归处理的时候加上返回值即可
- 当逆序对a,b一个在左区间一个在右区间，需要分情况讨论
- 当q[i] > q[j] 时，q[i]之后的所有数都对q[j]构成逆序对
class Reverse_order: def mergesort(self,nums): if len(nums) == 1:return 0 # 区间长度为1，这个区间就不存在逆序对 mid = len(nums) >> 1 left = nums[:mid] # mid将原始区间划分为左右两个子区间 right = nums[mid:] res = 0 res += self.mergesort(left) # 递归处理左右区间 res += self.mergesort(right) i = j = k = 0 while i
二分查找
- AcWing 789. 数的范围
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 n 和 q，表示数组长度和询问个数。
第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。
接下来 q 行，每行包含一个整数 k，表示一个询问元素。
输出格式
共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
输入样例：
6 3
1 2 2 3 3 4
3
4
5
输出样例：
3 4
5 5
-1 -1
思路：
能够进行二分的充要条件是，区间存在二段性（不一定是单调性）
- 找到区间的中点mid
- 判断目标值落在哪个区间，更新区间的端点为目标区间，这样每次缩小区间长度为原来的一半
class Binary_search: def binarysearch(self,nums,target): """ 找到第一个大于等于目标值的索引值 :param nums: :param target: :return: """ l,r = 0,len(nums) - 1 while l > 1 if nums[mid] >= target:r = mid else:l = mid + 1 return l def binarysearch2(self,nums,target): """ 找到第一个小于等于目标值的索引值 :param nums: :param target: :return: """ l,r = 0,len(nums) - 1 while l > 1 if nums[mid] >1 else:r = mid - 1 return r def main(self): n,q = map(int,input().split()) nums = list(map(int,input().split())) for i in range(q): k = int(input()) left = self.binarysearch(nums,k) right = self.binarysearch2(nums,k) if nums[left] != k:print(-1,-1) else:print(left,right)if __name__ == '__main__': binarysearch = Binary_search() binarysearch.main()
前缀和与差分
AcWing 795. 前缀和（一维前缀和）
输入一个长度为 n 的整数序列。
接下来再输入 m 个询问，每个询问输入一对 l,r。
对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。
输入格式
第一行包含两个整数 n 和 m。
第二行包含 n 个整数，表示整数数列。
接下来 m 行，每行包含两个整数 l 和 r，表示一个询问的区间范围。
输出格式
共 m 行，每行输出一个询问的结果。
数据范围
1≤l≤r≤n,
1≤n,m≤100000,
−1000≤数列中元素的值≤1000
输入样例：
5 3
2 1 3 6 4
1 2
1 3
2 4
输出样例：
3
6
10
class Prefixsum: def main(self): n,m = map(int,input().split()) nums = list(map(int,input().split())) nums = [0] + nums for i in range(1,n+1): nums[i] += nums[i-1] for j in range(m): l,r = map(int,input().split()) print(nums[r] - nums[l-1])if __name__ == '__main__': perfixsum = Prefixsum() perfixsum.main()
AcWing 796. 子矩阵的和（二维前缀和）
输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，
每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 n，m，q。
接下来 n 行，每行包含 m 个整数，表示整数矩阵。
接下来 q 行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。
输出格式
共 q 行，每行输出一个询问的结果。
数据范围
1≤n,m≤1000,
1≤q≤200000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000
输入样例：
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
输出样例：
17
27
21
解析：
- 二维前缀和： p r e f i x [ x 3 , y 3 ] = p r e f i x [ x 2 , y 3 ] + p r e f i x [ x 3 , y 2 ] − p r e f i x [ x 2 , y 2 ] + n u m s [ x 3 , y 3 ] prefix[x3,y3] = prefix[x2,y3] + prefix[x3,y2] - prefix[x2,y2] + nums[x3,y3] prefix[x3,y3]=prefix[x2,y3]+prefix[x3,y2]−prefix[x2,y2]+nums[x3,y3]
- 二维区间和： p r e f i x [ x 2 , y 2 , x 4 , y 4 ] = p r e f i x [ x 4 , y 4 ] − p r e f i x [ x 4 , y 1 ] − p r e f i x [ x 1 ] [ y 4 ] + p r e f i x [ x 1 , y 1 ] prefix[x2,y2,x4,y4] = prefix[x4,y4] - prefix[x4,y1] - prefix[x1][y4] + prefix[x1,y1] prefix[x2,y2,x4,y4]=prefix[x4,y4]−prefix[x4,y1]−prefix[x1][y4]+prefix[x1,y1]
class Prefixsum_arr: def __init__(self): N = 1010 self.prefix = [[0] * N for _ in range(N)] def prefixsum(self,nums,n,m): for i in range(1,n+1): for j in range(1,m+1): self.prefix[i][j] = self.prefix[i-1][j] + self.prefix[i][j-1] - self.prefix[i-1][j-1] + nums[i-1][j-1] def main(self): n,m,q = map(int,input().split()) nums = [] for i in range(n): line = list(map(int,input().split())) nums.append(line) self.prefixsum(nums,n,m) for j in range(q): x1,y1,x2,y2 = map(int,input().split()) res = self.prefix[x2][y2] - self.prefix[x2][y1-1] - self.prefix[x1-1][y2] + self.prefix[x1-1][y1-1] print(res)if __name__ == '__main__': prefixsum = Prefixsum_arr() prefixsum.main()
差分
AcWing 797. 差分(一维差分)
输入一个长度为 n 的整数序列。
接下来输入 m 个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r] 之间的每个数加上 c。
请你输出进行完所有操作后的序列。
输入格式
第一行包含两个整数 n 和 m。
第二行包含 n 个整数，表示整数序列。
接下来 m 行，每行包含三个整数 l，r，c，表示一个操作。
输出格式
共一行，包含 n 个整数，表示最终序列。
数据范围
1≤n,m≤100000,
1≤l≤r≤n,
−1000≤c≤1000,
−1000≤整数序列中元素的值≤1000
输入样例：
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1
输出样例：
3 4 5 3 4 2
解析：
差分：可以看做是前缀和的逆运算，
给定一个原数组a:a[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数组的差分数组
b数组构造方式如下：
a[0] = 0;b[1] = a[1] - a[0];b[2] = a[2] - a[1];b[3] = a[3] - a[2];...b[n] = a[n] - a[n-1];
- 差分数组的作用：
- 给定区间[l,r]，让我们把a数组中的[l,r]区间中的每一个数都加上c,暴力做法需要对区间进行遍历，再对区间[l,r]增加一个c
- 差分数组，只需要在s[l] += c,s[r+1] -= c，就可使得原数组在区间[l,r]上增加c
class Differenc: def __init__(self): N = 100010 self.nums = [0] * N # 差分数组 def insert(self,l,r,c): # 在差分数组区间l加上c，区间r+1减去c，使得原数组在区间[l,r]内增加c self.nums[l] += c self.nums[r+1] -= c def main(self): n,m = map(int,input().split()) nums = list(map(int,input().split())) for i in range(1,n+1): self.insert(i,i,nums[i-1]) # 求差分数组 for i in range(m): l,r,c = map(int,input().split()) # 将差分数组的l位置增加c，r+1位置减去c self.nums[l] += c self.nums[r+1] -= c for i in range(1,n+1): # 对差分数组求一遍前缀和，得到原数组 self.nums[i] += self.nums[i-1] print(self.nums[i],end=' ')if __name__ == '__main__': difference = Differenc() difference.main()
AcWing 798. 差分矩阵(二维差分)
输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。每个操作都要将选中的子矩阵中的每个元素的值加上 c。
请你将进行完所有操作后的矩阵输出。
输入格式
第一行包含整数 n,m,q。
接下来 n 行，每行包含 m 个整数，表示整数矩阵。
接下来 q 行，每行包含 5 个整数 x1,y1,x2,y2,c，表示一个操作。
输出格式
共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。
数据范围
1≤n,m≤1000,
1≤q≤100000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤c≤1000,
−1000≤矩阵内元素的值≤1000
输入样例：
3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1
输出样例：
2 3 4 1
4 3 4 1
2 2 2 2
解析：
与一维差分数组类似，要使得特定区间a[x1,y1,x2,y2]内的值增加c，我们只需要在差分数组b[x1,y1] 加上c，b[x1,y2+1]减去c，b[x2+1,y1]减去c，b[x2+1,y2+1]加上c，再对差分数组求一遍前缀和，就可得到原数组的区间a[x1,y1,x2,y2]内的值增加c
b[x1][y1] += c;b[x1][y2+1] -= c;b[x2+1][y1] -= c;b[x2+1][y2+1] += c;
class Difference2: def __init__(self): N = 1010 self.arr = [[0] * N for _ in range(N)] # 差分数组 def insert(self,x1,y1,x2,y2,c): self.arr[x1][y1] += c self.arr[x1][y2+1] -= c self.arr[x2+1][y1] -= c self.arr[x2+1][y2+1] += c def main(self): n, m, q = map(int,input().split()) for i in range(1,n+1): nums = list(map(int,input().split())) nums = [0] + nums for j in range(1,m+1): self.insert(i,j,i,j,nums[j]) for i in range(q): x1, y1, x2, y2, c = map(int,input().split()) self.insert(x1,y1,x2,y2,c) for i in range(1,n+1): for j in range(1,m+1): # 求二维数组的前缀和 self.arr[i][j] += (self.arr[i-1][j] + self.arr[i][j-1] - self.arr[i-1][j-1]) print(self.arr[i][j],end=' ') print()if __name__ == '__main__': difference2 = Difference2() difference2.main()
AcWing 799. 最长连续不重复子序列
给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式
第一行包含整数 n。
第二行包含 n 个整数（均在 0∼105 范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围
1 ≤ n ≤ 1 0 5 1≤n≤10^5 1≤n≤105
输入样例：
5
1 2 2 3 5
输出样例：
3
思路：
- 定义两个指针i,j，i指针往右移动
- 开一个数组count用于存放每个数出现的频次，以数组中每个数的值为索引，数组count中的值为这个数出现的频次
- 当这个数的频次大于1，就说明当前数出现了重复次数。并且出现重复次数是因为当前i指向的元素的加入
- 向右移动指针j，直到频次大于1的元素的频次降到1
class Double_pointer: def __init__(self): N = 100010 self.nums = [0] * N def main(self): n = int(input()) nums = list(map(int,input().split())) j = res = 0 for i in range(n): self.nums[nums[i]] += 1 while self.nums[nums[i]] > 1: self.nums[nums[j]] -= 1 j += 1 res = max(res,i - j + 1) print(res)if __name__ == '__main__': double = Double_pointer() double.main()
AcWing 800. 数组元素的目标和
给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。数组下标从 0 开始。
请你求出满足 A[i]+B[j]=x 的数对 (i,j)。
数据保证有唯一解。
输入格式
第一行包含三个整数 n,m,x，分别表示 A 的长度，B 的长度以及目标值 x。
第二行包含 n 个整数，表示数组 A。
第三行包含 m 个整数，表示数组 B。
输出格式
共一行，包含两个整数 i 和 j。
数据范围
数组长度不超过 1 0 5 10^5 105。
同一数组内元素各不相同。
1 ≤ 数组元素 ≤ 1 0 9 1≤数组元素≤10^9 1≤数组元素≤109
输入样例：
4 5 6
1 2 4 7
3 4 6 8 9
输出样例：
1 1
解析：
- 由于两个数组都是升序排列，可以定义两个指针i,j，指针i指向第一个数组的首位，j指向第二个数组的末尾
- 当i和j指向的两个数的和大于目标值，就将j向左移动一位
- 当i和j指向的两个数的和小于目标值，就将i向右移动一位
- 当i和j指向的两个数的和等于目标值，返回当前的i和j的值并结束循环
class Double_pointer2: def main(self): n, m, target = map(int,input().split()) nums1 = list(map(int,input().split())) nums2 = list(map(int,input().split())) i = 0 j = m - 1 while i = 0: if nums1[i] + nums2[j] == target: print(i,j) break elif nums1[i] + nums2[j] > target: j -= 1 else:i += 1if __name__ == '__main__': double2 = Double_pointer2() double2.main()
AcWing 2816. 判断子序列
给定一个长度为 n 的整数序列 a 1 , a 2 , … , a n a_1,a_2,…,a_n a1,a2,…,an以及一个长度为 m 的整数序列 b 1 , b 2 , … , b m b_1,b_2,…,b_m b1,b2,…,bm。
请你判断 a 序列是否为 b 序列的子序列。
子序列指序列的一部分项按原有次序排列而得的序列，例如序列 a 1 , a 3 , a 5 {a_1,a_3,a_5} a1,a3,a5 是序列 a 1 , a 2 , a 3 , a 4 , a 5 {a_1,a_2,a_3,a_4,a_5} a1,a2,a3,a4,a5的一个子序列。
输入格式
第一行包含两个整数 n,m。
第二行包含 n 个整数，表示 a 1 , a 2 , … , a n a_1,a_2,…,a_n a1,a2,…,an。
第三行包含 m 个整数，表示 b 1 , b 2 , … , b m b_1,b_2,…,b_m b1,b2,…,bm。
输出格式
如果 a 序列是 b 序列的子序列，输出一行 Yes。
否则，输出 No。
数据范围
1 ≤ n ≤ m ≤ 1 0 5 , 1≤n≤m≤10^5, 1≤n≤m≤105,
− 1 0 9 ≤ a i , b i ≤ 1 0 9 −10^9≤a_i,b_i≤10^9 −109≤ai,bi≤109
输入样例：
3 5
1 3 5
1 2 3 4 5
输出样例：
Yes
解析：
- 定义两个指针i,j，分别指向两个数组的首位置
- 如果指针j指向的值与指针i指向的值相等，就将指针i向后移动一位
- 当j移动到数组末尾时，i的值等于子串长度时，匹配成功，否则匹配失败
class Double_pointer: def main(self): n, m = map(int,input().split()) nums1 = list(map(int,input().split())) nums2 = list(map(int,input().split())) i = 0 for j in range(m): while i
位运算
AcWing 801. 二进制中1的个数
给定一个长度为 n 的数列，请你求出数列中每个数的二进制表示中 1 的个数。
输入格式
第一行包含整数 n。
第二行包含 n 个整数，表示整个数列。
输出格式
共一行，包含 n 个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中 1 的个数。
数据范围
1≤n≤100000,
0 ≤ 数列中元素的值 ≤ 1 0 9 0≤数列中元素的值≤10^9 0≤数列中元素的值≤109
输入样例：
5
1 2 3 4 5
输出样例：
1 1 2 1 2
解析：
算法1：lowbit()
原码(x)： 十进制数据的二进制表现形式就是原码，原码最左边的一个数字就是符号位，0为正，1为负。
反码(~x)：正数的反码是其本身（等于原码），负数的反码是符号位保持不变，其余位取反。
补码(-x)：正数的补码是其本身，负数的补码等于其反码 +1。因为反码不能解决负数跨零（类似于 -6 + 7）的问题，
所以补码出现了。
- lowbit计算二进制表示中的最低位的1的位置
原理：原码 & 补码 ，例如十进制12，原码为:0b1100;反码为：0b0100(即0b0011 + 1)
0b1100 & 0b0100 = 0b0100
- 计算x中1的个数，当x不为0时，每次循环减去一个lowbit(x)，循环的次数就是x的二进制表示中1的个数
class Count1: def lowbit(self,x): """ 获取x的二进制中最低位1 :param x: :return: """ return x & -x def main(self): n = int(input()) nums = list(map(int,input().split())) for i in range(n): res = 0 k = nums[i] while k: k -= self.lowbit(k) res += 1 print(res,end=' ')if __name__ == '__main__': count1 = Count1() count1.main()
class Count2: def main(self): n = int(input()) nums = list(map(int,input().split())) for i in range(n): res = 0 k = nums[i] while k: res += k & 1 k >>= 1 print(res,end=' ')if __name__ == '__main__': count2 = Count2() count2.main()
离散化
AcWing 802. 区间和
假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。
现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。
接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含两个整数 x 和 c。
再接下来 m 行，每行包含两个整数 l 和 r。
输出格式
共 m 行，每行输出一个询问中所求的区间内数字和。
数据范围
− 1 0 9 ≤ x ≤ 1 0 9 , −10^9≤x≤10^9, −109≤x≤109,
1 ≤ n , m ≤ 1 0 5 , 1≤n,m≤10^5, 1≤n,m≤105,
− 1 0 9 ≤ l ≤ r ≤ 1 0 9 , −10^9≤l≤r≤10^9, −109≤l≤r≤109,
− 10000 ≤ c ≤ 10000 −10000≤c≤10000 −10000≤c≤10000
输入样例：
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例：
8
0
5
解析：
- 将所有的插入和查询操作的索引值全部加入到一个索引数组中
- 对索引数组进行排序并去重，得到的新数组就是离散化后的数组
- 将插入操作和查询操作用一个二维数组存储，add数组存储的是每个插入操作的原始索引值和插入的数值，query数组存储的是每个查询操作的原始[l,r]值
- 开一个新的数组用来存放离散化后的值，这个值插入的位置就是离散化后的索引值对应的位置
- 查询操作处理类似，将查询操作的原始索引值转换为新的索引值，利用新的索引值在新的数组中去查找对应区间的值
- 离散化操作：由于离散化数组是排序去重的数组，存在单调性，可利用二分去查找大于等于当前值的第一个位置，查找出来的值可根据实际情况去确定是否需要做加1处理，这里由于是计算前缀和，前缀和的下标从1开始，所以这里将查询出来的下标直接加1
- 利用前缀和去计算区间和
class Discretization: def __init__(self): N = 300010 # 这里需要设置3倍空间，n次插入和m次查询的上界 self.add = [] self.query = [] self.alls_index = [] self.nums = [0] * N self.prefix = [0] * N def find(self,nums,x): """ 查找离散化后，新的索引值 :param nums:离散化后的数组 :param x:需要查询的索引值 :return: 离散化后对应的新的索引值 """ l = 0 r = len(nums) - 1 while l > 1 if nums[mid] >= x:r = mid else: l = mid + 1 return l + 1 # 由于计算的前缀和，所以索引需要从1开始，这里返回的索引值加上了1 def unique(self,nums): """ 对数组进行排序并去重 :param nums: 待排序去重的数组 :return: 排序去重后的数组 """ nums.sort() i = 1 for j in range(1,len(nums)): if nums[j] != nums[j-1]: nums[i] = nums[j] i += 1 return nums[:i] def main(self): n,m = map(int,input().split()) for i in range(n): x,c = map(int,input().split()) self.add.append([x,c]) self.alls_index.append(x) for j in range(m): l,r = map(int,input().split()) self.query.append([l,r]) self.alls_index.append(l) self.alls_index.append(r) # 对所有的索引数组进行排序并去重 index = self.unique(self.alls_index) # 处理插入操作，并将离散化后的值插入到新的数组nums中 for x,c in self.add: new_x = self.find(index,x) self.nums[new_x] += c # 求一遍前缀和 for i in range(1,len(index)+1): self.prefix[i] = self.prefix[i-1] + self.nums[i] # 处理离散化后的区间和查询操作 for l,r in self.query: new_l = self.find(index,l) new_r = self.find(index,r) print(self.prefix[new_r] - self.prefix[new_l-1])if __name__ == '__main__': discretization = Discretization() discretization.main()
AcWing 803. 区间合并
给定 n 个区间 [ l i , r i ] [l_i,r_i] [li,ri]，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：
[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含两个整数 l 和 r。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。
数据范围
1 ≤ n ≤ 100000 , 1≤n≤100000, 1≤n≤100000,
− 1 0 9 ≤ l i ≤ r i ≤ 1 0 9 −10^9≤l_i≤r_i≤10^9 −109≤li≤ri≤109
输入样例：
5
1 2
2 4
5 6
7 8
7 9
输出样例：
3
解析:
- 读取所有区间，对所有区间按左边界值进行从大到小排序
- 定义一个最小的边界值，来作为初始边界( e d = − 2 e 9 ed = -2e9 ed=−2e9)
- 依次遍历所有区间，当当前区间的左边界大于上一个区间的右边界时，说明两个区间不存在交点，就将当前区间加入到结果列表中
- 特判：如果ed未被更新过，说明区间为空
class Solution: def main(self): n = int(input()) zone = list() for i in range(n): line = list(map(int,input().split())) zone.append(line) zone.sort(key=lambda x:x[0]) # 定义一个初始右边界 ed = -2e9 res = [] for l,r in zone: if l > ed: # 如果当前区间的左端点小于上一个区间的右边界， # 则说明两个区间不存在相交，将当前区间加入到结果列表中 ed = r res.append([l,ed]) else: # 如果两个区间相交，就取较大的右边界值取更新新的右边界 ed = max(ed,r) if ed == -2e9:print(0) # 如果n=0，说明ed没有被更新过，直接返回0 else:print(len(res))if __name__ == '__main__': solution = Solution() solution.main()
第二章 数据结构
单链表
AcWing 826. 单链表
实现一个单链表，链表初始为空，支持三种操作：
向链表头插入一个数；删除第 k 个插入的数后面的数；在第 k 个插入的数后插入一个数。现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。
注意:
题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：
H x，表示向链表头插入一个数 x。
D k，表示删除第 k 个插入的数后面的数（当 k 为 0 时，表示删除头结点）。
I k x，表示在第 k 个插入的数后面插入一个数 x（此操作中 k 均大于 0）。
输出格式
共一行，将整个链表从头到尾输出。
数据范围
1≤M≤100000
所有操作保证合法。
输入样例：
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
输出样例：
6 4 6 5
- 模板（C++）
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点int head, e[N], ne[N], idx;// 初始化void init(){ head = -1; idx = 0;}// 在链表头插入一个数avoid insert(int a){ e[idx] = a, ne[idx] = head, head = idx ++ ;}// 将头结点删除，需要保证头结点存在void remove(){ head = ne[head];}- Python代码
class Solution: def __init__(self): N = 100010 self.e = [0] * N self.ne = [0] * N self.head = -1 self.idx = 1 def add_to_head(self,x): """ 在头结点后面插入一个数 head --> -1 head --> x --> -1 :param x: :return: """ self.e[self.idx] = x # 先存储需要插入的值 self.ne[self.idx] = self.head # 将当前节点的next指针指向头结点指向的节点 self.head = self.idx # 将头结点改向 self.idx += 1 # 将idx+1，说明当前节点已经被使用 def add_behind_k(self,k,x): """ 在第k个节点后插入 head --> x1 --> k --> -1 head --> x1 --> k --> x --> -1 :param k: :param x: :return: """ self.e[self.idx] = x # 先存储需要插入的节点的值 self.ne[self.idx] = self.ne[k] # 将当前节点的next指针指向节点k指向的节点 self.ne[k] = self.idx # 将节点k的指向改向 self.idx += 1 def remove_k(self,k): """ head --> x1 --> k --> x2 --> x3 --> -1 head --> x1 --> k --> x3 --> -1 :param k: :return: """ if k == 0:self.head = self.ne[self.head] # 如果k等于0，说明需要删除头结点 else:self.ne[k] = self.ne[self.ne[k]] # 删除节点k后面的节点就是将节点k的next指针指向next的next def main(self): M = int(input()) for i in range(M): line = input().split() if line[0] == "H": x = int(line[1]) self.add_to_head(x) elif line[0] == "I": k,x = int(line[1]),int(line[2]) self.add_behind_k(k,x) else: k = int(line[1]) self.remove_k(k)# 遍历链表，从链表的头结点开始遍历 idx = self.head while ~idx: # 如果idx等于-1，说明已经遍历到节点末尾，则跳出循环 print(self.e[idx],end=' ') idx = self.ne[idx] # 逐个移动节点if __name__ == '__main__': solution = Solution() solution.main()
双链表
AcWing 827. 双链表
实现一个双链表，双链表初始为空，支持 5 种操作：
在最左侧插入一个数；
在最右侧插入一个数；
将第 k 个插入的数删除；
在第 k 个插入的数左侧插入一个数；
在第 k 个插入的数右侧插入一个数
现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。
注意:
题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：
L x，表示在链表的最左端插入数 x。
R x，表示在链表的最右端插入数 x。
D k，表示将第 k 个插入的数删除。
IL k x，表示在第 k 个插入的数左侧插入一个数。
IR k x，表示在第 k 个插入的数右侧插入一个数。
输出格式
共一行，将整个链表从左到右输出。
数据范围
1≤M≤100000
所有操作保证合法。
输入样例：
10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2
输出样例：
8 7 7 3 2 9
- 模板（C++）
// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点int e[N], l[N], r[N], idx;// 初始化void init(){ //0是左端点，1是右端点 r[0] = 1, l[1] = 0; idx = 2;}// 在节点a的右边插入一个数xvoid insert(int a, int x){ e[idx] = x; l[idx] = a, r[idx] = r[a]; l[r[a]] = idx, r[a] = idx ++ ;}// 删除节点avoid remove(int a){ l[r[a]] = l[a]; r[l[a]] = r[a];}- Python代码
class Solution: def __init__(self): N = 100010 self.e = [0] * N self.left = [0] * N self.right = [0] * N self.left[1] = 0 # 初始化节点，节点0-->1; 0 0) // 判断栈是否为空，如果 tt > 0，则表示不为空{}- python代码
class Stack: def __init__(self): N = 100010 self.tt = -1 # 定义一个指针，指向-1 self.stack = [0] * N def push(self,x): self.tt += 1 # 先移动指针，再将值加入到栈中 self.stack[self.tt] = x def pop(self): self.tt -= 1 # 从栈顶弹出一个元素 def empty(self): if self.tt
AcWing 3302. 表达式求值
给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。
注意：
- 数据保证给定的表达式合法。
- 题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
- 题目保证表达式中所有数字均为正整数。
- 题目保证表达式在中间计算过程以及结果中，均不超过 2 31 − 1 2^{31−1} 231−1。
- 题目中的整除是指向 0 取整，也就是说对于大于 00 的结果向下取整，例如 5/3=1，对于小于 0 的结果向上取整，例如 5/(1−4)=−1。
- C++和Java中的整除默认是向零取整；Python中的整除//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。
输入格式
共一行，为给定表达式。
输出格式
共一行，为表达式的结果。
数据范围
表达式的长度不超过 1 0 5 10^5 105。
输入样例：
(2+2)*(1+1)
输出样例：
8
def cacl(nums,ops): """ :param nums: 数值栈，存放中缀表达式中的数值 :param ops: 运算符栈，存放中缀表达式中的运算符 :return: None """ b = nums.pop() # 栈中弹出的第一个元素为操作的第二个元素 a = nums.pop() # 栈中弹出的第二个元素为操作的第一个元素 c = ops.pop() # 弹出运算符 if c == "+":x = a + b elif c == "-":x = a - b elif c == "*": x = a * b else:x = int(a / b) nums.append(x) # 将运算结果添加到栈中def main(): weight = {'+':1,'-':1,'*':2,'/':2} # 定义运算符优先级权重 nums = [] # 定义一个栈存放数值 ops = [] # 定义一个栈存放运算符 s = input() i = 0 while i = weight[ch]): cacl(nums,ops) ops.append(ch) # 计算完成后将元算符入栈 i += 1 while len(ops): # 如果运算符栈不为空，循环遍历计算 cacl(nums,ops) print(nums[-1])main()队列
AcWing 829. 模拟队列
实现一个队列，队列初始为空，支持四种操作：
push x – 向队尾插入一个数 x；
pop – 从队头弹出一个数；
empty – 判断队列是否为空；
query – 查询队头元素。
现在要对队列进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。
输出格式
对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。
其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示队头元素的值。
数据范围
1 ≤ M ≤ 100000 , 1≤M≤100000, 1≤M≤100000,
1 ≤ x ≤ 1 0 9 , 1≤x≤10^9, 1≤x≤109,
所有操作保证合法。
输入样例：
10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6
输出样例：
NO
6
YES
4
- 模板（C++）
- 普通队列
int q[N], hh = 0, tt = -1; // hh 表示队头，tt表示队尾q[ ++ tt] = x; // 向队尾插入一个数 hh ++ ; // 从队头弹出一个数q[hh]; // 队头的值if (hh }} while (tt && check(stk[tt], i)) tt -- ; stk[ ++ tt] = i;} while (hh // 当j不为0时，i与j+1不匹配就将j回退 while (j && p[i] != p[j + 1]) j = ne[j]; // 匹配后就将j向后移动一位 if (p[i] == p[j + 1]) j ++ ; // 用next[i]记录当前j走到了哪里 ne[i] = j; } int p = 0; // 从根节点开始遍历 for (int i = 0; str[i]; i ++ ) { int u = str[i] - 'a'; if (!son[p][u]) son[p][u] = ++ idx; // 如果当前节点不存在就加入到trie树中 p = son[p][u]; // 插入完成后将节点p移动到当前节点 } cnt[p] ++ ; // 记录当前字符串的末尾位置}// 查询字符串出现的次数int query(char *str){ int p = 0; for (int i = 0; str[i]; i ++ ) { int u = str[i] - 'a'; if (!son[p][u]) return 0; // 如果当前字母不在trie树中就直接返回0 p = son[p][u]; } return cnt[p];} if (p[x] != x) { int t = find(p[x]); d[x] += d[p[x]]; // 路径压缩过程中不断维护当前节点到根节点的距离 p[x] = t; } return p[x];}p动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。/ppA 吃 B，B 吃 C，C 吃 A。/pp现有 N 个动物，以 1∼N 编号。/pp每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。/p p有人用两种说法对这 N 个动物所构成的食物链关系进行描述：/p p第一种说法是 1 X Y，表示 X 和 Y 是同类。/pp第二种说法是 2 X Y，表示 X 吃 Y。/p p此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。/p p当一句话满足下列三条之一时，这句话就是假话，否则就是真话。/p p当前的话与前面的某些真的话冲突，就是假话；/pp当前的话中 X 或 Y 比 N 大，就是假话；/pp当前的话表示 X 吃 X，就是假话。/pp你的任务是根据给定的 N 和 K 句话，输出假话的总数。/p p输入格式/pp第一行是两个整数 N 和 K，以一个空格分隔。/p p以下 K 行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中 D 表示说法的种类。/p p若 D=1，则表示 X 和 Y 是同类。/pp若 D=2，则表示 X 吃 Y。/p p输出格式/pp只有一个整数，表示假话的数目。/p p数据范围/pp1≤N≤50000,/pp0≤K≤100000/p p输入样例：/pp100 7/pp1 101 1/pp2 1 2/pp2 2 3/pp2 3 3/pp1 1 3/pp2 3 1/pp1 5 5/p p输出样例：/pp3/p pre class Solution: def __init__(self): N = 100010 self.p = [i for i in range(N)] self.dis = [0] * N # 存储每个节点到根节点的距离 def find(self,x): if x != self.p[x]: fx = self.find(self.p[x]) self.dis[x] += self.dis[self.p[x]] self.p[x] = fx return self.p[x] def main(self): n,k = map(int,input().split()) res = 0 for i in range(k): op,a,b = map(int,input().split()) if a n or b n:res += 1 else: fa = self.find(a) fb = self.find(b) if op == 1: # 性质1：a，b到根节点的距离同余3 # 如果a和b在同一个集合中，判断a和b到根的距离是否同余3 if fa == fb and (self.dis[a] - self.dis[b]) % 3: res += 1 elif fa != fb: self.p[fa] = fb self.dis[fa] = self.dis[b] - self.dis[a] else: if fa == fb and (self.dis[a] - self.dis[b] - 1) % 3: res += 1 elif fa != fb: self.p[fa] = fb self.dis[fa] = self.dis[b] - self.dis[a] + 1 # 节点合并的时候更新每个节点到根节点的距离 print(res)if __name__ == '__main__': solution = Solution() solution.main()/pre hr / h5堆/h5 hr / ulli堆的特点：小根堆：根节点小于等于它的子节点；大根堆：根节点大于等于它的子节点/lili堆的存储：可用一维数组存储堆，堆是一颗完全二叉树/lili手写小根堆的up(x)操作：如果当前节点的值小于根节点的值，就交换当前节点的值与根节点的值/lili手写小根堆的down(x)操作：如果当前节点的值大与它的子节点的值，就将当前节点的值与三个节点中最小的值交换/lili堆的几个常见操作：tabletheadtrth align="center"序号/thth align="center"操作/thth align="left"实现/th/tr/theadtbodytrtd align="center"1/tdtd align="center"插入一个数x/tdtd align="left"heap[++size] = x;up(size)/td/trtrtd align="center"2/tdtd align="center"求堆中的最小值/tdtd align="left"heap[1]/td/trtrtd align="center"3/tdtd align="center"删除堆中的最小值/tdtd align="left"heap[1] = heap[size];size --;down(1)/td/trtrtd align="center"4/tdtd align="center"删除堆中的任意一个元素/tdtd align="left"heap[k] = heap[size];size --;up(k);down(k)/td/trtrtd align="center"5/tdtd align="center"修改任意一个元素/tdtd align="left"heap[k] = x;up(k);down(k)/td/tr/tbody/table ulli删除堆中的一个元素，先将需要删除的元素与堆的末尾元素交换位置，再将堆的size–，执行一遍down和up操作；这里down和up操作至多只会执行一个hr / pAcWing 838. 堆排序/p p输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。/p p输入格式/pp第一行包含整数 n 和 m。/pp第二行包含 n 个整数，表示整数数列。/p p输出格式/pp共一行，包含 m 个整数，表示整数数列中前 m 小的数。/p p数据范围/pp 1 ≤ m ≤ n ≤ 1 0 5 ， 1≤m≤n≤10^5， 1≤m≤n≤105，/pp 1 ≤ 数列中元素 ≤ 1 0 9 1≤数列中元素≤10^9 1≤数列中元素≤109/p p输入样例：/pp5 3/pp4 5 1 3 2/p p输出样例：/pp1 2 3/p pre class Heap: def __init__(self): N = 100010 self.heap = [0] * N def down(self,x): """ :param x: :return: """ # 找到当前三个节点的最小值 mini = x # 如果存在左子节点，如果左子节点小于根节点的值，就将最小节点的索引记为左子结点 if x * 2 = self.idx and self.heap[mini] self.heap[x * 2]: mini = x * 2 if x * 2 + 1 = self.idx and self.heap[mini] self.heap[x * 2 + 1]: mini = x * 2 + 1 if x != mini: # 如果x不是最小节点，就进行交换 self.heap[mini],self.heap[x] = self.heap[x], self.heap[mini] # 交换后，节点x达到稳定状态 self.down(mini) # 递归堆原来最小的节点进行down def create(self,n): """ 建堆：从n/2位置开始建堆，可以在O(n)时间复杂度建堆 :param n: :return: """ cnt = n 1 for i in range(cnt,0,-1): self.down(i) # 对n/2 - 0的所有节点进行一遍down操作，得到的堆就是小根堆 def main(self): n,m = map(int,input().split()) nums = list(map(int,input().split())) for i in range(1,n+1): self.heap[i] = nums[i-1] self.idx = n self.create(self.idx) for j in range(m): res = self.heap[1] # 取出堆顶元素，堆顶元素就是当前堆的最小值 print(res,end=' ') self.heap[1],self.heap[self.idx] = self.heap[self.idx],self.heap[1] self.idx -= 1 self.down(1)if __name__ == '__main__': heap = Heap() heap.main()/pre pAcWing 839. 模拟堆/p p维护一个集合，初始时集合为空，支持如下几种操作：/p olliI x，插入一个数 x；/liliPM，输出当前集合中的最小值；/liliDM，删除当前集合中的最小值（数据保证此时的最小值唯一）；/liliD k，删除第 k个插入的数；/liliC k x，修改第 k个插入的数，将其变为 x；/li/ol p现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。/p p输入格式/pp第一行包含整数 N。/p p接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。/p p输出格式/pp对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。/pp每个结果占一行。/p p数据范围/pp 1 ≤ N ≤ 1 0 5 1≤N≤10^5 1≤N≤105/pp − 1 0 9 ≤ x ≤ 1 0 9 −10^9≤x≤10^9 −109≤x≤109/p p数据保证合法。/p p输入样例：/pp8/ppI -10/ppPM/ppI -10/ppD 1/ppC 2 8/ppI 6/ppPM/ppDM/p p输出样例：/pp-10/pp6/p olli理解hp与ph数组，以及为什么需要它们/li/ol ulli堆h[i]只能存放数据，不能存放当前数字是第几个插入的数，所以需要ph[k] = i来指明，第k个数字在h[]中的索引值为i/lili在执行交换操作的时候，可以直接交换数字,swap(h[a],h[b])/pp但是对于 p h [ k 1 ] = a 和 p h [ k 2 ] = b ph[k_1] = a和ph[k_2] = b ph[k1]=a和ph[k2]=b来说,a和b是它们存放的值,不 能通过值来找下标，也就是找不k_1,k_2是多少/lili于是引入hp[a] = k_2，hp[b] = k_2，则可以实现反向的操作ol start="2"li形象理解heap_swap中的次序是任意的/pph[]：房间号无直接实际意义，里边住着犯人/ppph[]：花名册，狱警所有，写明了几号犯人住在哪个房间号里，用于抓某些人/pp（但是狱警无权过问每个号里住的是谁）/pphp[]：住户册，监狱所有，写明了哪个房间号里住的是几号，用于管理监狱/pp（但是监狱没必要知道哪个犯人住在哪里）/ppheap_swap：已知两个犯人住的地方，交换它们住的地方，并且让狱警和管理 处都知道这件事情/ppswap(h[a], h[b])：两个人换地方住/ppswap(hp[a], hp[b])：监狱管理处翻房间号，把里边存放的犯人号交换/ppswap(ph[hp[a]], ph[hp[b]])：狱警：先申请查住户册，看这两个地方住的谁，再在花名册下写下来，这两个人位置换了/pph[a] = 10, h[b] = 20 swap: h[a] = 20,h [b] = 10/pphp[a] = 1 ,hp[b] = 2 swap:hp[a] = 2 ,hp[b] = 1/ppph[1] = a ,ph[2] = b swap:ph[1] = b ,ph[2] = a/pp//这种不变形也很像线代中：代表交换的初等矩阵，进行逆运算之后，仍然是该初等矩阵/li/ol pre class heap: def main(self): n = int(input()) self.heap = [0] * 100010 # 记录堆中的元素 self.hp = [0] * 100010 # 记录堆中元素到第几个插入的映射 self.ph = [0] * 100010 # 记录第几个插入的元素到堆的映射 self.cnt = 0 # 记录堆中的位置 self.idx = 0 # 记录第几个插入的元素 for i in range(n): line = input().split() op = line[0] if op == 'I': u = int(line[1]) self.cnt += 1 self.idx += 1 self.ph[self.idx] = self.cnt self.hp[self.cnt] = self.idx self.heap[self.cnt] = u self.up(self.cnt) # 将元素插入到对的最后一个位置，并进行up操作 elif op == 'PM': print(self.heap[1]) elif op == 'DM': self.swap(1,self.cnt) # 删除堆中的堆顶元素：将堆顶元素与堆尾元素交换，将堆大小减一 self.cnt -= 1 self.down(1) # 交换后对堆顶元素进行down操作 elif op == 'D': k = int(line[1]) # 要删除的第k个元素 hk = self.ph[k] # 获取这个元素在堆中的索引 self.swap(hk,self.cnt) self.cnt -= 1 self.down(hk) self.up(hk) else: k,x = int(line[1]),int(line[2]) hk = self.ph[k] self.heap[hk] = x self.down(hk) self.up(hk) def down(self,x): t = x if 2*x = self.cnt and self.heap[t] self.heap[2*x]:t = 2*x if 2*x+1 = self.cnt and self.heap[t] self.heap[2*x+1]:t=2*x+1 if t != x: self.swap(t,x) self.down(t) def up(self,x): while x 1 and self.heap[x] > 1]: self.swap(x,x>>1) x >>=1 def swap(self,u,t): self.ph[self.hp[u]],self.ph[self.hp[t]] = self.ph[self.hp[t]],self.ph[self.hp[u]] self.hp[u],self.hp[t] = self.hp[t],self.hp[u] self.heap[u],self.heap[t] = self.heap[t],self.heap[u]if __name__ == '__main__': heap = heap() heap.main()哈希表
- 存储结构：开放寻址法、拉链法
- 作用，将一个比较大的范围的数映射到一个比较小的范围；如 [ − 1 0 9 , 1 0 9 ] [-10^9,10^9] [−109,109]，映射到 [ 0 , 1 0 5 ] [0,10^5] [0,105]
- 哈希冲突：两个数被映射到同一个地址上
- 解决哈希冲突的方法：开放寻址法和拉链法
- 拉链法：
- 通过哈希函数将一个值映射到一个地址上
- 这个地址上存储一个单链表
- 如果出现了哈希冲突，就在链表上在增加一个元素
class Hash: def __init__(self): N = 100003 # 取大于n的第一个质数，降低哈希碰撞的概率 self.h = [-1] * N self.e = [0] * N self.ne = [0] * N self.idx = 0 self.n = N def insert(self,x): k = (x % self.n + self.n)% self.n # 计算哈希值，通过哈希值索引到一个地址上 self.e[self.idx] = x # 将这个值存储到链表中 self.ne[self.idx] = self.h[k] self.h[k] = self.idx self.idx += 1 def query(self,x): k = (x % self.n + self.n)% self.n idx = self.h[k] while ~idx: if self.e[idx] == x:return "Yes" idx = self.ne[idx] return "No" def main(self): n = int(input()) for i in range(n): line = input().split() op = line[0] x = int(line[1]) if op == "I":self.insert(x) else:print(self.query(x))if __name__ == '__main__': hash = Hash() hash.main()
2. 开放寻址法： 1. 只开一个数组，这个数组的长度一般来说是n的2-3倍 2. 处理冲突，如果计算得到的哈希值指到的地址上存在元素，就从前往后逐个找，直到某个地址上不存在元素 3. 添加：先查找哈希值计算得到的地址上是否存在元素，如果存在就从前往后找，直到找到一个没有元素的地址 4. 查找：先找到哈希值计算得到的地址上，如果当前值与查找的值相等，就找到元素，如果直到找到空位置还没找到需要查找的值，就不存在这个元素
class HASH: def __init__(self): N = 200003 self.hash = [float('inf')] * N # 初始化每个地址上存储的值为一个值域之外的值 self.n = N def find(self,x): k = (x % self.n + self.n) % self.n while self.hash[k] != float('inf') and self.hash[k] != x: k += 1 if k == self.n:k = 0 # 如果k到了最后一个位置，就从0继续开始查找 return k # 如果x存在哈希表中就返回在哈希表中的位置，如果不存在就返回可以插入的位置 def main(self): n = int(input()) for i in range(n): line = input().split() op = line[0] x = int(line[1]) k = self.find(x) if op == "I":self.hash[k] = x else: if self.hash[k] == x: print("Yes") else:print("No")if __name__ == '__main__': hash = HASH() hash.main()-
字符串哈希：
-
将一个字符串看成一个P进制的数
-
将这个P进制的字符串转换为十进制的数
-
将这个P进制的数对Q取模，计算后的哈希值范围就是[0,Q-1]
-
注意： 1. 不能字符映射成0；2. 假定不存在哈希冲突
- 经验值: P = 131 或者13331时，Q = 2 64 2^{64} 264，99.99%的概率下不会存在哈希冲突
-
计算区间[l,r]的哈希值时，只需要查询出h[r]和h[l-1]的哈希值
- h [ r ] = P r − 1 h[r] = P^{r-1} h[r]=Pr−1
- h [ l − 1 ] = P l − 2 h[l-1] = P^{l-2} h[l−1]=Pl−2
- 将两个哈希值进行位数对齐: h [ l − 1 ] ∗ P r − l + 1 h[l-1] * P^{r - l + 1} h[l−1]∗Pr−l+1
- 将对齐后的哈希值相减得到: h [ r ] − h [ l − 1 ] ∗ P r − l + 1 = h [ r − l ] h[r] - h[l-1] * P^{r-l+1} = h[r-l] h[r]−h[l−1]∗Pr−l+1=h[r−l]
- 例如：h[r] = ABCD的哈希值;h[l-1] = AB的哈希值；将h[l-1]与h[r]进行位数对齐后得到AB00,将两个哈希值相减，就得到CD的哈希值
AcWing 841. 字符串哈希
给定一个长度为 n的字符串，再给定 m个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1]和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
输入格式
第一行包含整数 n 和 m，表示字符串长度和询问次数。
第二行包含一个长度为 n的字符串，字符串中只包含大小写英文字母和数字。
接下来 m行，每行包含四个整数 l1,r1,l2,r2，表示一次询问所涉及的两个区间。
注意，字符串的位置从 11 开始编号。
输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1 ≤ n , m ≤ 1 0 5 1≤n,m≤10^5 1≤n,m≤105
输入样例：
8 3aabbaabb1 3 5 71 3 6 81 2 1 2
输出样例：
YesNoYes
class Hash: def __init__(self): N = 100010 self.hash = [0] * N # 存放字符串的前缀哈希值 self.p = [0] * N # 预处理p^n self.p[0] = 1 # 初始化p[0] = 1; 即P^0 = 1 self.q = 13331 # 经验值 131 或 13331 self.mod = 1 1=>j)：
- f[0][i][j]：i=>j 直接从i到j的距离 小于 i=>1=>j 经过节点1到达节点j的距离
- f[0][i][1]+f[0][1][j]：i=>1=>j 经过节点1到达节点j的距离小于 i=>j 直接从节点i到节点j的距离
-
动态规划分析：
f[k][i][j]可以从两种情况转移而来：
- 从f[k−1][i][j]转移而来，表示i到j的最短距离不经过节点k
- 从f[k−1][i][k]+f[k−1][k][j] 转移而来，表示i到j的最短距离经过节点k
- f[k][i][j]=min(f[k−1][i][j],f[k−1][i][k]+f[k−1][k][j])
- 从总结上来看，发现f[k]只可能与f[k−1]有关。
AcWing 854. Floyd求最短路
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。
再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible。
数据保证图中不存在负权回路。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
接下来 k 行，每行包含两个整数 x,y，表示询问点 x 到点 y 的最短距离。
输出格式
共 k 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。
数据范围
1 ≤ n ≤ 200 , 1≤n≤200, 1≤n≤200,
1 ≤ k ≤ n 2 1≤k≤n^2 1≤k≤n2
1 ≤ m ≤ 20000 , 1≤m≤20000, 1≤m≤20000,
图中涉及边长绝对值均不超过 10000。
输入样例：
3 3 21 2 12 3 21 3 12 11 3
输出样例：
impossible1
class Floyd: def __init__(self): N = 210 self.a = [[float('inf')] * N for _ in range(N)] def floyd(self): for k in range(1, self.n + 1): for i in range(1, self.n + 1): for j in range(1, self.n + 1): self.a[i][j] = min(self.a[i][j], self.a[i][k] + self.a[k][j]) def main(self): self.n, self.m, self.k = map(int, input().split()) for i in range(1, self.n + 1): self.a[i][i] = 0 for i in range(self.m): a, b, w = map(int, input().split()) self.a[a][b] = min(self.a[a][b], w) self.floyd() for j in range(self.k): x, y = map(int, input().split()) if self.a[x][y] == float('inf'): print("impossible") else: print(self.a[x][y])if __name__ == '__main__': floyd = Floyd() floyd.main()最小生成树
- 给定一个无向图，在图中选择若干条边把图的所有节点连起来。要求边长之和最小。在图论中，叫做求最小生成树。
- 每次将离连通部分的最近的点和点对应的边加入的连通部分，连通部分逐渐扩大，最后将整个图连通起来，并且边长之和最小。
- 无向图添加边的时候添加两条边（a --> b 和 b --> a）
- 先随机找一个起点，遍历一遍以这个点为起点的所有边，找到边长最短的边t
- 将这个点加入到st数组中（st数组表示生成树中的点）
- 当外层循环到第二次循环的时候，将边权和res += dis[t]
- 再遍历所有边，更新其他边到生成树的距离（边到集合的距离表示：边到集合的最小边长）
伪代码：
int dist[n],state[n];dist[1] = 0;for(i : 1 ~ n){ t self.dist[j]): t = j # 如果节点t是孤立点，则直接返回 if i and self.dist[t] == float('inf'):return float('inf') # 更新最小生成树的权值 if i:res += self.dist[t] self.st[t] = True # 将节点t加入到最小生成树中 # 循环判断节点t是否能够更新生成树中的其他点的最小距离 for k in range(1,self.n+1): self.dist[k] = min(self.dist[k],self.arr[t][k]) return res def main(self): self.n,self.m = map(int,input().split()) for i in range(self.m): a,b,w = map(int,input().split()) # 由于图中是无向边，所以存储两条边，分别由a-->b;b-->a self.arr[b][a] = self.arr[a][b] = min(self.arr[a][b],w) t = self.prim() if t == float('inf'):print('impossible') else:print(t)if __name__ == '__main__': prim = Prim() prim.main()Kruskal 求最小生成树
-
将所有边按照权重的大小进行升序排序，然后从小到大遍历所有边。
-
如果当前边不在生成树中，就选择这条边，反之就舍去这条边
-
直到n 个顶点，筛选出来 n-1 条边为止。
-
筛选出来的边和所有的顶点构成最小生成树。
判断是否会产生回路的方法为：使用并查集。
-
初始化每个点的父节点指向自身（并查集）
-
遍历过程的每条边，判断这两个顶点的是否在一个集合中。
-
如果边上的这两个顶点在一个集合中，说明两个顶点已经连通，这条边舍掉
-
如果不在一个集合中，则将这条边权重添加到 res += w，并将这个点加入到集合中
AcWing 859. Kruskal算法求最小生成树
给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。
由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。
输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
数据范围
1 ≤ n ≤ 1 0 5 , 1≤n≤10^5, 1≤n≤105,
1 ≤ m ≤ 2 ∗ 1 0 5 , 1≤m≤2∗10^5, 1≤m≤2∗105,
图中涉及边的边权的绝对值均不超过 1000。
输入样例：
4 51 2 11 3 21 4 32 3 23 4 4
输出样例：
6
class Kruskal: def __init__(self): N = 100010 self.arr = list() self.p = [i for i in range(N)] def find(self,x): if x != self.p[x]: self.p[x] = self.find(self.p[x]) return self.p[x] def kruskal(self): res = 0 cnt = 0 for node in self.arr: a,b,w = node pa = self.find(a) # 找到a,b点的根节点，如果两个根节点不在同一个集合中，就将b加入到集合中 pb = self.find(b) if pa != pb: res += w # 更新总的边权重 cnt += 1 # 更新集合中的点数 self.p[pa] = pb return res,cnt def main(self): self.n,m = map(int,input().split()) for i in range(m): a,b,w = map(int,input().split()) self.arr.append([a,b,w]) self.arr.sort(key=lambda x:x[2]) # 按边的权重从小到大进行排序 res,cnt = self.kruskal() if cnt
二分图
染色法判断二分图
- 染色法：可以将所有点分在两个集合，所有的边只在两个集合之间，集合内部不存在边
- 二分图：一定不含有奇数环
- 思路：
- 初始化所有点颜色为0（表示未染色）
- 遍历所有点，每次将未染色的点进行dfs染色（两条边的两个顶点染不同颜色）
- 染色过程中如果某个点染色失败，说明不是二分图
- 如果能够全部染色，说明是二分图
AcWing 860. 染色法判定二分图
给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。
请你判断这个图是否是二分图。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。
输出格式
如果给定图是二分图，则输出 Yes，否则输出 No。
数据范围
1 ≤ n , m ≤ 1 0 5 1≤n,m≤10^5 1≤n,m≤105
输入样例：
4 41 31 42 32 4
输出样例：
Yes
import sys# 必须设置递归深度sys.setrecursionlimit(1000000) # python会爆栈，虽然设置了递归深度也没多大用class Solution: def __init__(self): N = 100010 M = 200010 self.e = [0] * M self.ne = [0] * M self.h = [-1] * N self.idx = 0 self.color = [0] * N def add(self,a,b): self.e[self.idx] = b self.ne[self.idx] = self.h[a] self.h[a] = self.idx self.idx += 1 def dfs(self,u,c): self.color[u] = c idx = self.h[u] while ~idx: cur = self.e[idx] if not self.color[cur]: if not self.dfs(cur,3-c):return False else: if self.color[cur] == c: return False idx = self.ne[idx] return True def main(self): n,m = map(int,input().split()) for i in range(m): a,b = map(int,input().split()) self.add(a,b) self.add(b,a) flag = True for i in range(1,n+1): if not self.color[i]: if not self.dfs(i,1): flag = False print("No") break if flag: print("Yes")if __name__ == '__main__': solution = Solution() solution.main()二分图最大匹配
- 最外层遍历所有的顶点，循环内需要初始化st数组（避免st数组对后面的匹配造成影响）
- 每个点匹配成功就将res加一，表示匹配数
- find(x)，查找当前x是否能够成功匹配
- 遍历x的所有邻边，如果当前邻边y没有被匹配过，就试着匹配y
- match(y)：记录当前y被谁匹配，如果已经匹配过，就递归对match[y]进行重新配对
- 如果find(match[y])也匹配成功，那么就将原来的y匹配给x
- 匹配失败则返回False
def find(self,boy): idx = self.h[boy] while ~idx: girl = self.e[idx] # 遍历这个boy的所有邻边（girl） if not self.st[girl]: # 如果这个girl没有匹配过，就试着给这个女孩匹配 self.st[girl] = 1 # 标记匹配过 if self.match[girl] == 0 or self.find(self.match[girl]): # 如果这个girl匹配的boy数为0，说明这个girl可以被匹配 # 否则就试着重新对这个girl匹配的男孩重新匹配女孩 self.match[girl] = boy return True # 如果匹配成功就标记为True idx = self.ne[idx] return False
AcWing 861. 二分图的最大匹配
给定一个二分图，其中左半部包含 n 1 n_1 n1 个点（编号 1 ∼ n 1 1∼n_1 1∼n1），右半部包含 n 2 n_2 n2 个点（编号 1 ∼ n 2 1∼n_2 1∼n2），二分图共包含 m 条边。
数据保证任意一条边的两个端点都不可能在同一部分中。
请你求出二分图的最大匹配数。
二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。
二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。
输入格式
第一行包含三个整数 n 1 n_1 n1、 n 2 n_2 n2和 m。
接下来 m 行，每行包含两个整数 u 和 v，表示左半部点集中的点 u 和右半部点集中的点 v 之间存在一条边。
输出格式
输出一个整数，表示二分图的最大匹配数。
数据范围
1 ≤ n 1 , n 2 ≤ 500 , 1≤n_1,n_2≤500, 1≤n1,n2≤500,
1 ≤ u ≤ n 1 , 1≤u≤n_1, 1≤u≤n1,
1 ≤ v ≤ n 2 , 1≤v≤n_2, 1≤v≤n2,
1 ≤ m ≤ 1 0 5 1≤m≤10^5 1≤m≤105
输入样例：
2 2 41 11 22 12 2
输出样例：
2
class Solution: def __init__(self): N = 510 M = 100010 self.e = [0] * M self.ne = [0] * M self.h = [-1] * N self.idx = 0 self.st = [0] * N self.match = [0] * N def add(self,a,b): self.e[self.idx] = b self.ne[self.idx] = self.h[a] self.h[a] = self.idx self.idx += 1 def find(self,boy): idx = self.h[boy] while ~idx: girl = self.e[idx] # 遍历这个boy的所有邻边（girl） if not self.st[girl]: # 如果这个girl没有匹配过，就试着给这个女孩匹配 self.st[girl] = 1 # 标记匹配过 if self.match[girl] == 0 or self.find(self.match[girl]): # 如果这个girl匹配的boy数为0，说明这个girl可以被匹配 # 否则就试着重新对这个girl匹配的男孩重新匹配女孩 self.match[girl] = boy return True # 如果匹配成功就标记为True idx = self.ne[idx] return False def main(self): n1,n2,m = map(int,input().split()) for _ in range(m): boy,girl = map(int,input().split()) self.add(boy,girl) res = 0 for i in range(1,n1+1): self.st = [0] * 510 # 每次遍历的时候都需要初始化st数组，避免对后续遍历产生影响 if self.find(i):res += 1 # 如果匹配成功一对，res就加一 print(res)if __name__ == '__main__': solution = Solution() solution.main()
第四章 数学知识
质数
-
质数定义：在大于1的整数中，如果只包含1和本身这两个约数就被称为质数或素数
-
质数的判定：试除法
-
n的因数只需从2枚举到 n \sqrt{n} n
- 证明：
d | n 表示：d能够整除n
n d {n \over d} dn | n 表示： n d {n \over d} dn 也能整除n
例如：2是12的约数，那么6也是12的约数
所以只需要枚举较小的约数即可
∵ d ≤ n d {n \over d} dn
∴ d 2 d^2 d2 ≤ n
∴ d ≤ n \sqrt{n} n
细节： n \sqrt{n} n 最好写成 i ≤ n / i
def find(n): if n
- 证明：
∑ i = 0 n − 1 ( a i − a n / 2 ) = ∑ i = 0 n − 1 ( a i − a i / 2 ) \sum_{i = 0}^{n-1}(a_i - a_{n/2}) = \sum_{i = 0}^{n-1}(a_i - a_{i/2}) i=0∑n−1(ai−an/2)=i=0∑n−1(ai−ai/2)
∑ i = 0 n − 1 ( a i − a n / 2 ) = ( a n − 1 − a n / 2 ) + ( a n − 2 − a n / 2 ) + . . . + ( a n / 2 − a n / 2 ) + . . . + ( a n / 2 − a 0 ) = ( a n / 2 + 1 + a n / 2 + 2 + . . . + a n − 1 ) − ( a 0 + a 1 + . . . + a n / 2 − 1 ) \sum_{i = 0}^{n-1}(a_i - a_{n/2}) = (a_{n-1} - a_{n/2}) + (a_{n-2} - a{n/2}) + ... + (a_{n/2} - a_{n/2}) + ... + (a_{n/2} - a_0) \\ = (a_{n/2+1} + a_{n/2+2} +...+a_{n-1}) - (a_0 + a_1 + ... + a_{n/2-1}) i=0∑n−1(ai−an/2)=(an−1−an/2)+(an−2−an/2)+...+(an/2−an/2)+...+(an/2−a0)=(an/2+1+an/2+2+...+an−1)−(a0+a1+...+an/2−1)
∑ i = 0 n − 1 ( a i − a i / 2 ) = ( a n − 1 − a ( n − 1 ) / 2 ) + ( a n − 2 − a ( n − 2 ) / 2 ) + . . . + ( a n / 2 − a n / 2 ) + . . . + ( a 1 − a 1 / 2 ) + ( a 0 − a 0 ) = ( a 0 + a 1 + . . . + a n − 1 ) − 2 ∗ ( a 0 + a 1 + . . . + a n / 2 − 1 ) − a n / 2 − 1 = ( a n / 2 + 1 + a n / 2 + 2 + . . . + a n − 1 ) − ( a 0 + a 1 + . . . + a n / 2 − 1 ) \sum_{i = 0}^{n-1}(a_i - a_{i/2}) = (a_{n-1} - a_{(n-1)/2}) + (a_{n-2} - a{(n-2)/2}) + ... + (a_{n/2} - a_{n/2}) + ... + (a_1 - a_{1/2}) + (a_0 - a_0)\\ = (a_0 + a_1 +...+a_{n-1}) - 2*(a_0 + a_1 + ... + a_{n/2-1}) - a_{n/2 - 1} \\= (a_{n/2+1} + a_{n/2+2} +...+a_{n-1}) - (a_0 + a_1 + ... + a_{n/2-1}) i=0∑n−1(ai−ai/2)=(an−1−a(n−1)/2)+(an−2−a(n−2)/2)+...+(an/2−an/2)+...+(a1−a1/2)+(a0−a0)=(a0+a1+...+an−1)−2∗(a0+a1+...+an/2−1)−an/2−1=(an/2+1+an/2+2+...+an−1)−(a0+a1+...+an/2−1)
推公式:
- AcWing 125. 耍杂技的牛
农民约翰的 N 头奶牛（编号为 1…N）计划逃跑并加入马戏团，为此它们决定练习表演杂技。
奶牛们不是非常有创意，只提出了一个杂技表演：
叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。
奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。
这 N 头奶牛中的每一头都有着自己的重量 Wi 以及自己的强壮程度 Si。
一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。
您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。
输入格式
第一行输入整数 N，表示奶牛数量。
接下来 N 行，每行输入两个整数，表示牛的重量和强壮程度，
第 i 行表示第 i 头牛的重量 Wi 以及它的强壮程度 Si。
输出格式
输出一个整数，表示最大风险值的最小可能值。
数据范围
1≤N≤50000,
1≤Wi≤10,000,
1≤Si≤1,000,000,000
输入样例：
3
10 3
2 5
3 3
输出样例：
2
题解：
计算每一层的风险值：
n n n w w w s s s r r r 1 w 0 w_0 w0 s 0 s_0 s0 0 − s 0 0 -s_0 0−s0 2 w 1 w_1 w1 s 1 s_1 s1 w 0 − s 1 w_0 - s_1 w0−s1 … … … … i w i w_i wi s i s_i si w 0 + w 1 + . . . + w i − 1 − s i w_0 + w_1 + ... + w_{i-1} -s_i w0+w1+...+wi−1−si i+1 w i + 1 w_{i+1} wi+1 s i + 1 s_{i+1} si+1 w 0 + w 1 + . . . + w i − 1 + w i − s i + 1 w_0 + w_1 + ... + w_{i-1} + w_i-s_{i+1} w0+w1+...+wi−1+wi−si+1 … … … … n w n w_n wn s n s_n sn w 0 + w 1 + . . . + w i − 1 + w i + . . . + w n − 1 − s n w_0 + w_1 + ... + w_{i-1} + w_i + ... + w_{n-1} - s_n w0+w1+...+wi−1+wi+...+wn−1−sn 任选连续两层计算
n n n w w w s s s r r r i i i w i w_i wi s i s_i si w 0 + w 1 + . . . + w i − 1 − s i w_0 + w_1 + ... + w_{i-1} -s_i w0+w1+...+wi−1−si i + 1 i+1 i+1 w i + 1 w_{i+1} wi+1 s i + 1 s_{i+1} si+1 w 0 + w 1 + . . . + w i − 1 + w i − s i + 1 w_0 + w_1 + ... + w_{i-1} + w_i-s_{i+1} w0+w1+...+wi−1+wi−si+1 交换当前两层的叠放顺序
n n n w w w s s s r r r i i i w i + 1 w_{i+1} wi+1 s i + 1 s_{i+1} si+1 w 0 + w 1 + . . . + w i − 1 − s i + 1 w_0 + w_1 + ... + w_{i-1} - s_{i+1} w0+w1+...+wi−1−si+1 i + 1 i+1 i+1 w i w_i wi s i s_i si w 0 + w 1 + . . . + w i − 1 + w i + 1 − s i w_0 + w_1 + ... + w_{i-1} + w_{i+1} -s_i w0+w1+...+wi−1+wi+1−si 取出交换前后第i层和i+1层的风险值（各项中消掉 w 0 + w 1 + . . . + w i − 1 w_0 + w_1 + ... + w_{i-1} w0+w1+...+wi−1）
n n n r 前 r_前 r前 r 后 r_后 r后 i i i − s i - s_i −si − s i + 1 - s_{i+1} −si+1 i + 1 i+1 i+1 w i − s i + 1 w_i- s_{i+1} wi−si+1 w i + 1 − s i w_{i+1}- s_i wi+1−si 由于w为正值，所以 w i − s i + 1 w_i- s_{i+1} wi−si+1 > − s i + 1 - s_{i+1} −si+1; w i + 1 − s i + 1 w_{i+1}- s_{i+1} wi+1−si+1 > − s i - s_i −si
所以比较 w i − s i + 1 w_i- s_{i+1} wi−si+1与 w i + 1 − s i + 1 w_{i+1}- s_{i+1} wi+1−si+1的大小，便能够确定交换前后风险值的变化
假设：
w i − s i + 1 w_i- s_{i+1} wi−si+1 > w i + 1 − s i w_{i+1}- s_i wi+1−si 移项后得到
w i + s i w_i + s_i wi+si > w i + 1 + s i + 1 w_{i+1} + s_{i+1} wi+1+si+1
推出：如果当前层的自身重量和强壮程度之和大于下一层的自身重量和强壮程度，交换两层的顺序后得到的风险值不会变坏，所以将w+s按照从小到大的顺序叠放得到的风险值最小
def main(): n = int(input()) q = [] for i in range(n): w,s = map(int,input().split()) q.append([w,s]) q.sort(key=lambda x:sum(x)) res = -2e9 # si最大为1e9 ans = 0 for i in range(n): res = max(res, ans - q[i][1]) ans += q[i][0] print(res)if __name__ == '__main__': main()
- AcWing 125. 耍杂技的牛
- 证明：
- 证明：
-
-
- 拉链法：
- 模板（C++）
- python代码
- Python代码
- 模板（C++）
- Python代码
- AcWing 785. 快速排序
下一篇：服务器分机怎么连?
