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

在这里插入图片描述

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

目录

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

一、题单概览

1.1 分类结构统计

大类 子分类 题目数量 核心知识点
基础算法 简单库函数数据结构 8 vector、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 欧拉函数、乘法逆元、欧拉降幂
搜索算法 DFS 4 深度优先搜索、回溯
搜索算法 BFS 4 广度优先搜索、最短路径
搜索算法 二分 5 整数二分、实数二分
搜索算法 记忆化搜索 2 记忆化、剪枝
搜索算法 字符串匹配 3 KMP、Trie树、马拉车
树图算法 树图基础 7 链式前向星、遍历、图论基础
树图算法 并查集 3 并查集、路径压缩
树图算法 最短路/生成树 5 Dijkstra、BFS、Kruskal/Prim
数据结构 前缀和与差分 4 一维/二维前缀和、差分
数据结构 双指针 7 滑动窗口、双指针技巧
数据结构 单调栈/队列 2 单调栈、单调队列
数据结构 倍增/LCA/ST表 3 LCA、RMQ、倍增
数据结构 高级数据结构 5 线段树、树状数组
动态规划 简单DP 6 线性DP、背包基础
动态规划 进阶DP 12 树形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 被打乱的异或和 简单 异或运算
BISHI33 Poi的新加法(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/DFS O(V+E) O(V)
动态规划 O(n)或O(n²) O(n)或O(n²)
回溯算法 O(2ⁿ)或O(n!) O(n)
Dijkstra O((V+E)log V) O(V)
线段树操作 O(log n) O(n)
树状数组操作 O(log n) O(n)

参考资源

# python # 算法 # 开发语言
Logo
EazyDevelop社区

一站式 AI 云服务平台

更多推荐

cover

Harmony6.0 社团活动页面实战：构建高质感校园招募与活动排期界面

avatar EazyDevelop社区
cover

Flutter × Harmony6.0 社团活动管理页面实战：从组件设计到鸿蒙风格 UI 构建

avatar EazyDevelop社区
cover

基于零代码平台的订单利润分流数据加工

avatar EazyDevelop社区