2024蓝桥杯Python国赛备赛

作者： 作者的头像   波尔k ,  2024-05-30 15:28:27 ,  所有人可见 ,  阅读 102

19


9

2024蓝桥杯Python国赛

Tips

  • 输入的数量级在$1e5$及以上，则一定要开stdin加速
from sys import stdin
input = lambda: stdin.readline()
  • 默认递归深度为1000，一般树形结构的DFS需要重新设置递归深度
from sys import setrecursionlimit
setrecursionlimit(int(1e5))
  • IDLE字体可以选择Consolas
  • 浮点输出
print('%.5f' % pi)
print('{:.6f}'.format(pi))
  • 字符串补0对齐输出（状压DP调试用）
print('123'.zfill(5))
  • 二进制输出
print(bin(123))
print(bin(123)[2:])
  • 题型及分值
题目 分值 备注
A 5 填空题，通常比较简单
B 5 填空题，可能有点难度，若思考10min没什么思路，果断放弃
C 10 编程题，通常比较简单
D 10 编程题，通常比较简单
E 15 编程题，涉及一些简单的思维转换
F 15 编程题，可能有一些简单模拟+常见的数据结构
G 20 编程题，可能是数学公式题，多动脑子
H 20 编程题，难度适中，完全属于可做题，多想想
I 25 编程题，通常考查的知识点较难，看数据范围先写暴力
J 25 编程题，通常考查的知识点较难，看数据范围先写暴力
  • 时间复杂度导向的思考方向
数据范围 算法
$n \le 30$ 指数级别的时间复杂度，通常考虑dfs+剪枝、状压dp
$n \le 100$ $n^3$级别的时间复杂度，通常考虑floyd、区间dp
$n \le 1000$ $n^2$、$n^2logn$级别的时间复杂度，通常考虑二分、线性dp
$n \le 10000$ $n\sqrt{n}$级别的时间复杂度，通常考虑分块
$n \le 100000$ $nlogn$级别的时间复杂度，通常考虑排序算法、树状数组、线段树、heap、二分、set、dict、Tire
$n \le 1e6$ $n$、常数非常小的$nlogn$级别的时间复杂度，通常考虑单调队列、双指针、BFS、并查集、树状数组
$n \le 1e7$ $n$级别的时间复杂度，通常考虑双指针、KMP、线性素数筛法
$n \le 1e9$ $\sqrt n$级别的时间复杂度，通常考虑判断素数
$ n \le 1e18$ $logn$级别的时间复杂度，通常考虑最大公约数、快速幂、数位dp

Python语法/自带的容器

字符串

大小写操作

s = 'heKaI'
# 首字母大写
print(s.capitalize()) # Hekai
# 全部大写
print(s.upper()) # HEKAI
# 全部小写
print(s.lower()) # hekai
# 大小写互换
print(s.swapcase()) # HEkAi

查找

推荐使用find函数进行查找

find(str, beg=0, end=len(string))：

查找子串str第一次出现的位置，如果找到则返回相应的索引，否则返回-1

时间复杂度$O(n)$

s = 'My name is HeKai, a hansome boy.HeKai is my best friend'
ss = 'HeKai'
print(s.find(ss)) # 11
print(s.find(ss,20)) # 32
print(s.find(ss,40)) # -1

删除首尾字符：strip()

分割操作：split()

列表转字符串：''.join(list)

字符串与ASCII码

print(ord('a')) # 97
print(chr(65))  # A

列表

range

range(start,end,step)：从start开始，到end -1 结束，相邻两个数之间相差step

逆序遍历可以令step=-1，也可以结合reversed()函数实现

元素插入

insert(index,obj)：在index处插入元素obj

时间复杂度$O(n)$

元素删除

pop(index = -1)：删除列表中index处的元素（默认index = -1），并且返回该元素的值

remove(obj)：删除列表中第一次出现的obj元素

clear()：删除列表中所有元素

排序

sort()：默认对列表中的元素从小到大排序。
sort(reverse = True) ：列表中的元素按从大到小进行排序。

字典

fromkeys()

dict.fromkeys()以给定的多个键值创建一个新的字典

lst = ['Hee', 'Lv', 'Lee']
dic1 = dict.fromkeys(lst)
dic2 = dict.fromkeys(lst, '1234')
print(dic1) # {'Hee': None, 'Lv': None, 'Lee': None}
print(dic2) # {'Hee': '1234', 'Lv': '1234', 'Lee': '1234'

查找

dict.get(key)：根据键值来获取值

dict.items()：获取所有的键-值对

dict.keys()：获取所有的键

dict.values()：获取所有的值

删除

dict.pop(key)返回指定键对应的值，并在原字典删除此键值对

更新

dict.update(list)将list中的键值对更新到字典里，如果字典内包含该键值则覆盖，否则添加该键值对

复制

dic1=dic2简单的引用

dict.copy()深拷贝父对象，浅拷贝子对象

copy.deepcopy()递归拷贝所有数据

集合

add()：把要传入的元素作为一个整体添加到集合中

update()：要传入的元素拆分成单个字符，存于集合中，并去掉重复的字符

remove()：在集合中查找元素，如果存在则删除；如果没找到，则报错

discard()：在集合中查找元素，如果存在则删除；如果没找到，则什么也不做

clear()：清空集合中的所有元素

pop()：随机移除元素

集合操作：

集合的并集：a | b

集合的交集：a & b

集合的差集：a - b

基础算法

排序

list.sort(func = None, key = None, reverse = True(or False))

sorted函数可以拓展到任意一个可迭代的容器上

善用lambda：

lst = [(28,10), (16,20), (16,18), (10,8), (14,10)]
lst.sort(key = lambda x:(x[0], x[1]))
print(lst) # [(10, 8), (14, 10), (16, 18), (16, 20), (28, 10)]
lst.sort(key = lambda x:(x[1], x[0]))
print(lst) # [(10, 8), (14, 10), (16, 18), (16, 20), (28, 10)]
lst.sort(key = lambda x:(x[0]- x[1]), reverse = True)
print(lst) # [(28, 10), (14, 10), (10, 8), (16, 18), (16, 20)]
归并排序
A = [1, 5, 3, 7, 2, 11, 55, -10, 43]
tmp = [0] * len(A)
def Merge(l, m, r):
     i, j, k = l, m+1, l
     while i <= m and j <= r:
          if A[i] > A[j]:
               tmp[k] = A[j]
               j += 1
          else:
               tmp[k] = A[i]
               i += 1
          k += 1
     while i <= m:
          tmp[k] = A[i]
          k += 1
          i += 1
     while j <= r:
          tmp[k] = A[j]
          k += 1
          j += 1
     for i in range(l, r+1):
          A[i] = tmp[i]
def MergeSort(l, r):
     if l < r:
          m = (l + r) >> 1
          MergeSort(l, m)
          MergeSort(m+1, r)
          Merge(l, m, r)
print(A)
MergeSort(0, len(A)-1)
print(A)
# [-10, 1, 2, 3, 5, 7, 11, 43, 55]

日期问题

# 判断闰年
def isRun(year):
     if (year % 100 != 0 and year % 4 == 0) or year % 400 == 0:
          return True
     return False
# 合法性判断
days = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
def check(date):
     year = date // 10000
     month = date // 100 % 100
     day = date % 100
     if month < 1 or month > 12 or day < 1:
          return False
     if month != 2 and day > days[month]:
          return False
     if month == 2:
          leap = 0
          if isRun(year) is True:
               leap = 1
          if day > 28 + leap:
               return False
     return True

离散化

def lsh():
     CopyA = [A[i] for i in range(len(A))]
     CopyA.sort()
     tmp = []
     for i in range(len(CopyA)):
          if i > 0 and CopyA[i] == CopyA[i-1]:
               continue
          tmp.append(CopyA[i])
     for i in range(len(A)):
          A[i] = bisect_left(tmp, A[i]) + 1

差分

一维差分

def ins(l, r, c):
    A[l] += c
    A[r + 1] -= c

二维差分

def ins(x, y, xx, yy, c):
    A[x][y] += c
    A[x][yy + 1] -= c
    A[xx + 1][y] -= c
    A[xx + 1][yy + 1] += c

二分

基本套路，一定要敏锐的发现问题的单调性（可二分性）

求浮点型的二分：循环设置固定的迭代数，注意小数的精度(1e-2*要求)

lst = list(map(int,input().split()))
def check(pos,x):
    if lst[pos] <= x:
        return 1
    else:
        return 0
def tfind(x):
    left = 0
    right = len(lst) - 1
    while left <= right:
        mid = (left + right) // 2
        if check(mid,x):
            res = mid
            left = mid + 1
        else:
            right = mid - 1
    return res
bisect二分查找库

bisect函数类似于upper_bound

bisect_left函数类似于lower_bound

用法：

from bisect import bisect, bisect_left
A = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]

index = bisect(A, 3)
print(index) # 6
index = bisect_left(A, 3)
print(index) # 3

前缀和

一维前缀和：

[n, m] = list(map(int,input().split()))
lst = list(map(int,input().split()))
dp = [0]
for i in range(n):
    dp.append(dp[i]+lst[i])
for _ in range(m):
    [l, r] = list(map(int,input().split()))
    print(dp[r] - dp[l-1])

二维前缀和：

[n, m, q] = list(map(int,input().split()))
a = [list(0 for _ in range(m+1))]
for _ in range(n):
    lst = list(map(int,input().split()))
    a.append([0]+lst)
dp = [[0 for _ in range(m+1)]for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + a[i][j]
for _ in range(q):
    [x, y, xx, yy] = list(map(int,input().split()))
    res = dp[xx][yy] - dp[xx][y-1] - dp[x-1][yy] + dp[x-1][y-1]
    print(res)

数据结构

队列

因为list的pop(0)操作的时间复杂度是$O(n)$的，有时候可能会产生超时的问题

所以常用到collections.deque

from collections import deque
# 初始化
dq = deque([]) 
print(dq) # deque([])
lis = [1, 3, 2, 14]
dq = deque(lis)
print(dq) # deque([1, 3, 2, 14])
print(list(dq)) # [1, 3, 2, 14]

# append，从右端添加元素，与list一样
dq = deque(lis)
dq.append(10)
dq.append((1,2))
print(dq) # deque([1, 3, 2, 14, 10, (1, 2)])

# appendleft，从左端添加元素
dq.appendleft(-1)
print(dq) # deque([-1, 1, 3, 2, 14, 10, (1, 2)])

# pop
print(dq.pop()) # (1, 2)
print(dq.pop()) # 10
print(dq) # deque([-1, 1, 3, 2, 14])

# popleft
print(dq.popleft()) # -1
print(dq.popleft()) # 1
print(dq) # deque([3, 2, 14])

# extend，从右端逐个添加可迭代对象
# extendleft,从左端逐个添加可迭代对象
dq.extend([100, 200, 300])
dq.extendleft([-1, -2, -3])
print(dq)
# deque([-3, -2, -1, 3, 2, 14, 100, 200, 300])

双向链表

# 数组模拟链表
N = 1010
val = [0] * N
pre = [0] * N
nxt = [0] * N
head,tail,tot = 0,0,0

# 初始化
def ini():
    global head,tail,tot
    tot = 2
    head,tail = 0,1
    nxt[head] = tail
    pre[tail] = head

# 插入操作
def ins(p, x):
    # 在位置p插入x
    global tot
    q = tot
    tot += 1
    val[q] = x
    pre[nxt[p]] = q
    nxt[q] = nxt[p]
    nxt[p] = q
    pre[q] = p

# 删除操作
def rem(p):
    # 删除位置p上的元素
    nxt[pre[p]] = nxt[p]
    pre[nxt[p]] = pre[p]

并查集

N = 1010
lis = [0] * N
# 初始化：根节点设为自己
pa = list(range(N))

# 查询，路径压缩
def find(x):
     if pa[x] != x:
          pa[x] = find(pa[x])
     return pa[x]

# 合并
def union(x, y):
     pa[find(x)] = find(y)

大/小根堆

常用到heapq库的heappush,heappop方法

python中的heapq库只有最小堆，没有最大堆，当使用最大堆时，可以在插入元素时将元素取反

单调队列

“比你小还比你强，那你就可以退役了。”

这句话即为单调队列生动且恰当的原理描述

应用：$O(n)$得出每$k$个连续的数中的最值

from collections import deque
n,k = map(int, input().split())
lis = list(map(int, input().split()))
dq = deque([])
for i in range(n):
     if len(dq) and i - dq[0] >= k: dq.popleft()
     while len(dq) and lis[dq[-1]] <= lis[i]: dq.pop()
     dq.append(i)
     if i >= k - 1: print(lis[dq[0]])
     print([lis[i]for i in dq])

单调栈

单调栈和单调队列是类似的，若无左侧的出队操作，即单调栈

应用：求直方图中的最大矩形面积

from sys import stdin
from collections import deque
input = lambda: stdin.readline()
lt = [0 for _ in range(int(1e5)+10)]
rt = [0 for _ in range(int(1e5)+10)]
try:
     while True:
          lis = list(map(int, input().split()))
          n = lis[0]
          if n == 0: break
          q = []
          for i in range(1, n + 1):
               while len(q) and lis[i] < lis[q[-1]]:
                    rt[q.pop()] = i
               q.append(i)
          while len(q): rt[q.pop()] = n + 1
          for i in reversed(range(1, n + 1)):
               while len(q) and lis[i] < lis[q[-1]]:
                    lt[q.pop()] = i
               q.append(i)
          while len(q): lt[q.pop()] = 0
          ans = 0
          for i in range(1, n + 1):
               ans = max(ans, (rt[i] - lt[i] - 1) * lis[i])
          print(ans)
except:
     pass

KMP算法

$O(N+M)$的字符串匹配算法

记匹配串为$s$，模式串为$p$

$next[i]:$ 代表”$p$中以$p[i]$结尾的非前缀子串“和”$p$的前缀“能够匹配的最长长度(即：$p[1:j]=p[i-j+1:i]$)

n = int(input())
p = '!' + input().strip() # 模式串
m = int(input())
s = '!' + input().strip() # 匹配串
# 求next数组
ne = [0] * (n + 10)
j = 0
for i in range(2, n + 1):
    while j > 0 and p[i] != p[j + 1]:
        j = ne[j]
    if p[i] == p[j + 1]:
        j += 1
    ne[i] = j

# kmp算法
j = 0
for i in range(1, m + 1):
    while j > 0 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] # 这是个小细节，如果是子串不重叠的话，需要把这里改成 j = 0

字典树Tire

maxm = int(1e5) +10
nxt = [[0] *26 for _ in range(maxm)]
end = [False] * maxm
tot = 0
def ins(s):
    global tot
    p = 0
    for x in s:
        ch = ord(x) - ord('a')
        if not nxt[p][ch]:
            tot += 1
            nxt[p][ch] = tot
        p = nxt[p][ch]
    end[p] = True
def find(s):
    p = 0
    for x in s:
        ch = ord(x) - ord('a')
        if not nxt[p][ch]: return False
        p = nxt[p][ch]
    return end[p]

数组长度一般开$2e6$为最佳

简单应用：求一个序列中的任意两个数的异或和的最值【贪心+Tire】，做法就是把序列中的每个元素写出等长的(31)位二进制数，每个二进制数视为一个单词，建立一颗二叉Tire树。然后遍历序列中的元素，每一位尽可能取相异的节点即可。

树状数组

简单应用就是能够快速的求动态前缀和，操作对应的就是单点修改和区间查询，时间复杂度均为$O(logn)$

记树状数组为C,C[x]的含义为$\sum_{x-lowbit(x)<j\le x}A[j]$

from sys import stdin
input = lambda: stdin.readline()
n, m = map(int, input().split())
C = [0] * (n+1)
A = [0] + list(map(int, input().split()))
def lb(x):
     return x & -x
def query(x):
     res = 0
     while x > 0:
          res += C[x]
          x -= lb(x)
     return res
def add(x, y):
     while x <= n:
          C[x] += y
          x += lb(x)
for i in range(1, n+1):
     add(i, A[i])
for _ in range(m):
     k, a, b = map(int, input().split())
     if k == 0:
          print(query(b)-query(a-1))
     else:
          add(a, b)
区间加区间和

【要自己会推导】

$\sum_{i=1}^r a_i=\sum_{i=1}^r\sum_{j=1}^i d_j=\sum_{i=1}^r d_i*(r-i+1)=(r+1)*\sum_{i=1}^r d_i - \sum_{i=1}^rd_i*i$

故可以拿两个树状数组分别维护$\sum_{i=1}^r d_i $和$ \sum_{i=1}^rd_i*i$

from sys import stdin
input = lambda: stdin.readline()
n,m = map(int, input().split())
A = [0] + list(map(int ,input().split()))
C = [0] * (n + 10)
T = [0] * (n + 10)
def lb(x):
     return x & -x
def add(x, val):
     vv = x * val
     while x <= n:
          C[x] += val
          T[x] += vv
          x += lb(x)
def query(x, lis):
     res = 0
     while x:
          res += lis[x]
          x -= lb(x)
     return res
def ins(l, r, val):
     add(l, val)
     add(r + 1, -val)
def getSum(l, r):
     res = (r + 1) * query(r, C) - l * query(l - 1, C)
     res -= query(r, T) - query(l - 1, T)
     return res
for i in range(1, n + 1): ins(i, i, A[i])
for _ in range(m):
     tmp = input().split()
     if tmp[0] == 'Q':
          l,r = map(int, tmp[1:])
          print(getSum(l, r))
     else:
          l,r,val = map(int, tmp[1:])
          ins(l, r, val)

动态规划

线性DP

LIS

贪心+二分

from sys import stdin
from bisect import bisect_left
input = lambda: stdin.readline()
n = int(input())
f = []
dp = [0] * n
a = list(map(int, input().split()))
for i in range(n):
    p = bisect_left(f, a[i]) # bisect即为最长不下降子序列
    dp[i] = p + 1
    if p == len(f): f.append(a[i])
    else: f[p] = a[i]
print(len(f))

树状数组

from sys import stdin
input = lambda: stdin.readline()
n = int(input())
a = list(map(int, input().split()))
maxn = max(a) + 1
c = [0] * maxn
def lb(x):
    return x & -x
def add(x, y):
    while x < maxn:
        c[x] = max(c[x], y)
        x += lb(x)
def ask(x):
    res = 0
    while x:
        res = max(res, c[x])
        x -= lb(x)
    return res
dp = [0] * n
for i in range(n):
    dp[i] = ask(a[i] - 1) + 1 # ask(a[i]) + 1即为最长不下降子序列
    add(a[i], dp[i])
print(max(dp))

背包问题

01背包

关键点：考虑每一个物品时倒序遍历背包容量

[n, v] = list(map(int, input().split()))
[V, W] = [[0], [0]]
maxv = int(1e3) + 10
for i in range(n):
     [vi, wi] = list(map(int, input().split()))
     V.append(vi)
     W.append(wi)
dp = [0 for i in range(maxv)]
ans = 0
for i in range(1, n+1):
     for j in reversed(range(V[i], v+1)):
          dp[j] = max(dp[j], dp[j-V[i]]+W[i])
print(dp[v])
完全背包

关键点：考虑每一个物品时正序遍历背包容量

from sys import stdin
input = lambda: stdin.readline()
N,V = map(int, input().split())
v = [0] * N
w = [0] * N
for i in range(N): v[i],w[i] = map(int, input().split())
dp = [-9999] * (V + 1)
dp[0] = 0
for i in range(N):
     for j in range(v[i], V + 1):
          dp[j] = max(dp[j], dp[j - v[i]] + w[i])
print(max(dp))
多重背包

【二进制拆分】

from sys import stdin
input = lambda: stdin.readline()
N,V = map(int, input().split())
v = [0] * N
w = [0] * N
s = [0] * N
for i in range(N):
     v[i],w[i],s[i] = map(int, input().split())
dp = [0] * (V + 10)
for i in range(N):
     k,res = 1,s[i]
     while res > k:
          vv = k * v[i]
          ww = k * w[i]
          for j in reversed(range(vv, V + 1)):
               dp[j] = max(dp[j], dp[j - vv] + ww)
          res -= k
          k *= 2
     if not res: continue
     for j in reversed(range(res * v[i], V + 1)):
          dp[j] = max(dp[j], dp[j - res * v[i]] + res * w[i])
print(dp[V])

【单调队列优化】

from sys import stdin
from collections import deque
input = lambda: stdin.readline()
N,V = map(int, input().split())
dp = [[0 for _ in range(V+10)]for _ in range(2)]
def cal(x, u, k, v, p, w):
     return dp[x][u + k * v] + (p - k) * w
for i in range(N):
     v,w,s = map(int, input().split())
     nw = i & 1
     ls = (i -1) & 1
     for u in range(v):
          q = deque([])
          p = 0
          while p * v + u <= V:
               while len(q) and p - q[0] > s: q.popleft()
               while len(q) and cal(ls, u, p, v, p, w) >= cal(ls, u, q[-1], v, p, w): q.pop()
               q.append(p)
               dp[nw][p * v + u] = max(dp[nw][p * v + u], cal(ls, u, q[0], v, p, w))
               p += 1
print(dp[N - 1 & 1][V])
分组背包

特别注意枚举顺序

from sys import stdin
input = lambda: stdin.readline()
N,V = map(int, input().split())
w = [[]for i in range(N)]
v = [[]for i in range(N)]
dp = [0] * (V + 1)
for i in range(N):
     s = int(input())
     for j in range(s):
          x,y = map(int, input().split())
          v[i].append(x)
          w[i].append(y)
     for j in reversed(range(V + 1)):
          for k in range(s):
               if j < v[i][k]: continue
               dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k])
print(dp[V])

树形DP

顾名思义，在树形的数据结构上做动态规划，通常结合递归、回溯来实现状态的转移

树上背包

树形DP+分组背包，通常是因为父亲节点只能由子节点中的一个状态转移而来，子节点的所有状态构成一个分组，分组数量和节点的儿子个数相同

from sys import setrecursionlimit
setrecursionlimit(310)
n,m = map(int, input().split())
w = [0] * (n + 1)
s = [[]for _ in range(n + 1)]
dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
     x,w[i] = map(int, input().split())
     s[x].append(i)
def dfs(u):
     for v in s[u]:
          dfs(v)
          for i in reversed(range(m + 1)):
               for j in range(i + 1):
                    dp[u][i] = max(dp[u][i], dp[u][i - j] + dp[v][j])
     if u == 0: return
     for i in reversed(range(1, m + 1)):
          dp[u][i] = dp[u][i - 1] + w[u]
dfs(0)
print(dp[0][m])

状压DP

将集合信息转换为整数记录在DP状态中

区间DP

涉及区间的一些性质，且大区间能够由小区间转移而得

【例题，石子合并】

理解点：状态设计、枚举方式

n = int(input())
w = [0] + list(map(int, input().split()))
for i in range(1, n + 1): w[i] += w[i - 1]
dp = [[int(1e9)for _ in range(n + 1)]for _ in range(n + 1)]
for leen in range(1, n + 1):
     for i in range(1, n + 1):
          j = i + leen - 1
          if j > n: break
          if i == j:
               dp[i][j] = 0
               continue
          for k in range(i, j):
               d = w[j] - w[i - 1]
               dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + d)
print(dp[1][n])

数位DP

数位DP是一类与数字相关的计数类问题，一般描述形式为：给定一些限制条件，求满足条件的第$K$小的数，或者求某个区间内有多少满足条件限制的数。

主要用到的方法是试填法和分情况讨论。

数学

前$n$项平方和$S_n=\frac{n*(n+1)*(2n+1)}{6}$

熟记等差/等比数列的求和公式

对于两个互质的数$m$和$n$，表达式$m\cdot x+n\cdot y$，其中$x,y$均为正整数最大不能表示的数为$m*n-m-n$

所有不能表示的数的个数为$\frac{(m-1)*(n-1)}{2}$

矩阵快速幂

矩阵快速幂 = 矩阵乘法 + 快速幂

最经典的应用是求较大项($n>1e7$)的斐波那契数列

构造如下：
$$ [F_i,F_{i-1}] \cdot \left[ \begin{array} {c} 1 & 1 \\ 1 & 0 \end{array} \right] =[F_{i+1},F_i] $$

n,m = map(int, input().split())
def muti(a, b):
    c = [[0, 0], [0, 0]]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                c[i][j] += a[i][k] * b[k][j]
                c[i][j] %= m
    return c
def solve():
    if n <= 2:
        return 1 % m
    a = [[1, 1], [1, 0]]
    b = [[1, 0], [0, 1]]
    cnt = n - 2
    while cnt:
        if cnt & 1:
            b = muti(b, a)
        a = muti(a, a)
        cnt >>= 1
    res = b[0][0] + b[1][0]
    return res % m
print(solve())

【变形】当$n$比较大的时候，如果线性DP能做的情况下，应该要往矩阵加速上面来想

快速幂求逆元

定义：如果一个线性同余方程$ax\equiv 1(mod\;b)$，则称$x$为$a\;mod\;b$的逆元，记作$a^{-1}$

若$b$是一个素数，则可以使用快速幂来做

由于费马小定理，$ax\equiv 1(mod\;b)\Rightarrow ax\equiv a^{b-1}(mod\;b)\Rightarrow x\equiv a^{b-2}(mod\;b)$

欧拉函数

欧拉函数$\varphi(n)$，表示的是小于等于$n$并且和$n$互质的数的个数

唯一分解定理：$n=\prod_{i=1}^s p_i^{k_i}$，其中$p_i$是质数

有：$\varphi(n)=n\times \prod_{i=1}^s \frac{p_i-1}{p_i}$

欧拉筛求欧拉函数$O(n)$

def ini():
    f[1] = 1
    ispri[1] = False
    for i in range(2, maxn):
        if ispri[i]:
            pri.append(i)
            f[i] = i - 1
        for j in pri:
            if i * j >= maxn: break
            ispri[i * j] = False
            if i % j == 0:
                f[i * j] = f[i] * j
                break
            f[i * j] = f[i] * f[j]

约数个数定理

若$n=\prod_{i=1}^s p_i^{k_i}$，则$d(n)=\prod_{i=1}^m(k_i+1)$

约数和定理

约数和定理：若$n=\prod_{i=1}^s p_i^{k_i}$，则$f(n)=\prod_{i=1}^m(p_i^0+p_i^1+…+p_i^{k_i})$

欧拉筛

N = 1010
Pri = []
isPri = [True] * (N+10)
def pre():
     isPri[0] = isPri[1] = False
     for i in range(N):
          if isPri[i]: Pri.append(i)
          for j in Pri:
               if i * j > N: break
               isPri[i * j] = False
               if i % j == 0: break

扩展欧几里得算法

定理：$ax+by=gcd(a,b)$一定有解

扩展欧几里得算法，在欧几里得算法的基础上，不仅能够求出$gcd(a,b)$，还能得到一组特解$x_0,y_0$满足上式

且通解为：
$$ x=x_0+\frac{b}{gcd(a,b)}*t\\ y=y_0+\frac{a}{gcd(a,b)}*t $$

x,y = 0,0
def exgcd(a, b):
     global x, y
     if b == 0:
          x = 1
          y = 0
          return a
     d = exgcd(b, a % b)
     x,y = y,x
     y -= a // b * x
     return d

中国剩余定理

定义：CRT可以求解如下形式的一元线性同余方程组，其中$n_i$两两互质
$$ \cases{ x \equiv a_1(mod\;n_1)\\ x \equiv a_2(mod\;n_2)\\ …\\ x \equiv a_k(mod\;n_k) } $$
法1：

  1. 计算所有模数的乘积$n=\prod_{i=1}^k n_i$

  2. 对于第$i$个方程：

a. 计算$m_i=\frac{n}{n_i}$

b. 计算$m_i$在$mod\; n_i$意义下的逆元$m_i^{-1}$

c. 计算$c_i=m_im_i^{-1}$【此过程不能取余】

  1. 得到唯一解：$x=\sum_{i=1}^k a_ic_i(mod\;n)$
x,y = 0,0
def exgcd(a, b):
    ......
n = int(input())
lis = []
A,ans = 1,0
for i in range(n):
    lis.append(tuple(map(int, input().split())))
    A *= lis[i][0]
for i in range(n):
    B = A // lis[i][0]
    exgcd(B, lis[i][0])
    ans += B * x * lis[i][1]  % B和B的逆元
ans = (ans % A + A) % A
print(ans)

法2：

通过两两合并方程的方式进行，下面讲合并两个方程的思路

有：$x\equiv a_1(mod\;m_1),x\equiv a_2(mod\;m_2)$

转换为等式形式：$x=m_1x+a_1=m_2y+a_2$

即：$m_1x-m_2y=a_2-a_1$

无解的条件判断：$(a_2-a_1)\;mod\;gcd(m_1,m_2)!=1$

若有解，则可以通过exgcd求解出一组解$(x_0,y_0)$

则合并后的方程为：$x\equiv(m_1x_0+a_1)\;(mod(lcm(m_1,m_2)))$

两个可以拓展至$N$个方程的方程组上去

x,y = 0,0
def exgcd(a, b):
    ......
n = int(input())
A,M,ok = 1,0,1
for i in range(n):
    a,m = map(int, input().split())
    d = exgcd(A, a)
    if (m - M) % d != 0:
        ok = 0
        break
    M = A * x * (m - M) // d + M
    A = A * a // d
if not ok: print(-1)
else: print((M % A + A) % A)

组合数

法1：公式法

$C[n][k]=\frac{n!}{k!\cdot (n-k)!}=\frac{\prod_{x=k+1}^{n}x}{(n-k)!}$

为了减少计算次数，$k$取的越大越好

def cal(n, k):
    A = B = 1
    k = max(k, n - k)
    for i in range(1, n - k + 1):
        B *= i
    for i in range(k + 1, n + 1):
        A *= i
    return A // B

法2：杨辉三角预处理

递推式：$C[i][j]=C[i-1][j]+C[i-1][j-1]$

法3：阶乘及其逆元预处理

$C[n][k]=\frac{n!}{k!\cdot (n-k)!}$

预处理出阶乘及其乘法逆元的数组，$O(1)$的代入公式进行求解即可

基础图论

最短路

学习邻接表的建图方式，朴素的Dijkstra算法是$O(n^2)$的，用优先队列优化的Dijkstra算法是$O(nlogn)$的

Dijkstra算法：不断维护一个包含最短路径树中顶点的集合。在每一步中，我们找到一个尚未在集合内且与源顶点距离最小的顶点，并将其收于集合中。

from sys import stdin
from heapq import heappop, heappush
input = lambda: stdin.readline()
n,m = map(int, input().split())
maxm = 200010
mp = [[int(2e5)] * 1010 for _ in range(1010)]
tot = 1
ver = [0] * maxm
nxt = [0] * maxm
val = [0] * maxm
head = [0] * maxm
def add(a, b, c):
    global tot
    tot += 1
    ver[tot] = b
    val[tot] = c
    nxt[tot] = head[a]
    head[a] = tot
d = [0] * 1010
v = [0] * 1010
def dij(root):
    for i in range(1, n + 1):
        d[i] = int(1e9)
        v[i] = 0
    d[root] = 0
    q = []
    heappush(q, (d[root], root))
    while len(q):
        z,x = heappop(q)
        if v[x]: continue
        v[x] = 1
        i = head[x]
        while i:
            y = ver[i]
            z = val[i]
            if d[y] > z + d[x]:
                d[y] = z + d[x]
                heappush(q, (d[y], y))
            i = nxt[i]
for _ in range(m):
    a,b,c = map(int, input().split())
    add(a, b, c)
    add(b, a, c)

Floyd算法：$O(n^3)$的时间复杂度，三层循环其中第一层枚举的是中间节点

maxn = 310
d = [[int(1e9)] * maxn for _ in range(maxn)]
n,m = map(int, input().split())
for i in range(1, n + 1):
    d[i][i] = 0
for _ in range(m):
    x,y,z = map(int, input().split())
    d[x][y] = min(d[x][y], z)
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

最小生成树

Kruskal：按边权进行排序，用并查集进行维护，保证当前边的两端不在一个集合

maxm = int(1e6) + 10
n,m = map(int, input().split())
pa = [i for i in range(1 + n)]
def find(x):
    if x != pa[x]:
        pa[x] = find(pa[x])
    return pa[x]
edge = []
for _ in range(m):
    a,b,c = map(int, input().split())
    edge.append((c, a, b))
edge.sort()
ans = 0
for c,a,b in edge:
    fa = find(a)
    fb = find(b)
    if fa == fb: continue
    ans += c
    pa[fa] = fb
print(ans)

Prim：类似于Dijkstra算法，每次从不在当前集合中找一个最短的结点加入当前集合

0 评论