备战蓝桥杯学习路线：AcWing算法基础课->AcWing蓝桥杯课
（由于基础课和蓝桥课一共有85小时，现在每天平均是30mins到45mins，可能不是很够。从明天开始，每天看视频讲解一小时并且要消化内容，估计一起得花3-4小时。这样子差不多一月底，二月初可以结束视频课程）
Day1.(2021.10.12)
#Python input是输入的字符串，当要输入一串数组需要用如下arrs的两种方法
#如果输入的字符串没有用空格分开，则可以不加split()
n = int(input())
arrs = list(map(int, input().split()))
arrs = [int(x) for x in input().split()]学习思路：1 先理解算法主要思想，2 背模板，3多做几道题（在做题的时候，当你AC了，马上把代码删除，再重新写一边，重复两三次）
快速排序
其主要思想是分治
1. 确定分界点de，一般选择左端点q[l]，右端点q[r]或者中间q[(l+r)/2]
2. 调整范围，将左边调整为小于等于分界点，右边调整为大于等于分界点
3. 递归处理左右两段
其中重难点是2，简单方法（但耗空间）是：
1. 先设置两个数组a[], b[]
2. 数组q[l~r]中小于等于de的放入a[]，大于等于de的放入b[]
3. 然后将a和b合并放入数组q，a在左边，b在右边
主要方法是，在数组两端分别设置指针i,j，while q[i]<de: i++，while q[j]>de: j–，if i<j swap(q[i],q[j]) else 递归处理左边部分(l,j)和右边部分(j+1,r)。重复上述步骤。
Python模板：
# acwing.785 快速排序
n = int(input())
a = list(map(int, input().split()))
#a = [int(x) for x in input()]
def quick_sort(a,l,r):
if l>=r: return
# x = a[l]
x= max(min(a[l], a[r]), a[(l + r) // 2])
i,j = l-1,r+1
while i<j:
i+=1
j-=1
while a[i]<x: i+=1
while a[j]>x: j-=1
if i<j: a[i],a[j] = a[j],a[i]
quick_sort(a,l,j)
quick_sort(a,j+1,r)
quick_sort(a,0,n-1)
print(' '.join(map(str,a)))Day2.(2021.10.14)
Python Append
- 当Append一个元素时，Python将创建一个足够大的列表，来容纳N个元素和将要被追加的元素。重新创建的列表长度大于N＋1（虽然我们只触发一次append操作），实际上，为了未来的Append操作，M个元素长度（M>N+1)的内存将会被额外分配，然后，旧列表中的数据被copy到新列表中，旧列表销毁。
- 额外内存的分配，只会发生在第一次Append操作时，当我们创建普通列表时，不会额外分配内存。
从这里还有网上其他地方整理知识点可以知道：
Append操作会申请新的一连串的空间，整体copy过去，那么就存在时间效率的下降，相对于一开始申请很大的空间。
生成列表的五种方式（从0开始生成含有n个数的列表）
import timeit
def test1():
l = []
for i in range(1000):
l += [i]
def test2():
l = []
for i in range(1000):
l.append(i)
def test3():
l = [i for i in range(1000)]
def test4():
l = list(range(1000))
def test5():
l = [0] * 1000
t1 = timeit.Timer("test1()", "from __main__ import test1")
print(t1.timeit(number=1000), "milliseconds")
t2 = timeit.Timer("test2()", "from __main__ import test2")
print(t2.timeit(number=1000), "milliseconds")
t3 = timeit.Timer("test3()", "from __main__ import test3")
print(t3.timeit(number=1000), "milliseconds")
t4 = timeit.Timer("test4()", "from __main__ import test4")
print(t4.timeit(number=1000), "milliseconds")
t5 = timeit.Timer("test5()", "from __main__ import test5")
print(t5.timeit(number=1000), "milliseconds")
这个结果和书上的结果有出入的地方在于1和2项，书上1的性能比2慢一个数量级（10倍）。
Python数据结构性能分析
归并排序
归并排序的主要思想也是分治，它和快排的思想不同，快排是边分边治，它是先分后治。
1. 确定分界点 mid=(r+l)/2
2. 递归排序左右两部分 （根据选出的分界点，将分界点左边的递归处理，右边的递归处理）
3. 归并-合二为一 （递归的终止条件是l>=r，返回后就要考虑怎么把左右两部分正确的合在一起）
# acwing.787 归并排序
n = int(input())
a = list(map(int, input().split()))
def merge_sort(a,l,r):
if l>=r:return
mid = (l+r)//2
merge_sort(a,l,mid)
merge_sort(a,mid+1,r)
tmp,i,j = [],l,mid+1
while i<=mid and j<=r:
if a[i]<a[j]:
tmp.append(a[i])
i+=1
else:
tmp.append(a[j])
j+=1
# or using tmp.extend(a[i:mid+1])
if i<=mid:tmp+=a[i:mid+1]
if j<=r:tmp+=a[j:r+1]
a[l:r+1] = tmp[:]
merge_sort(a,0,n-1)
print(" ".join(map(str, a)))Day3.(2021.10.14)
Day2的List五种生成方式和数据结构分析是今天做的。本来说把归并的788题做了，结果进去就跳转到算法基础课的活动，然后在leetcode上也没找到合适的题就把归并和快排复习了下，发现归并都是用<=或>=，而快排只有最开始判断的时候用了>=，其余都没有>=或<=，如果有的话还会报错。
Day4.(2021.10.15)
二分
这一节在刚开始听的时候还有点蒙蔽，一上来就在讲方法和思想，我连算法要解决的问题都还不清楚😂。然后二分的本质不是单调性，而是边界。比如：给定一个区间，在这个区间中定义了某种性质，使得这个性质在有左半边区间是满足的，而右半部不满足（注意两者没有交点，当整数二分时），则二分就可以寻找到这个边界左半边的边界和右半的都可以找到。而找到左边的边界，和右边的边界就分别是用两个不同的模板了。
这里解决的算法问题是假定先找黑色那个点，后找绿色那个点，然后整体思路就是：
找黑色的边界点，首先检查中间值是否满足黑色性质，
如果满足，则在mid右边部分找[mid,r], l=mid，注意是包含mid。否则mid左边找[l,mid-1],r=mid-1
找绿色的边界点，首先检查中间值是否满足绿色性质，
如果满足，则在mid的左边部分找[l,mid],r=mid。否则mid右边找[mid+1,r],l=mid+1
整数二分（ACWING789题）：
注意：在找右边边界时需要mid=(l+r+1)/2 （如果不加1，假设l=r-1，如果此时True会无限递归），左边是mid=(l+r)/2。（或者记个口诀，let it go，l=mid的上面是有+1）
模板：解决单调数组找一个数最初和最后出现的位置，未出现则返回-1 -1
最后l和r的结果相等（当执行完一次寻找后，while）
# acwing 789.数的范围
if __name__ == '__main__':
n, q = map(int, input().split())
a = [int(x) for x in input().split()]
for i in range(q):
k = int(input())
l, r = 0, n-1
while l<r:
mid = (l+r)//2
if a[mid]>=k: r=mid
else: l=mid+1
if a[l]!=k:
print('-1 -1')
continue
else:
print(l, end=' ')
l, r = 0, n-1
while l<r:
mid = (l+r+1)//2
if a[mid]<=k: l=mid
else: r=mid-1
print(l)Day5.(2021.10.17)
说实话，二分算法的过程我感觉很抽象，必须要依靠画图才能肯定。
当你找左边界，是找所有>=num的数，如果arr[mid]>=num，那么答案一定在左半边，那么r=mid，因为也有可能就是mid。
假如红色点是左边界，现在mid在黄色点，是>=num（红色点的值）的，则应该去左边找，则令右边界为mid。
浮点数二分：
浮点数二分相对于整数二分就简单许多，不需要有加一减一等操作，只需要判断要找的数在mid左边还是右边。
# acwing 790. 数的三次方根
n=float(input())
l,r=-10000,10000
while l<r-1e-8:
mid=(l+r)/2
if mid**3>=n: r=mid
else: l=mid
print("{:.6f}".format(l))Day6.(2021.10.18)
高精度：
Java和Python不需要关注高精度，Java有大整数类，Python本身就是无限大。但万一以后搞C++去了呢？
大数运算一般有A+B, A-B, A*a, A/a。其中大写代表大数（位数在1000000之内），小写代表小数（值效于10000）。解决这几个问题一般是模拟人工加法的过程：
当然首先要看的是怎么存储两个大数，要用数组来存储，而且是数组的低位存大数的低位，假如123456789为大数，则arr[0]=9, arr[1]=8 … arr[8]=1。这是因为高位可能要进位，这样进位后不需要移动数组。
高精度加法：
# acwing 791. 高精度加法
n = list(map(int, input()[::-1]))
m = list(map(int, input()[::-1]))
def add(n,m):
res = []
i,j,t = 0,0,0
while i<len(n) or j<len(m):
if i<len(n):
t+=n[i]
i+=1
if j<len(m):
t+=m[j]
j+=1
res.append(t%10)
t//=10
if t: res.append(t)
return res
res = add(n,m)[::-1]
print("".join(map(str,res)))Day7.(2021.10.19)
高精度减法：
减法也是模拟人工减法的过程，同时减法是要保证A比B大的，不然就要B-A，然后加个负号（因此需要首先判断谁大）我们这里先假定A和B都是正数 （题目说了）。如果有负数，则可以用|A|+|B|或者|A|-|B|解决。（减法比加法复杂一点，因为需要判断谁大，和消除前导0）
# acwing 792. 高精度减法
n = list(map(int, input()[::-1]))
m = list(map(int, input()[::-1]))
def compare(n,m):
if len(n) != len(m):
return len(n)>len(m)
i = len(n)-1
while i>=0:
if n[i]!=m[i]:
return n[i]>m[i]
i-=1
# print(0) 这样子还可以节省时间
# exit(0)
return True
def sub(n,m):
res = []
i,j,t = 0,0,0
while i<len(n) or j<len(m):
if i<len(n):
t+=n[i]
i+=1
if j<len(m):
t-=m[j]
j+=1
res.append((t+10)%10)
if t<0: t=-1
else: t=0
while len(res)>1 and res[-1]==0:
res.pop()
return res
if compare(n,m):
res = sub(n,m)[::-1]
print("".join(map(str,res)))
else:
res = sub(m,n)[::-1]
print("-" + "".join(map(str,res)))
Day8.(2021.10.20)
今天复习了下加法和减法的算法并根据Python的特性重构了下，并自己试验几组数组
高精度乘法：
这里的高精度乘法是是大数和小数相乘。主要思想是把小数b看成一个整体，用A去乘（A每位去乘）
# acwing 793. 高精度乘法
A = list(map(int, input()))[::-1]
b = int(input())
def mul(A,b):
res,i,t,n = [],0,0,len(A)
while i<n:
t += A[i]*b
res.append(t%10)
t //= 10
i += 1
while t:
res.append(t%10)
t //= 10
while len(res)>1 and res[-1]==0:
res.pop()
return res
res = mul(A,b)[::-1]
print("".join(map(str,res)))Day9.(2021.10.21)
高精度除法：
这里也是大数除以小数，具体做法和手算除法一样。（从最高位开始算，但由于题目一般都是加减乘除要结合起来，所以也将除法的高位存在数组的高位）
# acwing 794. 高精度除法
A = list(map(int, input()))[::-1]
b = int(input())
def div(A,b):
res, n, i, t= [], len(A), len(A)-1, 0
while i>=0:
t = t*10+A[i]
res.append(t//b)
t %= b
i -= 1
while len(res)>1 and res[0]==0:
res.pop(0)
return res, t
res, t = div(A,b)
print("".join(map(str, res)))
print(t)Day10.(2021.10.22)
前缀和：
它能够快速求出数组中某一段的和。令s[0]=0可以少一个if判断（统一判断格式）。
C++输入数据大的时候用scanf，小的时候用cin，ios::sync_with_stdio(false)可以加快cin输入。
一维前缀和其实很简单，不多说
# acwing 795. 前缀和
n,m = map(int, input().split())
a = [0] + list(map(int, input().split()))
s = [0]*(n+1)
for i in range(1,n+1):
s[i] = s[i-1] + a[i]
for _ in range(m):
l,r = map(int, input().split())
print(s[r]-s[l-1])二维前缀和
二维前缀和求某个矩形区域的和看上图理解下，值得注意的是初始化的时候就是将求某个区域（原数组）的前缀和改成求某个点的前缀和。
二维前缀和主要有python二维数组的定义和输入方式，同样要注意的是为了子矩阵和计算方便，它使得数组第一行和第一列都为0。
# 这个代码和上面一维的风格有点不同，主要是有没有新增一个数组来作为前缀和数组
# 数组长度为n，m列，q个询问
n, m, q = map(int, input().split())
#构造原数组
a = [[0] * (m+1) for _ in range(n+1)]
for i in range(1,n+1):
a[i][1:] = list(map(int, input().split()))
#构造前缀和数组
#本来应该新建一个二维数组s，这样直接在a上原地修改可以节省空间，但可读性较差点
for i in range(1,n+1):
for j in range(1,m+1):
a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1]
for _ in range(q):
x1, y1, x2, y2 = map(int, input().split())
ans = a[x2][y2] - a[x1-1][y2] - a[x2][y1-1] + a[x1-1][y1-1]
print(ans)将一维前缀和风格改变：
# 数组长度为n，m个询问查询
n, m = map(int, input().split())
#构造输入数组
a = [0] * (n+1)
a[1:n+1] = list(map(int, input().split()))
#构造前缀和数组
for i in range(1,n+1):
a[i] += a[i-1]
#l,r分别代表查询的左边界和右边界
for i in range(m):
l, r = map(int, input().split())
print(a[r]-a[l-1])Day11.(2021.10.23)
一维差分：
假定a: a1,a2,a3…,an是数组b: b1,b2,b3…,bn的前缀和数组，那么成b是a的差分数组。即ai = b1+b2+b3+…+bi。（反过来可以推出b1=a1,b2=a2-a1,b3=a3-a2…,bn=an-an-1）(差分其实就是前缀和的逆运算)
差分有什么用呢，首先可以在O(n)的时间内，由b数组得到a数组，重点：让数组a某段（l,r）每个元素都加上（连续加多次）某一值的操作从O(n)->O(1)，只需要将b[l]+c,b[r+1]-c。
首先我们要考虑如何初始化差分数组，然而对于差分数组来说，我们不需要单独考虑如何构造，只需要考虑如何更新（把初始化也当成更新）。
重点：我们来看下为什么可以把初始化也当成更新操作，首先你假设a数组全为0，则差分数组b也全为0。现在你要做的更新操作就是在数组a[1,1]，[2,2]，[3,3]…的范围依加上a1,a2,a3…，则相当于在数组b[1]+a1,b[2]-a1、b[2]+a2,b[3]-a2、…
# 数组长度为n，m个询问查询
n, m = map(int, input().split())
# 定义插入函数
def insert(l,r,c):
b[l]+=c
b[r+1]-=c
#构建原数组和差分数组
a = [0]*(n+2)
b = [0]*(n+2)
# 初始化原数组
a[1:n+1] = list(map(int, input().split()))
# 初始化差分数组
for i in range(1,n+1):
insert(i,i,a[i])
for i in range(m):
l, r, c = map(int, input().split())
insert(l,r,c)
for i in range(1,n+1):
b[i]+=b[i-1]
print(b[i], end=" ")
二维差分：
注意二维差分和二维前缀和的不同，二维前缀和是对给定点的左上角操作，而二维差分则是对右下角进行操作。如果记不清楚该加减的位置，可以画图，这样更直观准确。（这里可能不好理解初始化二维差分数组的操作，插入操作是指在原数组某一范围插入一个数而要改变差分数组的哪些值的操作，当你在模拟在原始数组的每个点插入相对应的数时（这个动作是在改变差分数组的值），就相当于初始化差分数组）
# 数组长度为n，m. q个询问查询
n, m, q = map(int, input().split())
#构建原数组和差分数组
a = [[0]*(m+2) for _ in range(n+2)]
b = [[0]*(m+2) for _ in range(n+2)]
#定义插入函数
def insert(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
#初始化原数组
for i in range(1,n+1):
a[i][1:m+1] = list(map(int,input().split()))
#初始化差分数组
for i in range(1,n+1):
for j in range(1,m+1):
insert(i,j,i,j,a[i][j])
#q个插入操作
for i in range(0,q):
x1,y1,x2,y2,c = map(int, input().split())
insert(x1,y1,x2,y2,c)
#通过前缀和操作求原数组当前值
for i in range(1,n+1):
for j in range(1,m+1):
b[i][j] += b[i-1][j] + b[i][j-1] - b[i-1][j-1]
print(b[i][j], end=" ")
print()Day12.(2021.10.24)
双指针：
双指针算法有两大类，第一大类是分别指向两个数组，第二大类是同时指向一个序列。
双指针算法一般都可以从暴力的角度着手（看下i和j有没有什么单调关系），从而将算法复杂度从o(n^2)降低到o(n)。
模板:
i,j = 0,0
while i<n:
while j<i and check(i,j):
j+=1
i+=1
# 每道题的具体逻辑核心思想：
i，j = 0,0
while i<n:
while j<n:
O(n^2)
j+=1
i+=1
# 将这个朴素算法优化到O(n)# 检索以空格分开的单词
a = input()
n, i = len(a), 0
while i<n :
j = i
while i<n and a[i]!=" ":
i+=1
while j<i:
print(a[j], end="")
j+=1
print()
i+=1
# 这个代码稍微有点问题，就是你中间输入多个空格他会输出多个空行
当前下表i加入数组，若没有重复，则比较当前无重复数组长度和以前设定的最大长度，若更大，则更新且i+=1。（如果不开数组判断有没有重复，则可以使用hash表）
# acwing799. 最长连续不重复序列
n = int(input())
a = list(map(int, input().split()))
#初始化索引数组和两个指针
index_arr = [0]*(100001)
i,j,ans = 0,0,0
while i<n:
index_arr[a[i]] += 1
while index_arr[a[i]] == 2:
index_arr[a[j]] -= 1
j+=1
ans = max(ans, i-j+1)
i += 1
print(ans)位运算：
位运算一般有两个作用：1.n的二进制表示中第k位是几(n>>k&1)。2.lowbit操作（这道题好像是返回最右边的1所代表的数，树状数组的一个基本操作）
n, k = 10, 3
while k>=0:
print(n>>k&1, end="")
k-=1
它的功能是可以统计x里面1的个数（每次都把最后一个1去掉，减了多少次就有多少个1）
# acwing 801. 二进制中1的个数
n = int(input())
a = list(map(int, input().split()))
def lowbit(x):
return x&-x
for i in range(n):
res = 0
while a[i]:
a[i] -= lowbit(a[i])
res += 1
print(res, end=" ")
下面解释下为什么在计算机中用补码表示负数（最后一步手工带入x算）：
Day13.(2021.10.25)
逆序对
昨天1024买了课程，今天开始把前些天没做的题给补上，然后顺便再复习已经学过的知识。发现快排和归并又搞忘了。。。
逆序对是用归并的思想（分治）做的，只求逆序对中大的在左边序列，小的在右边序列的情况（最开始划分区间划分到为1的时候会解决大的和小的在一边的情况）。然后怎样计算有多少个逆序对呢：mid-i+1，当a[i]都比a[j]大的时候，左边序列i后面的值肯定也都比a[j]大。
# acwing788. 逆序对的数量
n = int(input())
a = list(map(int, input().split()))
def merge_sort(a,l,r):
if l>=r:return 0
mid = (l+r)//2
tmp,i,j = [],l,mid+1
res = merge_sort(a,l,mid) + merge_sort(a,mid+1,r)
while i<=mid and j<=r:
if a[i]<=a[j]:
tmp.append(a[i])
i+=1
else:
tmp.append(a[j])
res += mid-i+1
j+=1
if i<=mid: tmp.extend(a[i:mid+1])
if j<=r: tmp.extend(a[j:r+1])
a[l:r+1] = tmp[:]
return res
res = merge_sort(a,0,n-1)
print(res)Day14.(2021.10.26)
离散化：这里特指整数离散化，而且是有序的离散化（它的值域跨度很大，但是很稀疏）
# acwing 802. 区间和
n, m = map(int, input().split())
a, s = [0]*300010, [0]*300010
alls, add, query = [], [], []
for _ in range(n):
x, c = map(int, input().split())
add.append((x, c))
alls.append(x)
for _ in range(m):
l, r = map(int, input().split())
query.append((l,r))
alls.append(l)
alls.append(r)
#实现原代码中的去重排序操作
alls = list(set(alls))
alls.sort()
#找到离散化后x的坐标
def find(x):
l,r = 0,len(alls)-1
while l<r:
mid = (l+r)//2
if alls[mid]>=x:r=mid
else:l=mid+1
return r+1
#将所有数插入
for x,c in add:
index = find(x)
a[index] += c
#处理前缀和
for i in range(1,300010):
s[i] = s[i-1]+a[i]
for l,r in query:
print(s[find(r)]-s[find(l)-1])Day15.(2021.10.27)
区间合并
给你n个区间，如果某两区间有交集的话，就将它们合并成一个区间。
区间合并一般使用贪心算法（虽然这道题我没看出来贪心算法。。）
1.按区间左端点进行排序
2.扫描整个区间（在这个过程中把区间进行合并）
# acwing 803. 区间合并
n = int(input())
segs = []
for _ in range(n):
l,r = map(int, input().split())
segs.append((l,r))
segs = sorted(segs, key=lambda x:(x[0],x[1]))
def merge(segs):
res = []
st, ed=-2e9, -2e9
for i in range(n):
if ed<segs[i][0]:
if st!=-2e9: res.append((st,ed))
st, ed = segs[i][0],segs[i][1]
else: ed = max(ed,segs[i][1])
if st!=-2e9:
res.append((st, ed))
return len(res)
print(merge(segs))# 思路都一样，但是感觉这个代码更好理解
# acwing 803. 区间合并
n = int(input())
a = []
res = []
for _ in range(n):
l,r = map(int, input().split())
a.append([l,r])
a = sorted(a,key=lambda x:(x[0],x[1]))
for i in range(n):
if res:
if res[-1][1]>=a[i][0]:
res[-1][1]=max(res[-1][1], a[i][1])
else:
res.append([a[i][0], a[i][1]])
else:
res.append([a[0][0],a[0][1]])
print(len(res))Day16.(2021.10.28)
链表与邻接表
一般我们接触到的链表都是动态链表，如下图所示，但是动态链表的创建是非常满的（new操作），很大概率就直接超时了，所以一般只有面试的时候才用，笔试的时候不用。
这里讲的是拿数组模拟链表（单链表：用的最多的是邻接表，n个单链表合起来，用于存储树或者图，双链表：优化某些问题）
插入操作（非头节点）
删除操作
# acwing 826.单链表
# head表示头节点下表，e[i]表示节点i的值
# ne[i]表示节点i的next指针是多少，idx表示存储当前已经用到了哪个点
N = 100010
def insert_head(x):
global idx, head
e[idx], ne[idx], head, idx = x, head, idx, idx+1
def insert_node(k, x):
global idx
e[idx], ne[idx], ne[k], idx = x, ne[k], idx, idx+1
def remove(k):
ne[k] = ne[ne[k]]
if __name__ == '__main__':
m = int(input())
e, ne, idx, head = [0]*N, [0]*N, 0, -1
for _ in range(m):
op, *p = input().split()
p = [int(x) for x in p]
if op=='H': insert_head(p[0])
elif op=='D':
if p[0]==0: head = ne[head]
else: remove(p[0]-1)
else: insert_node(p[0]-1, p[1])
while head!=-1:
print(e[head], end=' ')
head = ne[head]Day16.(2021.10.29)
双链表
———————————————————————————————————————————
用下标为0的点表示头节点（左端点），为1的表示尾节点（右端点）
Left：左端点，right，右端点。这两个不算在链表里，所以在最左侧插入数就是在left右边插入。
为什么单链表用了头节点head，而双链表直接用01表示两端，这是因为大部分题目就用这样的操作可以解决。
0是左端点，因此r[0]=1, 1是右端点，l[1]=0
现在写的是在k的右边插入一个点，如果想在k的左边插入一个点，可以写成add(l[k],x)
这个是删除操作。
拿邻接表存储树和图放到第三章讲，这个双链表确实很难理解哈，只有自己多画图，然后结合着代码理解。
# acwing 827. 双链表
N = 100010
def insert(k,x):
global idx
e[idx], r[idx], l[idx], l[r[k]], r[k], idx = x, r[k], k, idx, idx, idx+1
def delete(k):
r[l[k]], l[r[k]] = r[k], l[k]
if __name__ == '__main__':
m = int(input())
e, l, r, idx = [0]*N, [0]*N, [0]*N, 2
r[0], l[1] = 1, 0
for _ in range(m):
op, *p = input().split()
p = [int(x) for x in p]
if op=='L': insert(0,p[0])
elif op=='R': insert(l[1],p[0])
elif op=='D': delete(p[0]+1)
elif op=='IL': insert(l[p[0]+1],p[1])
else: insert(p[0]+1,p[1])
while r[0]!=1:
print(e[r[0]], end=' ')
r[0] = r[r[0]]Day17.(2021.10.30)
栈和队列
刷题 acwing 828的时候看到x的范围是在1<=x<=10^9，就看了下c++整型，长整型的表示范围。
signed int 4B，(-2^32)/2 -> (2^32)/22-1 （长度是10位）
signed long 4B, (-2^32)/2 -> (2^32)/22-1 （长度是10位）
signed long long 8B. (-2^64)/2 -> (2^64)/22-1
首先学习用数组来模拟栈和队列：
栈：先进后出，从队尾插入队尾取出
# acwing 828. 模拟栈
N = 100010
m = int(input())
stk, tt = [0]*N, 0
def push(x):
global tt
stk[tt] = x
tt += 1
def pop():
global tt
tt -= 1
def empty():
global tt
if tt == 0: print("YES")
else: print("NO")
def query():
global tt
print(stk[tt-1])
for _ in range(m):
op, *p = input().split()
if op == "push":
push(int(p[0]))
elif op == "query":
query()
elif op == "pop":
pop()
else:
empty()队列：先进先出，在队尾插入，队头取出
# acwing 829. 模拟队列
N = 100010
m = int(input())
queue, hh, tt = [0]*N, 0, -1
def push(x):
global queue, hh, tt
tt += 1
queue[tt] = x
def pop():
global hh
hh+= 1
def empty():
global hh, tt
if hh== tt+1:
return "YES"
return "NO"
def query():
global queue, hh
return queue[hh]
for _ in range(m):
op, *p = input().split()
if op=="push":
x = int(p[0])
push(x)
elif op=="pop":
pop()
elif op=="empty":
print(empty())
else:
print(query())单调栈：给定一个序列，让我们求序列中的每个数的 左边离他最近的，且比它小的数（单调队列也一样）先想暴力解法，然后怎么优化（弄个单调序列出来）。
当把左边比右边大的数删掉后，会变成一个严格单调上升的栈。
# acwing 830. 单调栈
# 这是自己写的代码
# n = int(input())
# m = list(map(int, input().split()))
# a = []
#
# for i in range(n):
# while a:
# if a[-1]>=m[i]:
# a.pop()
# else:
# print(a[-1], end=" ")
# break
# if not a:
# print("-1", end=" ")
# a.append(m[i])
# 这是模仿yxc写的代码
N = 10010
n = int(input())
a = list(map(int, input().split()))
stk, tt = [0]*N, 0
for i in range(n):
while tt and stk[tt]>=a[i]: tt-=1
if tt: print(stk[tt], end=" ")
else: print("-1", end=" ")
tt += 1
stk[tt] = a[i]
# 今天又不会写这个代码了，整了下python标准库的栈
# acwing 830. 单调栈
import collections
n = int(input())
a = [int(x) for x in input().split()]
stk = collections.deque()
for i in range(len(a)):
while stk and a[i]<=stk[-1]:
stk.pop()
if stk: print(stk[-1], end=" ")
else: print("-1", end=" ")
stk.append(a[i])滑动窗口这道题，我花了两三个小时来理解😂，感觉大佬yxc思路是有一点点略过了。
q里面装的是数组a的下标，hh指的是当前滑动窗口最小值的下标存储在q中的哪个位置，tt指的是当前滑动窗口（去除掉左边比右边大的数后，严格单调上升）的尾端（即当前滑动窗口转换成严格单调上升后最大数的下标）在q的哪个位置。
N = 1000010
# 如果队列中存在两个元素，满足 a[i] >= a[j] 且 i < j，那么无论在什么时候我们都不会取
# a[i] 作为最小值了，所以可以直接将 a[i] 删掉；
# 此时队列中剩下的元素严格单调递增，所以队头就是整个队列中的最小值，可以用 O(1) 的时间找到；
# 为了维护队列的这个性质，我们在往队尾插入元素之前，先将队尾大于等于当前数的元素全部弹出即可；
# 这样所有数均只进队一次，出队一次，所以时间复杂度是 O(n) 的。
if __name__ == '__main__':
n, k = map(int, input().split())
hh, tt = 0, -1
arr, q = [int(x) for x in input().split()], [0]*N
for i in range(n):
if i-k+1 > q[hh]: hh+=1 # i-k+1是新的队头：解决队首已经出窗口的问题;
while hh<=tt and arr[i]<=arr[q[tt]]: tt-=1 # 解决队尾与当前元素a[i]不满足单调性的问题;
tt, q[tt] = tt+1, i # 将当前元素下标加入队尾;
if i+1 >= k: print(arr[q[hh]], end=' ') # 如果满足条件则输出结果;
hh, tt = 0, -1
print()
for i in range(n):
if i-k+1 > q[hh]: hh+=1
while hh<=tt and arr[i]>=arr[q[tt]]: tt-=1
tt, q[tt] = tt+1, i
if i+1 >= k: print(arr[q[hh]], end=' ')
#########################################################################################
# acwing 154. 滑动窗口
# q里面装的是a数组的下标（计算范围k内最小和最大值所用到的），这道题的核心思想是
# 当前维护的这个范围内是递增的，有个问题是，我们只看见hh在超出范围的时候改变进
# 行+1，假如当前序列为6 4 1 2 3，hh还没超出范围，怎么不改变呢。实际上tt在改变，
# 从而改变了hh。 由于维护的是一个队列，所以hh=0,tt=-1
N = 1000010
if __name__ == '__main__':
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
q, hh, tt = [0] * N, 0, -1
for i in range(n):
while hh<=tt and i-k+1>q[hh]: hh+=1
while hh<=tt and a[q[tt]]>=a[i]: tt-=1
tt, q[tt] = tt+1, i
if i-k+1>=0: print(a[q[hh]], end=" ")
print()
q, hh, tt = [0] * N, 0, -1
for i in range(n):
while hh<=tt and i-k+1>q[hh]: hh+=1
while hh<=tt and a[q[tt]]<=a[i]: tt-=1
tt, q[tt] = tt+1, i
if i-k+1>=0: print(a[q[hh]], end=" ")Day18.(2021.10.31)
KMP算法
Next[i]=j是指，模板串中以i为终点的长度为j的这段和模板串1，j的部分是相等的，即p[1,j]=p[i-j+1,i]
移动的时候，其实就是找以这个点（竖着的那条绿色的线）为终点的后缀和前缀相等的时候（将模板串p往后移）
模式串S和模板串P的匹配过程是清楚了，但是Next数组的求取过程还没不能够很清楚明了的知道求解过程。
# acwing 831. KMP字符串
if __name__ == '__main__':
n, p, m, s = int(input()), " " + input(), int(input()), " " + input()
ne = [0]*(n+1)
j = 0
for i in range(2,n+1):
while j and p[i]!=p[j+1]: j=ne[j]
if p[i]==p[j+1]: j+=1
ne[i]=j
j = 0
for i in range(1,m+1):
while j and s[i]!=p[j+1]: j=ne[j]
if s[i]==p[j+1]: j+=1
if j==n:
print(i-n, end=' ')
j=ne[j]Day19.(2021.11.01)
# 自己写的代码，遍历一个数组，然后用二分查找 O(nlogn)
# acwing 800. 数组元素的目标和
n,m,x = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
def binary_search(x, arr, n):
l,r = 0, n-1
while l<r:
mid = (l+r)//2
if arr[mid]>=x: r=mid
else: l=mid+1
if arr[l]==x:
return (True,l)
else:return (False,)
if n<m:
for i in range(n):
p = binary_search(x-a[i], b, n)
if p[0]:
print(i,p[1])
else:
for i in range(m):
p = binary_search(x-b[i], a, m)
if p[0]:
print(p[1],i)
yxc官方思路，双指针的体就是先暴力解，之后再找单调性进行优化。
其中i向右移动，j向左移动。
# acwing 800. 数组元素的目标和
n,m,x = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
j=m-1
for i in range(n):
while j>=0 and a[i] + b[j] >x: j-=1
if a[i]+b[j]==x:
print(i,j)
breakAcWing 2816.判断子序列
双指针做法：从前往后扫描数组B，判断B的当前数和A的当前数是否一样，如果一样的话就将B的当前数匹配到A的当前数，当遍历完B数组后，发现A数组中每个数都找到了与他匹配的数的话，就输出YES
双指针做法可以找到一种匹配方式
现在我们来证明，若存在一种匹配，双指针算法一定可以找出这种匹配。（这个就建议直接看原视频了哈😂）
# acwing 2816. 判断子序列
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
i,j = 0,0
while i<n and j<m:
if b[j]==a[i]:
i+=1
j+=1
else:
j+=1
if i == n:
print("Yes")
else:
print("No")Day19.(2021.11.02)
Trie树可以高效地存储和查找字符串
需要把所有单词的结尾都标记一下。
# acwing 835. Trie字符串统计
# idx存储的是当前用到了哪个节点，cnt存储的是以x节点为结束的字符串有多少个
# Trie树中有个二维数组son[N][26]，表示当前结点的儿子，如果没有的话，
# 可以等于++idx。Trie树本质上是一颗多叉树，对于字母而言最多有26个子结点。
# 所以这个数组包含了两条信息。比如：son[1][0]=2
# 表示1结点的一个值为a的子结点为结点2。如果son[1][0] = 0，
# 则意味着没有值为a子结点。这里的son[N][26]相当于链表中的ne[N]。
N = 100001
def insert(s):
global idx
p = 0
for i in range(len(s)):
u = ord(s[i]) - ord('a')
if not son[p][u]:
son[p][u], idx = idx, idx+1
p = son[p][u]
cnt[p] += 1
def query(s):
p = 0
for i in range(len(s)):
u = ord(s[i]) - ord('a')
if not son[p][u]:
return 0
p = son[p][u]
return cnt[p]
if __name__ == '__main__':
n = int(input())
son, cnt, idx = [[0]*26 for _ in range(N)], [0]*N, 1
for _ in range(n):
oprt, s = input().split()
if oprt == 'I': insert(s)
else: print(query(s))并查集：1.将两个集合合并 2.询问两个元素是否在一个集合当中（暴力做法不能够同时很好的完成这两个做法）
操作：用树的形式来维护每一个集合，根节点的编号就是当前集合的编号，每个点都存储它的父节点是谁。
这里实现了最常用路径压缩优化，一般不写按秩合并这个优化（用处不大）
# acwing 836. 合并集合
N = 100010
n,m = map(int, input().split())
p = [x for x in range(N)]
def find(x):
if p[x]!=x: p[x]=find(p[x])
return p[x]
for _ in range(m):
op,a,b = input().split()
if op == "M":
p[find(int(a))] = find(int(b))
else:
if find(int(a)) == find(int(b)): print("Yes")
else: print("No")在并查集的这个操作过程中，额外维护一些变量
只有根节点的size是有意义的，只需要在合并操作的时候更新size集合就可以了
# acwing 837. 连通块中的数量
n,m = map(int, input().split())
p = [x for x in range(n+1)]
size = [1]*(n+1)
def find(x):
if p[x]!=x:
p[x]=find(p[x])
return p[x]
for _ in range(m):
op, *px = input().split()
if op == "C":
a, b = int(px[0]), int(px[1])
if find(a)==find(b): continue
size[find(b)] += size[find(a)]
p[find(a)] = p[find(b)]
elif op == "Q1":
a, b = int(px[0]), int(px[1])
if find(a) == find(b): print("Yes")
else: print("No")
else:
a = int(px[0])
print(size[find(a)])Day20.(2021.11.03)
堆是一个完全二叉树，小根堆（每一个点都是小于等于左右儿子的），STL的堆就是优先队列
前面三个是stl直接实现了的，后两个没有直接实现
堆排序只需要把最小值输出，然后删除最小值，所以只需要实现down操作就可以了。
堆的建立操作的复杂度是O（n），具体可以看下图分析：
# acwing 838. 堆排序
n,m = map(int, input().split())
h = [0] + list(map(int, input().split()))
def dowm(k):
global n
u = k
if 2*k<=n and h[u]>h[2*k]: u=2*k
if 2*k+1<=n and h[u]>h[2*k+1]: u=2*k+1
if u!=k:
h[k], h[u] = h[u], h[k]
dowm(u)
for i in range(n//2, 0, -1):
dowm(i)
for _ in range(m):
print(h[1], end=" ")
h[1] = h[n]
n -= 1
dowm(1)下面是模拟堆需要的额外操作，如删除和修改第k个数。
# p是指下标(pointer)，h是指堆(heap)
# ph[index] = size 指的是第index个插入的数在堆中的size位置
# hp[size] = index是指堆中size位置的
# 元素是第index个插入的
# 这是一个复杂版的，带映射的一个操作
# acwing 839. 模拟堆
N = 100010
n = int(input())
h, hp, ph, size, index = [0]*N, [0]*N, [0]*N, 0, 0
def down(k):
global size
u = k
if 2*k<=size and h[u]>h[2*k]: u=2*k
if 2 * k + 1 <= size and h[u] > h[2 * k+1]: u = 2 * k+1
if u!=k:
heap_swap(k,u)
down(u)
def up(k):
global size
while k//2 and h[k//2]>h[k]:
heap_swap(k//2,k)
k //= 2
def heap_swap(i,j):
# 原本堆中第i个位置是第hp[i]次插入的，
# 由于改变了堆中的顺序，现在第hp[i]次插入的是j
# 原本这个位置记录的插入的是i，现在要改为j
ph[hp[i]], ph[hp[j]] = j, i
# 堆当中的第i个数和第j个数分别是第几次插入的，直接看
# 可能会看晕，先只看右边，右边的含义是第几次插入，左边
# 虽然和右边一样，但是左边是表示位置
# 堆中第i个位置，是第几次插入的
hp[i],hp[j] = hp[j],hp[i]
# 交换堆当中的第i和第j个数
h[i],h[j] = h[j],h[i]
for _ in range(n):
op, *px = input().split()
if op == "I":
x = int(px[0])
size, index = size+1, index+1
ph[index], hp[size] = size, index
h[size] = x
up(size)
elif op == "PM":
print(h[1])
elif op == "DM":
heap_swap(1,size)
size -= 1
down(1)
elif op == "D":
k = int(px[0])
k = ph[k]
heap_swap(k, size)
size -= 1
down(k)
up(k)
else:
k, x = map(int, px)
k = ph[k]
h[k] = x
down(k)
up(k)Day21.(2021.11.04)
# acwing 3302. 表达式求值
# Python 向0取整用int
# 后缀（后序遍历：左右根）表达式不需要括号，中缀（中序遍历：左根右）
# 表达式需要括号（所有的叶节点都是数字，内部节点都是运算符）
# 往上走，没有遍历完，往下走，遍历完了。
# 往上走，当前运算符的优先级低于前面的那个运算符
# 如何判断某棵子树被遍历完 等价于 当前运算符优先级小于等于上一个运算符优先级
# 遇到右括号），就从右往左计算
# eval用末尾的运算符去操作末尾的两个数
# acwing 3302. 表达式求值
# 如果栈顶的运算符优先级低，新运算符直接入栈
# 否则，先出栈计算，新运算符再入栈
# 判断顺序：数字、左括号、右括号和运算符
pr = {'+':1, '-':1, '*':2, '/':2}
def compute():
b, a, op = num_stack.pop(), num_stack.pop(), op_stack.pop()
if op == '+': a += b
elif op == '-': a -= b
elif op == '*': a *= b
else: a = int(a/b)
num_stack.append(a)
if __name__ == '__main__':
arr = input()
num_stack, op_stack, i = [], [], 0
while i<len(arr):
if str.isdigit(arr[i]):
num = arr[i]
while i+1<len(arr) and str.isdigit(arr[i+1]):
i += 1
num += arr[i]
num_stack.append(int(num))
elif arr[i] == '(': op_stack.append('(')
elif arr[i] == ')':
while op_stack[-1] != '(':
compute()
op_stack.pop()
else:
while op_stack and op_stack[-1] != '(' and pr[arr[i]] <= pr[op_stack[-1]]:
compute()
op_stack.append(arr[i])
i += 1
while op_stack: compute()
print(num_stack[-1])Day22.(2021.11.05)
hash这个操作是指把一个比较大的数据范围映射到一个比较小的范围。算法题中的hash表一般只有添加和查询操作，没有删除操作。（就算有也不是真的删，而是开个额外数组，打个标记）
取余的数要选择质数且尽可能要离2的整数次方远（这样的话冲突的概率最小）
# acwing 840. 模拟散列表
# 拉链法
# 这道题涉及到了Python和C++的%操作，具体不同可以看我的另一篇博客 Python和C++的%（取模与取余操作）
# 本题主要是保证取出来的数要是个正数，且在范围类。Python的%是向下取整，当a小于0的时候，根据
# 公式，最后的出来的一定是个大于0的数。所以可以直接用代码k = x % N，代替(x%N+N)%N，当然
# 也可以手动实现取余操作，然后mod((mod(x,N)+N),N)
N = 100003
# 这个h就有点相当于是头节点，从它找到第一个挂在它上面的节点
h, e, ne, idx = [-1]*N, [0]*N, [0]*N, 0
n = int(input())
def prime(x):
for i in range(2,x//2):
if x%i==0:
return False
return True
def mod(a,n):
return a-n*int(a/n)
def insert(x):
global idx
k = mod((mod(x,N)+N),N)
#k = x%N
e[idx] = x
ne[idx] = h[k]
h[k] = idx
idx += 1
def query(x):
global idx
k = mod((mod(x,N)+N),N)
#k = x % N
index = h[k]
while index != -1:
if e[index] == x:
print("Yes")
return
index = ne[index]
print("No")
if __name__ == "__main__":
# 求出大于10^5的最小质数是多少
num_prime = 100001
while not prime(num_prime):
num_prime += 1
for _ in range(n):
op, px = input().split()
px = int(px)
if op == "I":
insert(px)
else: query(px)
开放寻址法
开放寻址法一般定义数组长度为最大操作次数的的2-3倍（同样要为质数），一般设定最大值为0x33f3f3f3f。
# acwing 840. 模拟散列表
N, null = 200003, 0x3f3f3f3f
h = [null]*N
def mod(a,n):
return a-n*int(a/n)
def find(x):
k = mod(mod(x,N)+N,N)
while h[k]!=null and h[k]!=x:
k+=1
if k==N: k=0
return k
if __name__ == '__main__':
n = int(input())
for _ in range(n):
op, px = input().split()
px = int(px)
k = find(px)
if op=="I": h[k]=px
else:
if h[k]==null: print("No")
else: print("Yes")Day23.(2021.11.06)
字符串hash（字符串前缀hash）
这里假定模的值是2^64，但是我用Python实验的时候发现不得行。（存有疑惑，按照y总讲的，不应该取个质数么，然后我试了个质数91815541可以）
但C++ 中unsigned long long相当于直接对2^64取模了，所以源代码中就没有相应的取模操作。
# acwing 841. 字符串哈希
# h 数组是字符串前缀的hash值
# P是指进位需要乘的数（P[1]表示进一位，在十进制中相当于是乘以10）
N, P, M = 100010, 131, 91815541
def get(l, r):
return (h[r] - h[l - 1] * p[r - l + 1])%M
if __name__ == '__main__':
h, p = [1] * N, [0] * N
n, m = map(int, input().split())
s = " " + input()
for i in range(1, n + 1):
p[i] = (p[i - 1] * P)%M
h[i] = (h[i - 1] * P + ord(s[i]))%M
for _ in range(m):
l1, r1, l2, r2 = map(int, input().split())
if get(l1, r1) == get(l2, r2): print("Yes")
else: print("No")
#----------------------------------------------------------------------------------------
N, P, M = 100010, 131, 91815541
def mod(a,b):
return a-b*int(a/b)
def get(l,r):
return mod(mod(h[r]-h[l-1]*p[r-l+1],M)+M,M)
if __name__ == '__main__':
h, p = [0]*N, [0]*N
n, m = map(int, input().split())
p[0]=1
s = " " + input()
for i in range(1, n+1):
p[i] = mod(mod(p[i-1]*P,M)+M,M)
h[i] = mod(mod(h[i-1]*P+ord(s[i]),M)+M,M)
for _ in range(m):
l1,r1,l2,r2 = map(int, input().split())
if get(l1,r1)==get(l2,r2): print("Yes")
else: print("No")Day23.(2021.11.08)
vector（变长数组），倍增的思想，支持比较运算（按字典序）
定义：：
vector <int> a; 定义：一个vector数组a
vector <int> a(10); 定义：一个长度为10的vector数组a
vector <int> a(10,3); 定义：一个长度为10的vector数组a，并且所有元素都为3
常用函数：：
size(); 返回元素个数
empty(); 返回是否是空
clear(); 清空
front(); 返回vector的第一个数
back(); 返回vector的最后一个数
push_back(); 向vector的最后插入一个数
pop_back(); 把vector的最后一个数删掉
begin(); vector的第0个数
end(); vector的最后一个的数的后面一个数
倍增的思想：
系统为某一程序分配空间是，所需时间，与空间大小无关，与申请次数有关
遍历方法
假设有个vector <int> a;
第一种：
for(int i = 0;i < a.size();i ++) cout<<a[i]<<" ";
第二种：
for(vector <int>::iterator i = a.begin();i != a.end();i ++) cout<<*i<<" "; vector <int>::iterator可以写为auto
第三种：
for(auto x : a) cout<<x<<" ";
pair，支持比较运算，以first为第一关键字，以second为第二关键字（按字典序）
定义：：
pair <类型,类型> 变量名; 两个类型可以不同
初始化方式：
假设有个pair <int,string> p;
第一种：
p = make_pair(10,"abc");
第二种：
p = {10,"abc");
常用函数：：
first(); 第一个元素
second(); 第二个元素
string（字符串）
常用函数：：
substr(); 返回每一个子串
c_str(); 返回这个string对应的字符数组的头指针
size(); 返回字母个数
length(); 返回字母个数
empty(); 返回字符串是否为空
clear(); 把字符串清空
queue（队列）
定义：：
queue <类型> 变量名;
常用函数：：
size(); 这个队列的长度
empty(); 返回这个队列是否为空
push(); 往队尾插入一个元素
front(); 返回队头元素
back(); 返回队尾元素
pop(); 把队头弹出
注意：队列没有clear函数！！！
清空：
变量名 = queue <int> ();
priority_queue（优先队列，堆）
注意：默认是大根堆！！！
定义：：
大根堆：priority_queue <类型> 变量名;
小根堆：priority_queue <类型,vecotr <类型>,greater <类型>> 变量名
常用函数：
size(); 这个堆的长度
empty(); 返回这个堆是否为空
push();往堆里插入一个元素
top(); 返回堆顶元素
pop(); 弹出堆顶元素
注意：堆没有clear函数！！！
stack（栈）
常用函数：
size(); 这个栈的长度
empty(); 返回这个栈是否为空
push(); 向栈顶插入一个元素
top(); 返回栈顶元素
pop(); 弹出栈顶元素
deque（双端队列）
常用函数：
size(); 这个双端队列的长度
empty(); 返回这个双端队列是否为空
clear(); 清空这个双端队列
front(); 返回第一个元素
back(); 返回最后一个元素
push_back(); 向最后插入一个元素
pop_back(); 弹出最后一个元素
push_front(); 向队首插入一个元素
pop_front(); 弹出第一个元素
begin(); 双端队列的第0个数
end(); 双端队列的最后一个的数的后面一个数
set，map，multiset，multimap 基于平衡二叉树（红黑树），动态维护有序序列
set/multiset
注意：set不允许元素重复，如果有重复就会被忽略，但multiset允许！！！
常用函数：
size(); 返回元素个数
empty(); 返回set是否是空的
clear(); 清空
begin(); 第0个数，支持++或--，返回前驱和后继
end(); 最后一个的数的后面一个数，支持++或--，返回前驱和后继
insert(); 插入一个数
find(); 查找一个数
count(); 返回某一个数的个数
erase();
（1）输入是一个数x，删除所有x O(k + log n)
（2）输入一个迭代器，删除这个迭代器
lower_bound(x); 返回大于等于x的最小的数的迭代器
upper_bound(x); 返回大于x的最小的数的迭代器
map/multimap
常用函数：
insert(); 插入一个数，插入的数是一个pair
erase();
（1）输入是pair
（2）输入一个迭代器，删除这个迭代器
find(); 查找一个数
lower_bound(x); 返回大于等于x的最小的数的迭代器
upper_bound(x); 返回大于x的最小的数的迭代器
unordered_set，unordered_map，unordered_muliset,unordered_multimap 基于哈希表
和上面类似，增删改查的时间复杂度是O(1)
不支持lower_bound()和upper_bound()
bitset 压位
定义：
bitset <个数> 变量名;
支持：
~，&，|，^
>>，<<
==，!=
[]
常用函数：
count(); 返回某一个数的个数
any(); 判断是否至少有一个1
none(); 判断是否全为0
set(); 把所有位置赋值为1
set(k,v); 将第k位变成v
reset(); 把所有位变成0
flip(); 把所有位取反，等价于~
flip(k); 把第k位取反
与C++ STL所对应，这里我们来下Python常用的容器。
1. Counter （数数和排序）
# 比如分析文本中每个单词出现过的次数，并只保留出现次数最高的若干个。
# Counter是一个dict子类，主要是用来对你访问的对象的频率进行计数。
# elements()：返回一个迭代器，每个元素重复计算的个数，如果一个元素的计数小于1,就会被忽略。
# most_common([n])：返回一个列表，提供n个访问频率最高的元素和计数
# subtract([iterable-or-mapping])：从迭代对象中减去元素，输入输出可以是0或者负数
# update([iterable-or-mapping])：从迭代对象计数元素或者从另一个 映射对象 (或计数器) 添加。
# 统计字符出现的次数
>>> import collections
>>> collections.Counter('hello world')
Counter({'l': 3, 'o': 2, 'h': 1, 'e': 1, ' ': 1, 'w': 1, 'r': 1, 'd': 1})
# 统计单词数
>>> collections.Counter('hello world hello world hello nihao'.split())
Counter({'hello': 3, 'world': 2, 'nihao': 1})
>>> c = collections.Counter('hello world hello world hello nihao'.split())
>>> c
Counter({'hello': 3, 'world': 2, 'nihao': 1})
# 获取指定对象的访问次数，也可以使用get()方法
>>> c['hello']
3
>>> c = collections.Counter('hello world hello world hello nihao'.split())
# 查看元素
>>> list(c.elements())
['hello', 'hello', 'hello', 'world', 'world', 'nihao']
# 追加对象，或者使用c.update(d)
>>> c = collections.Counter('hello world hello world hello nihao'.split())
>>> d = collections.Counter('hello world'.split())
>>> c
Counter({'hello': 3, 'world': 2, 'nihao': 1})
>>> d
Counter({'hello': 1, 'world': 1})
>>> c + d
Counter({'hello': 4, 'world': 3, 'nihao': 1})
# 减少对象，或者使用c.subtract(d)
>>> c - d
Counter({'hello': 2, 'world': 1, 'nihao': 1})
# 清除
>>> c.clear()
>>> c
Counter()
# 除此之外，它的构造函数还接收dict类型。我们可以直接通过一个value是int类型的dict来初始化一个
# Counter，比如：
c = Counter({'apple': 5, 'pear': 4})
c = Counter(apple=4, pear=3)
2. defaultdict（主要可以解决两个问题）
第一、当key为空的时候，dict会抛出异常，当然也可以用dict.get(key,None)来解决这解决这个问题。
第二、当key存在重复，我们希望将相同value存到一个list中。
collections.defaultdict(default_factory)为字典的没有的key提供一个默认的值。参数应该是一个函数，当没有参数调用时返回默认值。如果没有传递任何内容，则默认为None。
# defaultdict(None, {})
d = collections.defaultdict()
defaultdict的一个典型用法是使用其中一种内置类型(如str、int、list或dict)作为默认工厂，这些内置类型在没有参数调用时返回空类型。
# defaultdict(<class 'str'>, {})
e = collections.defaultdict(str)
# ''
e['hello']
# 使用int作为default_factory的例子
from collections import defaultdict
fruit = defaultdict(int)
# defaultdict(<class 'int'>, {'apple': 2})
fruit['apple'] += 2
# 0
fruit['banana'] # 没有对象时，返回0
# defaultdict(<class 'int'>, {'apple': 2, 'banana': 0})
fruit
# 使用list作为default_factory的例子
s = [('NC', 'Raleigh'), ('VA', 'Richmond'), ('WA', 'Seattle'), ('NC', 'Asheville')]
d = collections.defaultdict(list)
for k,v in s:
d[k].append(v)
# defaultdict(<class 'list'>, {'NC': ['Raleigh', 'Asheville'], 'VA': ['Richmond'], 'WA': # ['Seattle']})
d
3. deque（双端队列）
# 在日常的使用当中，真正用到双端队列的算法其实不太多。大多数情况下我们使用deque主要有两个原 # 因，第一个原因是deque收到GIL的管理，它是线程安全的。而list则没有GIL锁，因此不是线程安全的。 # 也就是说在并发场景下，list可能会导致一致性问题，而deque不会。另一个原因是deque支持固定长度，# 当长度满了之后，当我们继续append时，它会自动弹出最早插入的数据。并且deque优化了从左端插入和 # 弹出的时间复杂度（现在都是O(1)）
# append(x)：添加x到右端
# appendleft(x)：添加x到左端
# clear()：清楚所有元素，长度变为0
# copy()：创建一份浅拷贝
# count(x)：计算队列中个数等于x的元素
# extend(iterable)：在队列右侧添加iterable中的元素
# extendleft(iterable)：在队列左侧添加iterable中的元素，注：在左侧添加时，iterable参数的顺序# 将会反过来添加
# index(x[,start[,stop]])：返回第 x 个元素（从 start 开始计算，在 stop 之前）。返回第一个匹 # 配，如果没找到的话，升起 ValueError 。
# insert(i,x)：在位置 i 插入 x 。注：如果插入会导致一个限长deque超出长度 maxlen 的话，就升起 # 一个 IndexError 。
# pop()：移除最右侧的元素
# popleft()：移除最左侧的元素
# remove(value)：移去找到的第一个 value。没有抛出ValueError
# reverse()：将deque逆序排列。返回 None 。
# maxlen：队列的最大长度，没有限定则为None。
>>> from collections import deque
>>> d = deque(maxlen=10)
>>> d
deque([], maxlen=10)
>>> d.extend('python')
>>> [i.upper() for i in d]
['P', 'Y', 'T', 'H', 'O', 'N']
>>> d.append('e')
>>> d.appendleft('f')
>>> d
deque(['f', 'p', 'y', 't', 'h', 'o', 'n', 'e'], maxlen=10)
4. namedtuple（命名元组）
# namedtuple很特殊，它涉及到元编程的概念。在常见的面向对象当中。我们都是定义类，然后通过类的构# 造函数来创建实例。而元编程指的是我们定义元类，根据元类创建出来的并不是一个实例，而是一个类。
# namedtuple是一个非常简单的元类，通过它我们可以非常方便地定义我们想要的类。它的第一个参数是命# 名元组的构造器
# 如果我们要定义一个学生类，这个类中有name, score, age三个字段，则这个类会写成：
class Student:
def __init__(self, name=None, score=None, age=None):
self.name = name
self.score = score
self.age = age
# 这还只是粗略的写法，如果考虑规范，还需要定义property等注解，又需要很多代码。如果我们使用 # namedtuple可以简化这个工作，我们来看代码：
from collections import namedtuple
Student = namedtuple('Student', ['name', 'score', 'age'])
# 这个是实例
student = Student(name='xiaoming', score=99, age=10)
print(student.name)
# 通过使用namedtuple，我们只需要一行就定义了一个类，但是这样定义的类是没有缺省值的，但是
# namedtuple很强大，我们可以通过传入defaults参数来定义缺省值。
Student = namedtuple('Student', ['name', 'score', 'age'], defaults=(0, 0))
# 可以注意到，虽然我们定义了三个字段，但是我们只设置了两个缺省值。在这种情况下，namedtuple会自
# 动将缺失值匹配上score和age两个字段。因为在Python的规范当中，必选参数一定在可选参数前面。所以
# nuamdtuple会自动右对齐。
5. OrderedDict（有序字典）
# Python字典中的键的顺序是任意的:它们不受添加的顺序的控制。collections.OrderedDict类提供了保
# 留他们添加顺序的字典对象。
>>> from collections import OrderedDict
>>> o = OrderedDict()
>>> o['key1'] = 'value1'
>>> o['key2'] = 'value2'
>>> o['key3'] = 'value3'
>>> o
OrderedDict([('key1', 'value1'), ('key2', 'value2'), ('key3', 'value3')])
# 如果在已经存在的key上添加新的值，将会保留原来的key的位置，然后覆盖value值。
6. ChianMap
# 一个 ChainMap 将多个字典或者其他映射组合在一起，创建一个单独的可更新的视图。 如果没有 maps
# 被指定，就提供一个默认的空字典 。ChainMap是管理嵌套上下文和覆盖的有用工具。
>>> from collections import ChainMap
>>> d1 = {'apple':1,'banana':2}
>>> d2 = {'orange':2,'apple':3,'pike':1}
>>> combined_d = ChainMap(d1,d2)
>>> reverse_combind_d = ChainMap(d2,d1)
>>> combined_d
ChainMap({'apple': 1, 'banana': 2}, {'orange': 2, 'apple': 3, 'pike': 1})
>>> reverse_combind_d
ChainMap({'orange': 2, 'apple': 3, 'pike': 1}, {'apple': 1, 'banana': 2})
>>> for k,v in combined_d.items():
... print(k,v)
...
pike 1
apple 1
banana 2
orange 2
>>> for k,v in reverse_combind_d.items():
... print(k,v)
...
pike 1
apple 3
banana 2
orange 2DFS深度优先搜索
# DFS 的两个重要概念 回溯（要记得恢复现场）和剪枝
# 思路比较奇怪的一般用深度优先搜索
# 全排列可用DFS
# 这里不用path[u]=0，因为会被覆盖
# acwing 842.排列数字
N = 10
path, flag = [0]*N, [False]*N
def dfs(u):
if u==n:
for i in range(n):
print(path[i], end=" ")
print()
return
for i in range(1,n+1):
if not flag[i]:
path[u]=i
flag[i]=True
dfs(u+1)
flag[i]=False
if __name__ == '__main__':
n = int(input())
dfs(0)八皇后问题
# acwing 843. n-皇后问题
# u代表行，i代表列，递归行，每行看每列
N= 20
def dfs(u):
if u==n:
for i in range(n):
print("".join(grid[i]))
print()
return 0
for i in range(n):
if not col[i] and not dg[n+u-i] and not udg[u+i]:
col[i], dg[n+u-i], udg[u+i] = True, True, True
grid[u][i]='Q'
dfs(u+1)
grid[u][i] = '.'
col[i], dg[n + u - i], udg[u + i] = False, False, False
if __name__ == '__main__':
n = int(input())
grid = [['.']*n for _ in range(n)]
col, dg, udg = [False]*N, [False]*N, [False]*N,
dfs(0)
# acwing 843. n-皇后问题
# 按网格搜索
N = 20
def dfs(x,y,s):
if y==n:
x+=1
y=0
if x==n:
if s==n:
for i in range(n):
print(''.join(grid[i]))
print()
return 0
dfs(x,y+1,s)
if not row[x] and not col[y] and not dg[n+y-x] and not udg[x+y]:
row[x], col[y], dg[n+y-x], udg[x+y] = True, True, True, True
grid[x][y] = 'Q'
dfs(x,y+1,s+1)
grid[x][y] = '.'
row[x], col[y], dg[n + y - x], udg[x + y] = False, False, False, False
if __name__ == '__main__':
n = int(input())
grid = [['.']*n for _ in range(n)]
row, col, dg, udg = [False]*N, [False]*N, [False]*N, [False]*N
dfs(0,0,0)
Day24.(2021.11.09)
BFS（广度搜索优先）
最短路包含动态规划问题（DP是没有环的最短路），只有当所有边的权重都一样的时候，才可以用BFS求最短路问题。
一般模板：
queue <- 初始化
while queue
{
t<-队头
扩展t
}# acwing 844. 走迷宫
# 注释部分存储路径
# 以前是开个数组来存有没有被访问过，这里直接用存距离的数组来一并存储这个信息
from collections import deque
directions = [(1,0), (-1,0),(0,1),(0,-1)]
def bfs():
while q:
tmp = q.popleft()
for direction in directions:
x,y = tmp[0]+direction[0], tmp[1]+direction[1]
if x>=0 and x<n and y>=0 and y<m and g[x][y]==0 and d[x][y]==-1:
d[x][y] = d[tmp[0]][tmp[1]]+1
q.append((x,y))
# prev[x][y] = tmp
return d[-1][-1]
# def path():
# print(n-1,m-1)
# x,y = prev[-1][-1]
# while x or y:
# print(x,y)
# x,y = prev[x][y]
# print(0,0)
if __name__ == '__main__':
n,m = map(int, input().split())
g,d,q = [], [[-1]*m for _ in range(n)], deque()
# prev = [[0]*m for _ in range(n)]
for _ in range(n):
g.append([int(x) for x in input().split()])
d[0][0] = 0
q.append((0,0))
print(bfs())
# path()
树的深度遍历
首先来看树（图）的基本深度优先遍历思路
每个点只访问一次，所以需要一个先标记这个点被搜索过了。然后访问这个点的子节点（如果子节点没被访问过）
# acwing 846. 树的重心
N = 100010
# 将重心删除后，剩余各个连通块中点数的最大值，先初始化为最大值
ans = N
def add(a,b):
global idx
e[idx] = b
ne[idx] = h[a]
h[a] = idx
idx += 1
# 深度优先遍历一般都有个for循环，
# 然后再在for循环中深度遍历
def dfs(u):
global ans
# 标记访问过树节点u
st[u] = True
# sum：以u为根的树的节点数（包括u）
# res：删除树节点u后，最大连通子图（子树）节点数
sum, res = 1, 0
# 找到存储与u节点相连的树节点的存储节点
# 这里不用担心返回子树会返回父节点向上的节点数（因为是无向图嘛，也走得上去）
# 因为是从上往下搜索的，所以父节点肯定会被标记过
i = h[u]
while i!=-1:
# 树节点j为与树节点u直接相连的树节点
j = e[i]
# 如果树节点j没有被访问过
if not st[j]:
# 以树节点u的子节点j为根的树的大小
s = dfs(j)
# 求最大连通子图（子树）的大小
res = max(res,s)
# 先把这棵子树的节点数加上
sum += s
# 继续访问树节点u的下一棵子树
i=ne[i]
# 现在把以u为根的所有子树的连通数情况求出来了，但是还要将
# 当前结果和整棵树除掉u这棵子树的数量进行对比
res = max(res,n-sum)
# 比较删除当前树节点的最大连通子图节点数和
# 删除其它节点得出的最大连通子图节点数
ans = min(ans,res)
return sum
if __name__ == '__main__':
h, e, ne, idx = [-1]*N, [0]*2*N, [0]*2*N, 0
# 记录某个树节点是否被访问过
st = [False]*N
n = int(input())
# 无向图，所以要从a->b,b->a都要插入一条边
for i in range(n-1):
a,b = map(int, input().split())
add(a,b)
add(b,a)
dfs(1)
print(ans)# acwing 847.图中点的层次
from collections import deque
N = 100010
def bfs():
while q:
tmp = q.popleft()
i = h[tmp]
while i!=-1:
j = e[i]
if d[j]==-1:
d[j] = d[tmp]+1
q.append(j)
i = ne[i]
return d[n]
def add(a,b):
global idx
e[idx] = b
ne[idx] = h[a]
h[a] = idx
idx += 1
if __name__ == '__main__':
n, m = map(int, input().split())
h, e, ne, idx = [-1]*N, [0]*N, [0]*N, 0
q, d = deque(), [-1]*N
q.append(1)
d[1] = 0
for _ in range(m):
a,b = map(int, input().split())
add(a,b)
print(bfs())Day25.(2021.11.10)
# acwing 143.最大异或对
M = 3000000
son, idx = [[0]*2 for _ in range(M)], 0
def insert(x):
global idx
p = 0
for i in range(30,-1,-1):
u = (x>>i)&1
if not son[p][u]:
idx += 1
son[p][u]=idx
p = son[p][u]
def query(x):
res, p = 0,0
for i in range(30,-1,-1):
u = (x>>i)&1
if son[p][1-u]:
res = res + (1<<i)
p = son[p][1-u]
else:
p = son[p][u]
return res
if __name__ == '__main__':
n = int(input())
a = [int(x) for x in input().split()]
for i in range(n):
insert(a[i])
res = 0
for i in range(n):
res = max(res, query(a[i]))
print(res)有向无环图的拓扑序列（就是图的宽度优先搜索的应用）（有向无环图又称为拓扑图）
若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列。
# acwing 848. 有向图的拓扑序列
from collections import deque
N = 100010
h, e, ne, idx = [-1]*N, [0]*N, [0]*N, 0
# d装的是入度数
q, d, ans = deque(), [0]*N, []
def topsort():
for i in range(1,n+1):
if not d[i]:
q.append(i)
while q:
tmp = q.popleft()
ans.append(tmp)
i = h[tmp]
while i!=-1:
j = e[i]
d[j]-=1
if d[j]==0: q.append(j)
i=ne[i]
return len(ans)==n
def insert(a,b):
global idx
e[idx] = b
ne[idx] = h[a]
h[a] = idx
idx += 1
if __name__ == '__main__':
n, m = map(int, input().split())
for i in range(m):
a, b = map(int, input().split())
insert(a,b)
d[b] += 1
if topsort(): print(" ".join(map(str, ans)))
else: print("-1")Day26.(2021.11.12)
这道题有两种做法，这里的是并查集维护额外信息。
这道题路径压缩和合并集合进行赋值的时候十分不好理解。
# acwing 240. 食物链
def find(x):
if p[x] != x:
t = find(p[x])
d[x] += d[p[x]]
p[x] = t
return p[x]
if __name__ == '__main__':
n, k = map(int, input().split())
p, d, ans = [x for x in range(n+1)], [0] * (n+1), 0
for _ in range(k):
op, x, y = map(int, input().split())
if x > n or y > n:
ans += 1
continue
px, py = find(x), find(y)
if op == 1:
if px == py:
if (d[x]-d[y])%3: ans += 1
else:
p[px] = py
d[px] = d[y] - d[x]
else:
if px == py:
if (d[x]-d[y]-1)%3: ans += 1
else:
p[px] = py
d[px] = d[y] - d[x] + 1
print(ans)
#-------------------------------------------------------------------------
# acwing 240. 食物链
N = 500010
def mod(a,b):
return a-b*int(a/b)
def find(x):
if p[x]!=x:
t = find(p[x])
d[x]+=d[p[x]]
p[x]=t
return p[x]
if __name__ == '__main__':
n,k = map(int, input().split())
p, d = [x for x in range(N)], [0]*N
ans = 0
for _ in range(k):
op, x, y = map(int, input().split())
px, py = find(x), find(y)
if x>n or y>n: ans+=1
elif op==1:
# 不能这样写，感觉应该是有负数的情况
# if px==py and (d[x]%3) != d[y]%3: ans+=1
if px==py and mod(d[x]-d[y],3): ans+=1
elif px!=py:
p[px]=py
d[px]=d[y]-d[x]
else:
# 不能这样写，感觉应该是有负数的情况
# if px==py and (d[x]%3) != (d[y]%3 + 1): ans+=1
if px==py and mod(d[x]-d[y]-1,3): ans+=1
elif px!=py:
p[px]=py
d[px]=d[y]-d[x]+1
print(ans)
Day27.(2021.11.13)
今天复习了堆，hash和并查集的内容
Day28.(2021.11.14)
最短路问题
n指点的个数，m指边的个数
稠密图边多（m和n^2差不多的时候，用邻接矩阵来存）， 稀疏图（用邻接表来存）
朴素dijkstra（稠密图），堆优化版的dijkstra（稀疏图），bellman_ford（稠密图），spfa（稀疏图）（不晓得是不是只能运用于这个场景）
源指起点，汇指终点
# acwing 849. Dijkstra求最短路I
# https://blog.csdn.net/qq_37796444/article/details/80663810
# y总算法思路没有这个博客讲的形象
# 第一个for循环是找出没有被确认的最短路径的点集合中离源点最近的点
# 第二个for循环是用选出的这个点来更新源点到其他点的最短路径（只用更新
# 没被确认的相邻的点，但是为了代码方便就直接全部更新）
N, null = 510, 0x3f3f3f3f
def dijkstra():
dist[1]=0
for _ in range(n):
t = -1
for j in range(1,n+1):
if not st[j] and (t==-1 or dist[t]>dist[j]):
t=j
st[t]=True
for j in range(1,n+1):
dist[j]=min(dist[j], dist[t]+g[t][j])
if dist[n]==null: return -1
else: return dist[n]
if __name__ == '__main__':
g = [[null]*N for _ in range(N)]
# dist 用于存储每个点到起点的最短距离
# st 用于在更新最短距离时 判断当前点的最短距离是否确定 是否需要更新
dist, st = [null]*N, [False]*N
n, m = map(int, input().split())
for _ in range(m):
x,y,z = map(int, input().split())
g[x][y] = min(g[x][y],z)
ans = dijkstra()
print(ans)# acwing 850. Dijkstra求最短路II
from heapq import *
N, NULL = 150010, 0x3f3f3f3f
def add(a,b,c):
global idx
e[idx] = b
ne[idx] = h[a]
w[idx] = c
h[a] = idx
idx += 1
def dijkstra():
dist[1] = 0
heap = []
heappush(heap,(0,1))
while heap:
t = heappop(heap)
distance, ver = t[0], t[1]
if st[ver]: continue
else: st[ver] = True
i = h[ver]
while i!=-1:
j = e[i]
if dist[j] > distance + w[i]:
dist[j] = distance + w[i]
heappush(heap,(dist[j],j))
i=ne[i]
if dist[n]==NULL: return -1
else: return dist[n]
if __name__ == '__main__':
h, e, w, ne, idx = [-1]*N, [0]*N, [0]*N, [0]*N, 0
dist, st = [NULL]*N, [False]*N
n, m = map(int,input().split())
for _ in range(m):
x,y,z = map(int, input().split())
add(x,y,z)
ans = dijkstra()
print(ans)
Day29.(2021.11.15)
Bellman-Ford（有负权边使用，可以有负环，有负环的情况不一定有最短路）
for n 次 （k次，求的最短距离是从1号点不超过k条边走到每个点的最短距离）
spfa要求不能有负环
# acwing 853.有边数限制的最短路
# 这个代码确实简单，但是这个原理确实也完全不了解
import copy
N, NULL = 510, 0x3f3f3f3f
def bellman_ford():
dist[1] = 0
for _ in range(k):
last = copy.deepcopy(dist)
for j in range(m):
a,b,w = edges[j]
dist[b] = min(dist[b], last[a] + w)
if dist[n] > (NULL/2): return 'impossible'
else: return dist[n]
if __name__ == '__main__':
edges, dist = [], [NULL]*N
n, m, k = map(int, input().split())
for _ in range(m):
x,y,z = map(int, input().split())
edges.append((x,y,z))
ans = bellman_ford()
print(ans) 
# acwing 851.spfa求最短路
# st用来判断当前点是否在队列中（这个
# 队列中的点都是变化过的，要用来更新其他边）
from collections import deque
N, NULL = 100010, 0x3f3f3f3f
def add(a,b,c):
global idx
e[idx] = b
ne[idx] = h[a]
w[idx] = c
h[a] = idx
idx += 1
def spfa():
dist[1]=0
q = deque([1])
while q:
a = q.popleft()
st[a] = False
index = h[a]
while index!=-1:
b = e[index]
if dist[b] > dist[a] + w[index]:
dist[b] = dist[a] + w[index]
if not st[a]:
q.append(b)
st[b] = True
index = ne[index]
if dist[n]==NULL: return 'impossible'
else: return dist[n]
if __name__ == '__main__':
h,e,ne,w,idx = [-1]*N, [0]*N, [0]*N, [0]*N, 0
dist, st = [NULL]*N, [False]*N
n,m = map(int, input().split())
for _ in range(m):
x,y,z = map(int, input().split())
add(x,y,z)
ans = spfa()
print(ans)Day30.(2021.11.16)
spfa判断负环，这里主要是用一个额外的数组来存储边数，当经过的边数大于等于n的时候就可以判断存在负环。然后初始化需要将所有点都先放入队列，是因为可能从1号点走不到负环。所以需要以所有点都走一下试试。
# acwing spfa判断负环
from collections import deque
N, M, NULL = 2010, 10010, 0x3f3f3f3f
def add(a,b,c):
global idx
e[idx] = b
ne[idx] = h[a]
w[idx] = c
h[a] = idx
idx += 1
def spfa():
dist[1] = 0
q = deque([x for x in range(1,n+1)])
while q:
a = q.popleft()
st[a] = False
index = h[a]
while index!=-1:
b = e[index]
if dist[b] > dist[a] + w[index]:
dist[b] = dist[a] + w[index]
cnt[b] = cnt[a] + 1
if cnt[b]>=n: return 'Yes'
if not st[b]:
st[b] = True
q.append(b)
index = ne[index]
return 'No'
if __name__ == '__main__':
n, m = map(int, input().split())
h, e, ne, w, idx = [-1]*N, [0]*M, [0]*M, [0]*M, 0
dist, cnt, st = [NULL]*N, [0]*N, [False]*N
for _ in range(m):
x,y,z = map(int, input().split())
add(x,y,z)
ans = spfa()
print(ans)Floyd算法
d[i,j]最开始存的所有边，这个算法基于动态规划
可以有负权，但是不能有负权回路
d[k,i,j]从i这个点只经过1~k这些点到达j的最短距离。这个题还要注意下可能会点x,y到点x,y
# acwing 854. Floyd求最短路
N, NULL = 210, 0x3f3f3f3f
def floyd():
for k in range(1,n+1):
for i in range(1,n+1):
for j in range(1,n+1):
grid[i][j] = min(grid[i][j], grid[i][k]+grid[k][j])
if __name__ == '__main__':
n,m,k = map(int, input().split())
grid = [[NULL]*N for _ in range(N)]
for i in range(N):
grid[i][i] = 0
for _ in range(m):
x,y,z = map(int, input().split())
grid[x][y] = min(grid[x][y],z)
floyd()
for _ in range(k):
x,y = map(int, input().split())
if grid[x][y] > (NULL/2): print('impossible')
else: print(grid[x][y])最短路有些时候是判断==NULL [ dijkstra（没有负边），spfa（用的链表，会阻止-x+NULL这种更新）]，有些时候是>NULL/2（bellman_ford和floyd）（例如spfa，spfa从源点开始更新相连的点（最终如果更新到终点的话，那说明源点和终点了相连），然而bellman_ford直接用所有边更新，可能在第一遍就更新了终点）
版权声明：本文为weixin_41126303原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。