Warning
OVER 学习结束！可能以后都不会用PYTHON写算法题目了，因为PYTHON的一些算法语法基础不牢固导致一道题看了2个小时！

时间题目链接完成情况
3.29比赛链接:https://www.nowcoder.com/acm/contest/106557百分之50
3.30比赛链接:https://www.nowcoder.com/acm/contest/106558
3.31比赛链接:https://www.nowcoder.com/acm/contest/106559
4.1比赛链接:https://www.nowcoder.com/acm/contest/106560
4.2比赛链接:https://www.nowcoder.com/acm/contest/106562优先队列 + 并查集
4.3比赛链接:https://www.nowcoder.com/acm/contest/106563搜索 + 剪枝
4.4比赛链接:https://www.nowcoder.com/acm/contest/106564动态规划1
4.5比赛链接:https://www.nowcoder.com/acm/contest/106565动态规划2
4.6比赛链接:https://www.nowcoder.com/acm/contest/106566图论 + 最短路
4.7比赛链接:https://www.nowcoder.com/acm/contest/106567数学
4.8比赛链接:https://www.nowcoder.com/acm/contest/106568线段树 + 树状数组
4.9比赛链接:https://www.nowcoder.com/acm/contest/106569LCA + RMQ
4.10
4.11
4.12蓝桥杯

知识点完成情况

待办
数学
LCA + RMQ树上问题

PY 笔记

递归

先递归的后算，递归的特性是 自下而上

def fun(x):
   if exam():
       return
   return fun(min_x)

DFS 和 BFS 的实现

DFS 是属于 递归迭代 的算法过程， BFS 是属于 层次扩展（队列完成）

因为有时候DFS的时间复杂度是 2 的n次方，所以如果层次足够少的话，便可以使用BFS来实现

PY中的DP 缓存

dp = {}

PY 内置函数

1. 快速幂
pow(a,b,mod)
pow(a,b)


2. gcd（最大公约数）
import math
math.gcd(a,b)


def gcd(a, b):
  if b == 0:
    return a
  return gcd(b, a % b)


3. 找满足值


next(i for i in range(n - 1) if not fa[i])

Deque(队列)

from collections import deque


origin = int(input())


q = deque([origin]) # 需要列表存入


x1, x2 = map(int, input().split())
q.append(x1)
q.appendleft(x2)


x = q.popleft()
y = q.pop()
print(q[0],q[-1],x,y,len(q))


if not q:
  print("YES")

排序算法

基础排序

nums.sort(key=())


class Node:
  def __init__(self, a, b,c):
    self.a = a
    self.b = b
    self.c = c
  def __repr__(self):
    return f'({self.a}, {self.b}, {self.c})'


t = int(input())
nodes = []


for _ in range(t):
  a, b, c = map(int, input().split())
  nodes.append(Node(a,b,c))


nodes = sorted(nodes, key = lambda x : (x.a, -x.b,x.c))

基数排序（基于每一位的大小排序）

归并排序

def guibing(arr):
  if len(arr) == 1:
    return arr
  mid = (len(arr)) // 1
  left = guibing(arr[:mid])
  right = guibing(arr[mid:])
  return merge(left, right)


def merge(left ,right):
  ans = []
  i = j = 0


  while(i < len(left) and j < len(right)):
    if(left[i] < right[j]):
      ans.append(left[i])
      i += 1
    else:
      ans.appemd(right[j])
      j += 1
  ans.extend(left[i:])
  ans.extend(right[j:])
  return ans

归并排序 求 逆序队

count = 0


def merge(left, right):
  global count
  ans = []
  i = j = 0


  while i < len(left) and j < len(right):
    if(left[i] <= right[j]): # 一定要 =
      ans.append(left[i])
      i += 1
    else:
      ans.append(right[j])
      count += (len(left) - i)
      j += 1
  ans.extend(left[i:])
  ans.extend(right[j:])
  return ans


def f(arr):
  if len(arr) == 1:
    return arr
  mid = len(arr) // 2
  left = f(arr[:mid])
  right = f(arr[mid:])
  return merge(left, right)

快排

  • 理解 第一种快排的排序方法
def quick_sort(l, r,arr):
  if l >= r:
    return;
  i ,j = l, r
  x = arr[l]
  while i < j:
    while i < j and arr[j] >= x:
      j -= 1
    while i < j and arr[i] <= x:
      i += 1
    if i < j:
      arr[i], arr[j] = arr[j], arr[i]


  arr[l], arr[i] = arr[i], arr[l]
  quick_sort(l, i - 1, arr)
  quick_sort(i + 1, r, arr)
def quick_sort1(arr):
  if len(arr) <= 1:
    return arr
  povit = arr[0]
  left = [x for x in arr[1:] if x <= povit]
  right = [x for x in arr[1:] if x > povit]


  return quick_sort1(left) + [povit] + quick_sort1(right)

建树

1. 有权
dj = [[] for _ in range(n + 1)]
dj[a].append((b,w))


2. 无权
dj[a].append(b)

二分查找

C++

  • lower_bound() 查找可插入元素的最小位置
  • upper_bound() 查找可插入元素的最大位置
  • binary_bound() 查找元素是否存在

PY

import bisect
bisect.bisect_left() # 靠左 >= 严格大于等于
bisect.bisect_right() # 靠右 > 严格大于
# 从 lo -> hi
 x = bisect.bisect_right(a, need, lo=1, hi=i)

三分

三分用来求函数极值

一般 有 先增后减，先减后增 的特性

三分模版:

 while l < r:
        mid1 = l + (r - l) // 3
        mid2 = r - (r - l) // 3
        if f(mid1) > f(mid2):
            r = mid2 - 1
        else:
            l = mid1 + 1
    print(f(l))

分治常见题目

解决最近曼哈顿距离

优先队列 heapq

heapq是 默认为 小根堆 需要用大根堆的话可以 可以用 值 * -1来存储

当 a 初始化 为heapq后, 优先队列的长度 和 是否为空的判断都是 判断 a 这个列表

import heapq


a = []
# 插入
heapq.heappush(a, item)


# 弹出
heapq.heappop(a)


# 判断是否为空 或者 长度 以 a 为判断
len(a)
if not a


# 如果要将 list(a) 直接变成 优先队列
heapq.heapify(a)


# 取 前 n 大 用队列存
heapq.nlargest(n, a)


# 取 钱前 n 小 用队列存
heapq.nsmallest(n, a)

优先队列 自定义排序结构

a = []
heapq.heappush(a, (-item[0], item[1], item[2]))

优先队列相关问题

  • 中位数问题:

    一个小根堆，一个大根队来维护中位数

  • 前 k 大问题

    一个 长度为 k 小根堆来维护

Python 的输入处理

import sys
input = sys.stdin.readline
  1. 单个读取:n = int(input())
  2. 一行读取:a = list(map(int, input().split()))
  3. 多行读取 每行一个元素:nums = [int(input()) for _ in range(n)]
  4. 多行读取 每行多个元素:nums = [list(map(int, input().split())) for _ in range(n)]

Python 的输出处理

  • 将字符串连接:
    • ‘m’.join(list):将列表中的字符串用m连接起来
  • 将列表中的元素先转化为 字符串再输出:
    • ‘m’.join(map(str, list))
      • map的意思是将list中的每一个元素都转化为字符
  • 格式化输出:
    • print(f “{x : .2f}”) 保留两位小数
    • print(f”{name} got {score} points.”)
    • print(x, end = ’ ‘)

多组测试

while True:
    try:
    except EOFError:  # 输入结束时退出
        break
    except ValueError:  # 无效输入时退出
        break

字典的操作

  • 基础map
mp = {}
# 防止访问没有存在的字典，如果不存在 就返回 k
mp.get(a[r], k)
  • 更方便的map
from collections import defaultdict
# 可以避免访问不存在的字典出现报错
mp = defaultdict(int)
  • MAP去重离散化
# 排序 + 去重
sorted(set(arr))
# enumerate 返回的是 (index, vavlue)
# 现在需要的是 key : index
# 所以需要 将 i, x 反转
mp = {x : i for i , x in enumerate(sorted(set(arr)))}

栈和队列

在 PY 中， 栈和队列都可以使用 deque(双端队列)来实现

栈

from collections import deque
stack = deque()
stack.append(x)


# 访问栈头
top = stack[-1]
top = stack.pop()


# 清空栈
stack.clear()

队列

from collections import deque
q = deque()


# 加入
q.append(x)
q.appendleft(x)
q.insert(l, item)


# 出队
left = q.popleft()

01 分数规划

  • 二分 + 贪心 设 X = (∑a[i]) / (∑b[i]) -> ∑a[i] - X * ∑b[i] = 0 二分查找 X，看 X 对于 这个式子的影响是过大还是过小。
l = 0
r = 1e6
eps = 1e-6
while (r - l) > eps:
    mid = (r + l) / 2
    if exam(mid):
        l = mid
    else:
        r = mid

动态规划

一定是 从最优 到 最优

计算当前节点时，统计需要的历史信息（dp的存储）

01 背包 / 完全背包

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])

一个是 价值 从小到大（完全背包） 一个是 价值 从大到小（01 背包）

# 01 背包
for i in range(1, n+1):
    for j in range(C, w[i]-1, -1):
        f[j] = max(f[j], f[j - w[i]] + v[i])
# 完全背包
for i in range(1, n+1):
    for j in range(C, w[i]-1, -1):
        f[j] = max(f[j], f[j - w[i]] + v[i])

多重背包

问题:每一个物品有 选择次数限制 s[i]

使用二进制优化 转化成01背包

将 s[i] 使用二进制进行拆分 (k _ w, k _ v) k是 2 的 n次方

new = []
for i in range(n):
  w, v, s = W[i], V[i], S[i]
  k = 1
  while k < s:
    new.append((w * k, v * k))
    s -= k
    k <<= 1
  if s > 0:
    new.append((w * s, v * s))
  # 转化成新的 01 背包

分组背包

问题:分成 n 组，每一组 选 一个 的最大价值

dp[i][j] = max(dp[i][j],dp[i - 1][j - w[i]] + v[i])

for group in groups:
  for j in range(V,-1,-1):
    for w,v in group:
      if j >= w:
        f[j] = max(f[j],f[j - w] + v)

有依赖背包

树型DP

区间DP

数论

埃式筛

prime = []
is_prime = [True] * (n + 1)
for i in range(2,n):
    if if_prime[i]:
        prime.append(i)
        for j in range(i * i, n + 1, i):
            is_prime[j] = False
return prime

拆分因子

ans = set()


for i in range(1, int(n ** 0.5) + 1):
    if n % i == 0:
        ans.add(i)
        ans.add(n // i)
  return sorted(ans)

因子预处理

fac = [[] for i in range(n + 1)]


for i in range(1, n + 1):
  for j in range(i, n + 1, i):
    fac[j].append(i)
return fac

Python 解决字符串分割问题

巧妙的使用 split(‘char’)

s = input().strip()


terms = s.split('+')


ans = 0
for fa in terms:
  s1 = fa.split('*')
  temp = 1
  for fac in s1:
    if fac:
      temp *= int(fac)
  ans += temp

字符串

KMP

# NEXT[I] 表示 前 i - 1 个元素的 最长前后缀匹配长度
next = [0] * len(s2)
def get_next(s2):
    n = len(s2)
    next[0] = -1
    next[1] = 0
    i, cn = 2,0 # cn 表示 i - 1 的next值
    while i < n:
        if s2[i - 1] == s2[cn]:
            next[i++] = ++cn
        elif cn > 0:
            cn = next[cn]
        else:
            next[i++] = 0


def kmp(s1, s2):
    n, m = len(s1),len(s2)
    x, y = 0, 0
    get_next(s2)
    while x < n and y < m:
        if s1[x] == s2[y]:
            x += 1
            y += 1
        elif y == 0:
            x += 1
        else:
            y = next[y]

字典树

cnt = 1


n, s # n 表示 层, s 表示 种类
# 第一层什么不都存储，相当于空字符
tree = [[0]*s for i in range(n)]
# pass 表示 每一个前缀的 访问次数
pass = [0] * N
# end 表示 每一个字符串的结尾 访问次数
def insert(word):
  cur = 1
    pass[cur] += 1
  for x in word:
         path = x - 'a'
        if tree[cur][path] == 0:
            tree[cur][path] = ++cnt
        cur = tree[cur][path]
        pass[cur] += 1
    end[cur] += 1


def prenum(pre):
    cur = 1
    for x in pre:
        path = x - 'a'
        if tree[cur][path] == 0:
            return 0
        cur = tree[cur][path]
    return pass[cur]


def delete(word):
    if prenum(word) > 0:
        cur = 1
        for x in word:
            path = x - 'a'
            pass[tree[cur][path]] -= 1
            if pass[tree[cur][path]] == 0:
              tree[cur][path] = 0
                return;
            cur = tree[cur][path]
        end[cur] -= 1

Dijkstra

import heapq
def dj(n, g, start):
    dist = [float('inf')] * n
    dist[start] = 0
    heap = [(0,start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in g[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                heapq.heappush(heap,(dist[v],v))
     return dist