牛客网笔试模板必刷题 - Python算法学习指南

在这里插入图片描述

题单链接: 牛客网笔试模板必刷题
题目总数: 147道
题单定位: 笔试TOP101的升级版，全部采用ACM模式，适合即将参加笔试、需要快速补全笔试算法知识点的同学学习
覆盖范围: 覆盖了90%+的笔面试算法知识点

目录

  1. 题单概览
  2. 基础算法
  3. 贪心算法
  4. 数学算法
  5. 搜索算法
  6. 树图算法
  7. 数据结构
  8. 动态规划

一、题单概览

1.1 分类结构统计

大类子分类题目数量核心知识点
基础算法简单库函数数据结构8vector、stack、queue、set、multiset、priority_queue
基础算法暴力枚举5枚举、贪心策略
基础算法模拟7日期计算、字符串处理、模拟过程
基础算法排序3快速排序、桶排序
基础算法桶思想2桶排序、离散化
基础算法构造4构造算法、数学构造
基础算法位运算4位运算、异或运算
基础算法博弈论3巴什博弈、扩展巴什博弈
基础算法随机化4随机化算法、Pollard-Rho
基础算法整除分块2整除分块、数论分块
贪心算法简单贪心7贪心策略、排序贪心
贪心算法贪心进阶5区间贪心、排序不等式
数学算法简单数论4质数判断、质因数分解、GCD/LCM
数学算法模运算/快速幂8快速幂、矩阵快速幂、模运算
数学算法组合数学6组合数、排列组合、容斥原理
数学算法高级数论3欧拉函数、乘法逆元、欧拉降幂
搜索算法DFS4深度优先搜索、回溯
搜索算法BFS4广度优先搜索、最短路径
搜索算法二分5整数二分、实数二分
搜索算法记忆化搜索2记忆化、剪枝
搜索算法字符串匹配3KMP、Trie树、马拉车
树图算法树图基础7链式前向星、遍历、图论基础
树图算法并查集3并查集、路径压缩
树图算法最短路/生成树5Dijkstra、BFS、Kruskal/Prim
数据结构前缀和与差分4一维/二维前缀和、差分
数据结构双指针7滑动窗口、双指针技巧
数据结构单调栈/队列2单调栈、单调队列
数据结构倍增/LCA/ST表3LCA、RMQ、倍增
数据结构高级数据结构5线段树、树状数组
动态规划简单DP6线性DP、背包基础
动态规划进阶DP12树形DP、区间DP、状态压缩DP

1.2 难度分布

难度级别题目数量占比
入门6道4.1%
简单56道38.1%
中等67道45.6%
较难16道10.9%
困难2道1.4%

二、基础算法

2.1 简单库函数数据结构（8道）

题号题目名称难度核心考察知识点
BISHI1【模板】序列操作简单vector操作
BISHI2【模板】栈的操作简单stack操作
BISHI3【模板】队列操作简单queue操作
BISHI4【模板】集合操作简单set操作
BISHI5【模板】多重集合操作简单multiset操作
BISHI6【模板】整数优先队列简单priority_queue
BISHI7字符串哈希简单字符串哈希
BISHI8大整数哈希简单大数哈希

2.2 暴力枚举（5道）

题号题目名称难度核心考察知识点
BISHI9田忌赛马中等贪心+枚举
BISHI10小红的字符串修改简单字符串枚举
BISHI11变幻莫测简单模拟枚举
BISHI12元素方碑中等枚举+模拟
BISHI13九倍平方数简单数学枚举

2.3 模拟（7道）

题号题目名称难度核心考察知识点
BISHI14特殊的科学计数法简单字符串模拟
BISHI15小红的夹吃棋简单博弈模拟
BISHI16计算一年中的第几天入门日期模拟
BISHI17纸牌游戏简单游戏模拟
BISHI18多项式输出简单格式模拟
BISHI19乒乓球简单规则模拟
BISHI20回文日期简单日期判断

2.4 排序（3道）

# 快速排序模板
def quick_sort(nums, left, right):
    if left >= right:
        return
    pivot = nums[left]
    i, j = left, right
    while i < j:
        while i < j and nums[j] >= pivot:
            j -= 1
        while i < j and nums[i] <= pivot:
            i += 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[left], nums[i] = nums[i], nums[left]
    quick_sort(nums, left, i - 1)
    quick_sort(nums, i + 1, right)
    return nums

# 归并排序模板
def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
题号题目名称难度核心考察知识点
BISHI21【模板】排序入门快速排序
BISHI22分数线划定简单排序+贪心
BISHI23小红书推荐系统简单排序应用

2.5 位运算（4道）

# 常用位运算技巧
# 1. 判断奇偶
is_odd = x & 1

# 2. 获取最低位的1
lowbit = x & (-x)

# 3. 消除最低位的1
x = x & (x - 1)

# 4. 判断是否为2的幂
is_power_of_2 = x > 0 and (x & (x - 1)) == 0

# 5. 异或交换两数
a = a ^ b
b = a ^ b
a = a ^ b
题号题目名称难度核心考察知识点
BISHI30二进制数1简单位运算
BISHI31二进制不同位数简单位运算
BISHI32被打乱的异或和简单异或运算
BISHI33Poi的新加法(Easy)简单位运算模拟

2.6 博弈论（3道）

# 巴什博弈
# n个物品，每次取1-m个，取最后一个者胜
# 先手必胜当且仅当 n % (m+1) != 0

def bash_game(n, m):
    return n % (m + 1) != 0
题号题目名称难度核心考察知识点
BISHI34甜蜜的博弈简单博弈
BISHI35【模板】巴什博弈中等巴什博弈
BISHI36【模板】扩展巴什博弈较难扩展巴什博弈

三、贪心算法

3.1 简单贪心（7道）

题号题目名称难度核心考察知识点
BISHI43讨厌鬼进货入门贪心
BISHI44灵异背包？简单贪心背包
BISHI45小红的矩阵染色简单贪心染色
BISHI46小红的魔法药剂简单贪心
BISHI47交换到最大简单贪心交换
BISHI48小红的整数配对简单贪心配对
BISHI49小红闯关中等贪心策略

3.2 贪心进阶（5道）

# 区间贪心模板
# 按右端点排序，每次选择右端点最小的区间

def interval_scheduling(intervals):
    # intervals: [(start, end), ...]
    intervals.sort(key=lambda x: x[1])
    count = 1
    end = intervals[0][1]
    for i in range(1, len(intervals)):
        if intervals[i][0] >= end:
            count += 1
            end = intervals[i][1]
    return count
题号题目名称难度核心考察知识点
BISHI50[JSOI2007]建筑抢修中等区间贪心
BISHI51低买高卖中等贪心交易
BISHI52奥赛组队中等排序贪心
BISHI53[P1080]国王游戏(简化版)中等排序不等式
BISHI54货物堆放中等贪心

四、数学算法

4.1 简单数论（4道）

import math

# 1. 质数判断
def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

# 2. 质因数分解
def prime_factors(n):
    factors = []
    i = 2
    while i * i <= n:
        while n % i == 0:
            factors.append(i)
            n //= i
        i += 1
    if n > 1:
        factors.append(n)
    return factors

# 3. GCD和LCM
def gcd(a, b):
    return math.gcd(a, b)

def lcm(a, b):
    return a * b // gcd(a, b)

# 4. 扩展欧几里得算法
def exgcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = exgcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return g, x, y
题号题目名称难度核心考察知识点
BISHI55判断质数入门质数判断
BISHI56分解质因数简单质因数分解
BISHI57最大公因数与最小公倍数简单GCD/LCM
BISHI58矩形游戏简单数学

4.2 模运算与快速幂（8道）

# 快速幂模板
def fast_pow(base, exp, mod):
    result = 1
    base = base % mod
    while exp > 0:
        if exp & 1:  # 如果exp是奇数
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result

# 矩阵快速幂
def matrix_mult(A, B, mod):
    n = len(A)
    m = len(B[0])
    p = len(B)
    C = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            for k in range(p):
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod
    return C

def matrix_pow(M, n, mod):
    if n == 1:
        return M
    if n % 2 == 0:
        half = matrix_pow(M, n // 2, mod)
        return matrix_mult(half, half, mod)
    else:
        return matrix_mult(M, matrix_pow(M, n - 1, mod), mod)

# 求乘法逆元（费马小定理，mod为质数）
def mod_inverse(a, mod):
    return fast_pow(a, mod - 2, mod)
题号题目名称难度核心考察知识点
BISHI59阶乘末尾非零数字中等数论
BISHI60大水题简单快速幂
BISHI61小q的数列简单递推
BISHI62斐波那契数列简单矩阵快速幂
BISHI63计算阶乘简单高精度
BISHI64【模板】快速幂Ⅰ‖整数中等快速幂
BISHI65【模板】分数取模中等逆元
BISHI66子数列求积中等前缀积

4.3 组合数学（6道）

# 组合数计算（预处理阶乘逆元）
MOD = 10**9 + 7

def precompute_factorials(n, mod):
    fact = [1] * (n + 1)
    inv_fact = [1] * (n + 1)
    for i in range(2, n + 1):
        fact[i] = fact[i-1] * i % mod
    inv_fact[n] = pow(fact[n], mod - 2, mod)
    for i in range(n-1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % mod
    return fact, inv_fact

def comb(n, k, fact, inv_fact, mod):
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % mod * inv_fact[n-k] % mod
题号题目名称难度核心考察知识点
BISHI67穿搭大挑战简单组合
BISHI68刷题统计简单数学
BISHI69[HNOI2008]越狱简单容斥
BISHI70【模板】组合数中等组合数
BISHI71人员分组问题中等组合
BISHI72中位数之和较难数学

4.4 高级数论（3道）

# 欧拉函数
def euler_phi(n):
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result

# 欧拉降幂
# a^b mod m = a^(b mod phi(m) + phi(m)) mod m (当b >= phi(m)时)
def euler_pow(a, b, mod):
    phi = euler_phi(mod)
    if b >= phi:
        b = b % phi + phi
    return pow(a, b, mod)
题号题目名称难度核心考察知识点
BISHI73【模板】欧拉函数Ⅰ‖单个整数中等欧拉函数
BISHI74【模板】非质模数下的乘法逆元中等逆元
BISHI75【模板】欧拉降幂中等欧拉降幂

五、搜索算法

5.1 DFS（4道）

# DFS模板
def dfs(node, visited):
    if node in visited:
        return
    visited.add(node)
    for neighbor in graph[node]:
        dfs(neighbor, visited)

# 全排列回溯
def permute(nums):
    result = []
    n = len(nums)
    
    def backtrack(path, used):
        if len(path) == n:
            result.append(path[:])
            return
        for i in range(n):
            if not used[i]:
                used[i] = True
                path.append(nums[i])
                backtrack(path, used)
                path.pop()
                used[i] = False
    
    backtrack([], [False] * n)
    return result
题号题目名称难度核心考察知识点
BISHI76迷宫寻路简单DFS
BISHI77数水坑简单Flood Fill
BISHI78全排列简单回溯
BISHI79取数游戏中等DFS+剪枝

5.2 BFS（4道）

from collections import deque

# BFS模板
def bfs(start, target):
    queue = deque([start])
    visited = {start}
    distance = {start: 0}
    
    while queue:
        node = queue.popleft()
        if node == target:
            return distance[node]
        for neighbor in get_neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                distance[neighbor] = distance[node] + 1
                queue.append(neighbor)
    return -1
题号题目名称难度核心考察知识点
BISHI80走迷宫简单BFS
BISHI81剪纸游戏简单BFS
BISHI82没挡住洪水简单BFS
BISHI83迷宫问题中等BFS最短路

5.3 二分（5道）

# 整数二分模板
# 查找满足条件的最大值（左边界）
def binary_search_left(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

# 查找满足条件的最小值（右边界）
def binary_search_right(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right + 1) // 2
        if nums[mid] > target:
            right = mid - 1
        else:
            left = mid
    return left

# 二分答案模板
def check(mid):
    # 判断mid是否满足条件
    pass

def binary_search_answer(left, right):
    while left < right:
        mid = (left + right) // 2
        if check(mid):
            right = mid
        else:
            left = mid + 1
    return left
题号题目名称难度核心考察知识点
BISHI85【模板】整数域二分简单二分查找
BISHI86圆覆盖中等二分答案
BISHI87[CQOI2010]扑克牌中等二分
BISHI88小苯的魔法染色中等二分答案
BISHI89山峰数组计数中等二分

5.4 字符串匹配算法（3道）

# KMP算法
def build_lps(pattern):
    lps = [0] * len(pattern)
    length = 0
    i = 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

def kmp_search(text, pattern):
    if not pattern:
        return 0
    lps = build_lps(pattern)
    i = j = 0
    while i < len(text):
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == len(pattern):
                return i - j
        else:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return -1

# Trie树
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end
题号题目名称难度核心考察知识点
BISHI92【模板】前缀函数(KMP)中等KMP
BISHI93【模板】Trie字典树中等Trie
BISHI94【模板】马拉车算法中等Manacher

六、树图算法

6.1 树图基础（7道）

# 链式前向星（邻接表）
class Graph:
    def __init__(self, n):
        self.n = n
        self.head = [-1] * n
        self.to = []
        self.nxt = []
        self.cnt = 0
    
    def add_edge(self, u, v):
        self.to.append(v)
        self.nxt.append(self.head[u])
        self.head[u] = self.cnt
        self.cnt += 1

# 树的遍历
def tree_dfs(root, graph, visited):
    visited.add(root)
    for child in graph[root]:
        if child not in visited:
            tree_dfs(child, graph, visited)
题号题目名称难度核心考察知识点
BISHI95【模板】链式前向星简单图存储
BISHI96先序中序后序遍历简单树遍历
BISHI97旺仔哥哥走迷宫中等图论
BISHI98谍中谍中谍…中等图论
BISHI99我朋友的朋友不是我的朋友中等图论
BISHI100二分图判定中等二分图
BISHI101世界树上找米库中等树形DP

6.2 并查集（3道）

# 并查集模板
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        # 按秩合并
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True
    
    def is_connected(self, x, y):
        return self.find(x) == self.find(y)
题号题目名称难度核心考察知识点
BISHI102【模板】并查集较难并查集
BISHI103【模板】有依赖的背包问题中等树形DP
BISHI104修复公路中等并查集+Kruskal

6.3 最短路/生成树（5道）

import heapq

# Dijkstra算法
def dijkstra(graph, start, n):
    dist = [float('inf')] * n
    dist[start] = 0
    pq = [(0, start)]
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

# Kruskal算法（最小生成树）
def kruskal(edges, n):
    # edges: [(u, v, w), ...]
    edges.sort(key=lambda x: x[2])
    uf = UnionFind(n)
    mst_weight = 0
    
    for u, v, w in edges:
        if uf.union(u, v):
            mst_weight += w
    return mst_weight
题号题目名称难度核心考察知识点
BISHI105【模板】单源最短路Ⅰ‖无权图中等BFS
BISHI106【模板】单源最短路Ⅲ‖非负权图较难Dijkstra
BISHI107【模板】最小生成树较难Kruskal/Prim
BISHI108最优乘车简单最短路
BISHI109邮递员送信中等最短路

七、数据结构

7.1 前缀和与差分（4道）

# 一维前缀和
class PrefixSum:
    def __init__(self, nums):
        self.prefix = [0]
        for num in nums:
            self.prefix.append(self.prefix[-1] + num)
    
    def range_sum(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]

# 二维前缀和
def build_2d_prefix(matrix):
    m, n = len(matrix), len(matrix[0])
    prefix = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m):
        for j in range(n):
            prefix[i+1][j+1] = prefix[i][j+1] + prefix[i+1][j] - prefix[i][j] + matrix[i][j]
    return prefix

def query_2d_prefix(prefix, r1, c1, r2, c2):
    return prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]

# 差分
class Difference:
    def __init__(self, n):
        self.diff = [0] * (n + 2)
    
    def add(self, left, right, val):
        self.diff[left] += val
        self.diff[right + 1] -= val
    
    def get_result(self):
        result = []
        cur = 0
        for i in range(len(self.diff) - 1):
            cur += self.diff[i]
            result.append(cur)
        return result
题号题目名称难度核心考察知识点
BISHI110【模板】静态区间和(前缀和)简单前缀和
BISHI111【模板】差分简单差分
BISHI112【模板】二维前缀和中等二维前缀和
BISHI113【模板】二维差分中等二维差分

7.2 双指针（7道）

# 滑动窗口模板
from collections import defaultdict

def sliding_window(s, t):
    need = defaultdict(int)
    for char in t:
        need[char] += 1
    required = len(t)
    left = 0
    min_len = float('inf')
    min_start = 0
    
    for right, char in enumerate(s):
        if need[char] > 0:
            required -= 1
        need[char] -= 1
        
        while required == 0:
            if right - left + 1 < min_len:
                min_len = right - left + 1
                min_start = left
            need[s[left]] += 1
            if need[s[left]] > 0:
                required += 1
            left += 1
    
    return "" if min_len == float('inf') else s[min_start:min_start + min_len]
题号题目名称难度核心考察知识点
BISHI114【模板】滑动窗口简单滑动窗口
BISHI115可匹配子段计数简单双指针
BISHI116【模板】双指针中等双指针
BISHI117小苯的IDE括号问题(easy)中等双指针
BISHI118相差不超过k的最多数中等滑动窗口
BISHI119小红的01子序列构造(easy)中等双指针
BISHI120？？？较难双指针

7.3 单调栈和单调队列（2道）

# 单调栈 - 下一个更大元素
def next_greater_elements(nums):
    n = len(nums)
    result = [-1] * n
    stack = []  # 存储索引
    
    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            result[stack.pop()] = nums[i]
        stack.append(i)
    return result

# 单调队列 - 滑动窗口最大值
from collections import deque

def max_sliding_window(nums, k):
    result = []
    dq = deque()  # 存储索引，保持单调递减
    
    for i, num in enumerate(nums):
        # 移除窗口外的元素
        while dq and dq[0] <= i - k:
            dq.popleft()
        # 保持单调递减
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result
题号题目名称难度核心考察知识点
BISHI121数列后缀极大位置统计简单单调栈
BISHI122区间后缀极大位置计数简单单调栈

7.4 倍增/LCA与ST表（3道）

# LCA（最近公共祖先）- 倍增法
class LCA:
    def __init__(self, n, graph):
        self.n = n
        self.graph = graph
        self.LOG = 20
        self.parent = [[-1] * n for _ in range(self.LOG)]
        self.depth = [0] * n
        self.dfs(0, -1)
        self.build()
    
    def dfs(self, u, p):
        self.parent[0][u] = p
        for v in self.graph[u]:
            if v != p:
                self.depth[v] = self.depth[u] + 1
                self.dfs(v, u)
    
    def build(self):
        for k in range(1, self.LOG):
            for v in range(self.n):
                if self.parent[k-1][v] != -1:
                    self.parent[k][v] = self.parent[k-1][self.parent[k-1][v]]
    
    def query(self, u, v):
        if self.depth[u] < self.depth[v]:
            u, v = v, u
        # 将u提升到与v同一深度
        for k in range(self.LOG - 1, -1, -1):
            if self.depth[u] - (1 << k) >= self.depth[v]:
                u = self.parent[k][u]
        if u == v:
            return u
        # 同时提升u和v
        for k in range(self.LOG - 1, -1, -1):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]

# ST表（RMQ）
class SparseTable:
    def __init__(self, arr):
        n = len(arr)
        self.LOG = (n).bit_length()
        self.st = [[0] * n for _ in range(self.LOG)]
        self.st[0] = arr[:]
        
        for k in range(1, self.LOG):
            for i in range(n - (1 << k) + 1):
                self.st[k][i] = max(self.st[k-1][i], self.st[k-1][i + (1 << (k-1))])
    
    def query(self, l, r):
        k = (r - l + 1).bit_length() - 1
        return max(self.st[k][l], self.st[k][r - (1 << k) + 1])
题号题目名称难度核心考察知识点
BISHI123环形字符串跃迁中等倍增
BISHI124【模板】最近公共祖先(LCA)中等LCA
BISHI125【模板】静态区间最值中等ST表

7.5 高级数据结构（5道）

# 树状数组（Binary Indexed Tree）
class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    def lowbit(self, x):
        return x & (-x)
    
    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += self.lowbit(i)
    
    def query(self, i):
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= self.lowbit(i)
        return res
    
    def range_query(self, l, r):
        return self.query(r) - self.query(l - 1)

# 线段树
class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.lazy = [0] * (4 * self.n)
        self.build(arr, 1, 0, self.n - 1)
    
    def build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
            return
        mid = (start + end) // 2
        self.build(arr, 2*node, start, mid)
        self.build(arr, 2*node+1, mid+1, end)
        self.tree[node] = self.tree[2*node] + self.tree[2*node+1]
    
    def push_down(self, node, start, end):
        if self.lazy[node] != 0:
            mid = (start + end) // 2
            self.tree[2*node] += self.lazy[node] * (mid - start + 1)
            self.tree[2*node+1] += self.lazy[node] * (end - mid)
            self.lazy[2*node] += self.lazy[node]
            self.lazy[2*node+1] += self.lazy[node]
            self.lazy[node] = 0
    
    def update(self, node, start, end, l, r, val):
        if l <= start and end <= r:
            self.tree[node] += val * (end - start + 1)
            self.lazy[node] += val
            return
        self.push_down(node, start, end)
        mid = (start + end) // 2
        if l <= mid:
            self.update(2*node, start, mid, l, r, val)
        if r > mid:
            self.update(2*node+1, mid+1, end, l, r, val)
        self.tree[node] = self.tree[2*node] + self.tree[2*node+1]
    
    def query(self, node, start, end, l, r):
        if l <= start and end <= r:
            return self.tree[node]
        self.push_down(node, start, end)
        mid = (start + end) // 2
        res = 0
        if l <= mid:
            res += self.query(2*node, start, mid, l, r)
        if r > mid:
            res += self.query(2*node+1, mid+1, end, l, r)
        return res
题号题目名称难度核心考察知识点
BISHI126【模板】动态区间和Ⅱ‖区间修改+查询较难线段树
BISHI127区间根号与区间求和中等线段树
BISHI128区间加乘与单点求值中等线段树
BISHI129区间增量与区间小于计数中等树状数组
BISHI130区间取反与区间数一中等线段树

八、动态规划

8.1 简单动态规划（6道）

# 1. 线性DP - 爬楼梯
class Solution:
    def climbStairs(self, n):
        if n <= 2:
            return n
        prev2, prev1 = 1, 2
        for i in range(3, n + 1):
            current = prev1 + prev2
            prev2, prev1 = prev1, current
        return prev1

# 2. 0-1背包
def knapsack_01(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)
    for i in range(n):
        for j in range(capacity, weights[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    return dp[capacity]

# 3. 完全背包
def knapsack_complete(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)
    for i in range(n):
        for j in range(weights[i], capacity + 1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    return dp[capacity]

# 4. 最长上升子序列
def length_of_lis(nums):
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# 5. 最大子数组和
def max_subarray_sum(nums):
    dp = [0] * len(nums)
    dp[0] = nums[0]
    max_sum = nums[0]
    for i in range(1, len(nums)):
        dp[i] = max(nums[i], dp[i-1] + nums[i])
        max_sum = max(max_sum, dp[i])
    return max_sum
题号题目名称难度核心考察知识点
BISHI131数楼梯简单递推
BISHI132小红的地砖简单线性DP
BISHI133最长不下降子序列简单LIS
BISHI134最大子段和简单线性DP
BISHI135三角形取数(Hard)中等线性DP
BISHI136【模板】01背包简单背包DP

8.2 进阶动态规划（12道）

# 1. 完全背包
def knapsack_complete(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)
    for i in range(n):
        for j in range(weights[i], capacity + 1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    return dp[capacity]

# 2. 多重背包（二进制优化）
def knapsack_multiple(weights, values, counts, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)
    for i in range(n):
        # 二进制拆分
        k = 1
        while counts[i] > 0:
            use = min(k, counts[i])
            w, v = weights[i] * use, values[i] * use
            for j in range(capacity, w - 1, -1):
                dp[j] = max(dp[j], dp[j - w] + v)
            counts[i] -= use
            k *= 2
    return dp[capacity]

# 3. 树形DP
def tree_dp(graph, values, root=0):
    n = len(graph)
    dp = [[0, 0] for _ in range(n)]  # [不选, 选]
    
    def dfs(u, parent):
        dp[u][1] = values[u]
        for v in graph[u]:
            if v != parent:
                dfs(v, u)
                dp[u][0] += max(dp[v][0], dp[v][1])
                dp[u][1] += dp[v][0]
    
    dfs(root, -1)
    return max(dp[root])

# 4. 区间DP - 石子合并
def stone_merge(stones):
    n = len(stones)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + stones[i]
    
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + prefix[j+1] - prefix[i]
                dp[i][j] = min(dp[i][j], cost)
    return dp[0][n-1]

# 5. 状态压缩DP
def tsp(dist):
    n = len(dist)
    dp = [[float('inf')] * n for _ in range(1 << n)]
    dp[1][0] = 0  # 从城市0出发
    
    for mask in range(1 << n):
        for u in range(n):
            if not (mask & (1 << u)):
                continue
            for v in range(n):
                if mask & (1 << v):
                    continue
                new_mask = mask | (1 << v)
                dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v])
    
    return min(dp[(1 << n) - 1][i] + dist[i][0] for i in range(n))
题号题目名称难度核心考察知识点
BISHI137【模板】完全背包中等完全背包
BISHI138【模板】多重背包中等多重背包
BISHI139【模板】二维费用背包中等二维背包
BISHI140【模板】分组背包较难分组背包
BISHI141来硬的较难背包DP
BISHI142最大学分较难背包DP
BISHI143没有上司的舞会较难树形DP
BISHI144食物链计数较难树形DP
BISHI145石子合并较难区间DP
BISHI146收集金币中等状态压缩DP
BISHI147旅行者的大逃脱困难综合DP

附录：ACM模式输入输出模板

import sys

# 快速输入
input = sys.stdin.readline

# 读取一行整数
n = int(input())

# 读取一行多个整数
a, b, c = map(int, input().split())

# 读取一行列表
arr = list(map(int, input().split()))

# 读取n行
n = int(input())
matrix = []
for _ in range(n):
    row = list(map(int, input().split()))
    matrix.append(row)

# 读取到文件末尾
for line in sys.stdin:
    a, b = map(int, line.split())
    # 处理逻辑

# 快速输出
print(' '.join(map(str, result)))

# 多组测试数据
while True:
    try:
        n = int(input())
        # 处理逻辑
    except:
        break

附录：时间/空间复杂度速查表

算法类型典型时间复杂度空间复杂度
数组遍历O(n)O(1)
双指针O(n)O(1)
二分查找O(log n)O(1)
哈希查找O(1)O(n)
快速排序O(n log n)平均O(log n)
归并排序O(n log n)O(n)
堆排序O(n log n)O(1)
二叉树遍历O(n)O(h)
图的BFS/DFSO(V+E)O(V)
动态规划O(n)或O(n²)O(n)或O(n²)
回溯算法O(2ⁿ)或O(n!)O(n)
DijkstraO((V+E)log V)O(V)
线段树操作O(log n)O(n)
树状数组操作O(log n)O(n)

参考资源

# python # 算法 # 开发语言
Logo
亚马逊云科技技术品牌专区

更多推荐

cover

基于STM32的全屋环境智能监测与预警终端设计

avatar 亚马逊云科技技术品牌专区

Keras：面向人类的深度学习库

Keras3支持多后端（TensorFlow、PyTorch、JAX），通过设置环境变量切换，兼容指定版本。pip安装后可用Sequential API快速构建CNN模型，如MNIST分类示例，实

avatar 亚马逊云科技技术品牌专区

AI行业日报｜2026-09-25：5个热点事件

本期行业动态聚焦于端侧算力重构、自主智能体工作流、开发工具经济模型、网络隔离架构设计与公共部门合规审查。以下结合一线技术场景进行结构化梳理，供 AI 研究员与软件工程团队参考。 PrismML 正将其轻量级语言模型适配至搭载高通处理器的智能眼镜终端 1 。该平台的核心战略指向开源权重模型的本地化运行，旨在最大化挖掘穿戴设备现有算力的利用效率 1 。对于嵌入式与边缘计算开发者而言，此类微型模型向低功

avatar 亚马逊云科技技术品牌专区