Python 竞赛模板

基础设置

输入输出

输入

# 单个整数
n = int(input())

# 多个整数（空格分隔）
a, b = map(int, input().split())

# 一行整数转列表
arr = list(map(int, input().split()))

# 去除换行符
s = input().strip()  # 去除首尾空白（含 \n）

# 读取 n 行到列表
arr = [int(input()) for _ in range(n)]

# 读取到文件结尾（EOF）：直接遍历 sys.stdin
for line in sys.stdin:
    a, b = map(int, line.strip().split())
    print(a + b)

# ⚠️ input() 会保留换行符，需要 strip()
s = input().strip()  # 去除 '\n'

# ⚠️ int() 会自动去除空白和符号
int("  123  ")  # 123
int("-123")     # -123
int("+123")     # 123

输出

print(x)           # 单个值
print(a, b, c)     # 多个值（默认空格分隔）

# 空格分隔的列表
print(*ans)                    # 解包输出
print(" ".join(map(str, ans))) # join 输出

# 不换行输出
print(x, end='')     # 末尾不换行
print(x, end=' ')    # 末尾加空格

# 交互题：必须加 flush！强制刷新缓冲区
print(f"? {mid}")
sys.stdout.flush()

常用配置

# 加速输入
import sys
input = sys.stdin.readline
# 设置递归深度（DFS 必备）
sys.setrecursionlimit(10**6)

# 常用导入
import math
import itertools
import bisect
from collections import deque, Counter, defaultdict

# 常用常量
INF = 10**18          # 无穷大（整数，推荐）
MOD = 10**9 + 7       # 取模

# ⚠️ 禁止用浮点数作为 INF，会导致 TLE
# INF = 1e9           # 错误！浮点数运算慢
# INF = float('inf')  # 错误！浮点数运算慢

# ⚠️ 常见陷阱

# 列表 * n 可能是浅拷贝
a = [[0] * 3] * 3     # 错误！三个引用同一列表
a = [[0] * 3 for _ in range(3)]  # 正确

# 浮点数比较
abs(a - b) < 1e-9     # 判断浮点数相等

基础数据类型

复杂度速查

数据结构	操作	时间复杂度
列表	索引访问/切片	O(1) / O(k)
	append/pop(末尾)	O(1)
	insert/pop(开头)	O(n)
	in 检查	O(n)
集合/字典	in 检查	O(1) 平均
	add/insert	O(1) 平均
	remove/delete	O(1) 平均
堆	push/pop	O(log n)
	查看最值	O(1)
排序	sort/sorted	O(n log n)
遍历	所有元素	O(n)

注：集合/字典的 O(1) 是平均情况，最坏情况可能为 O(n)

列表操作

初始化与创建

# 自动初始化为全0
a = [0] * n

# 二维列表（注意：不能用 [[0]*m]*n，是浅拷贝！）
grid = [[0] * m for _ in range(n)]

# 列表推导式
squares = [x * x for x in range(n)]
evens = [x for x in range(n) if x % 2 == 0]

# 基本格式: [表达式 for 变量 in 可迭代对象 if 条件]
# 示例: 读取 q 行整数
S_list = [int(input()) for _ in range(q)]

增删改操作

# 尾部操作（O(1)）
a.append(x)      # 尾部添加
a.pop()          # 尾部删除

# 头部操作（O(n)，慎用！）
a.insert(0, x)   # 头部插入
a.pop(0)         # 头部删除

# 任意位置
a.insert(i, x)   # 在位置 i 插入
a.pop(i)         # 删除位置 i 的元素
a.remove(x)      # 删除值为 x 的第一个元素

# 批量操作
a.extend([1, 2, 3])    # 追加多个元素
a += [1, 2, 3]         # 同上
a.clear()              # 清空列表

查询操作

# 最大/最小值
mx = max(a)
mn = min(a)
idx = a.index(max(a))  # 最大值的索引

# 统计
a.count(x)      # 元素 x 出现的次数
len(a)          # 列表长度

# 检查存在
x in a          # O(n) 操作，频繁查询建议用 set
x not in a

# 查找索引
a.index(x)      # 返回第一个 x 的索引，不存在会报错
a.index(x, start, end)  # 在指定范围内查找

排序操作

# 原地排序
a.sort()                # 升序
a.sort(reverse=True)    # 降序

# 返回新列表
b = sorted(a)
b = sorted(a, reverse=True)

# 多关键字排序
a.sort(key=lambda x: (-x[0], x[1]))  # 第一项降序，第二项升序

# 多列表打包排序（同步排序）
x = [3, 1, 2]
y = ['c', 'a', 'b']
sorted(zip(x, y))  # → [(1, 'a'), (2, 'b'), (3, 'c')]

切片与反转

# 切片（不修改原列表）
a[start:end]      # [start, end)，左闭右开
a[start:end:step] # 带步长
a[::-1]           # 反转
a[::2]            # 隔一个取一个
a[-1]             # 最后一个元素
a[-3:]            # 最后三个元素

# 反转（修改原列表）
a.reverse()       # 原地反转
a = a[::-1]       # 创建新列表

算法题常用技巧

# 去重（保持顺序）
list(dict.fromkeys(a))

# 累加求和
sum(a)

# 前缀和
from itertools import accumulate
prefix = list(accumulate(a))

# 相邻元素差分
diff = [a[i+1] - a[i] for i in range(len(a)-1)]

# 二维列表展平
flat = [x for row in mat for x in row]

# 二维列表转置
transposed = list(zip(*matrix))

# 二分查找插入位置
import bisect
pos = bisect.bisect_left(a, x)

字符串

基本操作

s = "hello"
lst = list(s)        # 字符串转列表

# 大小写转换
s.upper()            # 转大写
s.lower()            # 转小写
s.capitalize()       # 首字母大写
s.swapcase()         # 大小写互换

# 去除空白
s.strip()            # 去除首尾空白
s.lstrip()           # 去除左边空白
s.rstrip()           # 去除右边空白

查找与替换

# 查找
s.find('a')          # 返回第一个 'a' 的索引，不存在返回 -1
s.rfind('a')         # 从右边找
s.index('a')         # 同 find，但不存在会报错
s.count('a')         # 统计字符出现次数
s.count('abc')       # 统计子串出现次数

# 替换
s.replace('old', 'new')       # 替换所有
s.replace('old', 'new', 1)    # 只替换第一个
s.replace(c, ' ')             # 字符替换为空格

判断方法

# 字符/字符串判断
'a'.isdigit()        # 单字符判断：False
'5'.isdigit()        # 数字字符：True
s.isdigit()          # 全是数字
s.isalpha()          # 全是字母
s.islower()          # 全是小写
s.isupper()          # 全是大写

# 回文判断
s == s[::-1]         # 字符串是否回文

格式化与对齐

# 填充对齐
s = s.ljust(width, '0')   # 左边补 '0' 到指定长度
s = s.rjust(width, '0')   # 右边补 '0'
s = s.center(width, '0')  # 居中补 '0'

# 补零
s = s.zfill(5)            # 左边补 '0' 到宽度 5

# 分割与连接
s.split()                 # 按空白分割（默认）
s = ' '.join(lst)        # 用空格连接
s = ''.join(lst)          # 直接连接

去重与排序

# 字符串去重（保持顺序）
s = ''.join(dict.fromkeys(s))

# 字符串排序
sorted_s = ''.join(sorted(s))           # 按字符排序
words.sort()                            # 列表按字典序排序
# Python 字符串默认按字典序比较：'A' < 'Z' < 'a' < 'z'

ASCII 码与进制转换

# ord() 和 chr()
ord('A')      # 字符转 ASCII 码: 65
chr(97)       # ASCII 码转字符: 'a'

# 字母序号转换（A-Z → 0-25）
ord('A') - ord('A')  # 0

# 数字字符转数字
int('5')           # 5
ord('5') - ord('0') # 5

# 进制转换
int("FF", 16)      # 十六进制转十进制: 255
int("101", 2)      # 二进制转十进制: 5
int("77", 8)       # 八进制转十进制: 63

# 十进制转其他进制
bin(255)           # '0b11111111'
oct(255)           # '0o377'
hex(255)           # '0xff'

最长数字子串

import re

# 提取连续数字串
s = "abc123xyz456"
arr = re.findall(r'\d+', s)  # ['123', '456']

# 找最长数字子串
max_len = max(len(x) for x in arr)
res = ''.join(x for x in arr if len(x) == max_len)

最长回文子串

s = input().strip()

res = ""

def expand(l, r):
    """从中心 (l, r) 向两边扩展，返回最长回文子串"""
    while l >= 0 and r < len(s) and s[l] == s[r]:
        l -= 1
        r += 1
    return s[l + 1: r]

for i in range(len(s)):
    res = max(res, expand(i, i), key=len)     # 奇数长度回文
    res = max(res, expand(i, i + 1), key=len) # 偶数长度回文

print(len(res))

集合

s = set()
s.add(x)
s.remove(x)      # 不存在会报错
s.discard(x)     # 不存在不报错
s.pop()      # 删除并返回一个元素
print(x in s)           # 检查元素

# 集合运算
s1 & s2          # 交集
s1 | s2          # 并集
s1 - s2          # 差集
s1 ^ s2          # 对称差集

# 子集判断
s1 <= s2         # s1 是否是 s2 的子集（等价于 s1.issubset(s2)）
s1 < s2          # s1 是否是 s2 的真子集
s1.issubset(s2)  # 同上，方法写法

# 示例：检查 s1 中每个元素是否都在 s2 中
is_subset = all(ch in s2 for ch in s1)  # 逐个检查
is_subset = s1 <= s2                     # 直接判断（推荐）

# set 没有 sort() 方法
# ✅ 正确：用 sorted()
lst = sorted(s)

字典

d = {}
d.get(key, default)    # 获取值，不存在返回 default

# 增量赋值
d[key] = d.get(key, 0) + value

# 计数器：统计字符出现次数
from collections import Counter
cnt = Counter(arr)
cnt.values()           # 获取所有出现次数的值（dict_values 类型）
min(cnt.values())      # 获取最小出现次数
max(cnt.values())      # 获取最大出现次数

d = {'x': 1, 'y': 2}
for k, v in d.items():
    print(k, v)

defaultdict

from collections import defaultdict

# int 默认值：计数
d = defaultdict(int)
d["a"] += 1  # 不需要先判断键是否存在

# list 默认值：分组
d = defaultdict(list)
d["a"].append(1)  # 自动创建空列表

# 常用场景
# 1. 计数
s = "abracadabra"
cnt = defaultdict(int)
for char in s:
    cnt[char] += 1   # 不需要先判断键是否存在
# {'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1}

# 对比普通字典：
d = {}
for char in s:
  if char not in d:
	  d[char] = 0
  d[char] += 1

# 2. 分组
words = ["apple", "banana", "apricot"]
group = defaultdict(list)
for w in words:
    group[w[0]].append(w)
# {'a': ['apple', 'apricot'], 'b': ['banana']}

堆（优先队列）

import heapq
heap = []              # 小顶堆（Python 只有小顶堆）
heapq.heapify(heap)   # 转堆
heapq.heappush(heap, x)  # 插入
heapq.heappop(heap)    # 弹出最小值
heap[0]               # 查看最小值
heapq.heapreplace(heap, x)  # 弹出+插入（原子操作）
# 大顶堆：存负值
heapq.heappush(heap, -x)
x = -heapq.heappop(heap)  # 取出时再取负，得到原值

房间分配（优先队列）

# 最少房间数：按到达时间排序，用小顶堆存储离开时间
def min_rooms(timetable):
    timetable.sort()  # 按到达时间排序
    heap = []
    for arrival, departure in timetable:
        if heap and arrival > heap[0]:  # 有房间空出
            heapq.heapreplace(heap, departure)
        else:  # 需要新房间
            heapq.heappush(heap, departure)
    return len(heap)

求 Top K 大元素：

def top_k(arr, k):
    heap = arr[:k]
    heapq.heapify(heap)
    for x in arr[k:]:
        if x > heap[0]:
            heapq.heapreplace(heap, x)
    return sorted(heap, reverse=True)

合并 K 个有序数组：

def merge_sorted_arrays(arrays):
    result = []
    heap = [(arr[0], i, 0) for i, arr in enumerate(arrays) if arr]
    heapq.heapify(heap)
    while heap:
        val, i, j = heapq.heappop(heap)
        result.append(val)
        if j + 1 < len(arrays[i]):
            heapq.heappush(heap, (arrays[i][j+1], i, j+1))
    return result

双端队列

from collections import deque

dq = deque()
dq.append(x)
dq.appendleft(x)
dq.pop()
dq.popleft()

单调队列

from collections import deque

# 求窗口最小值（递增队列）
q = deque()
for i in range(n):
    while q and q[0][0] < i - k:      # 超出窗口
        q.popleft()
    while q and q[-1][1] >= arr[i]:   # 队尾不优
        q.pop()
    q.append((i, arr[i]))
    min_val = q[0][1]

# 求窗口最大值（递减队列）
q = deque()
for i in range(n):
    while q and q[0][0] < i - k:
        q.popleft()
    while q and q[-1][1] <= arr[i]:
        q.pop()
    q.append((i, arr[i]))
    max_val = q[0][1]

核心算法

二分查找

在有序数组上查找

import bisect

arr = sorted([...])  # 先排序

# lower_bound: 第一个 >= x 的位置
pos = bisect.bisect_left(arr, x)

# upper_bound: 第一个 > x 的位置
pos = bisect.bisect_right(arr, x)

手动实现

# 查找左边界（第一个 >= target 的位置）
def lower_bound(arr, x):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

# 查找右边界（第一个 > target 的位置）
def upper_bound(arr, x):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] <= x:
            lo = mid + 1
        else:
            hi = mid
    return lo

在单调函数上查找

def last_true(lo: int, hi: int, f: Callable[[int], bool]) -> int:
    """查找最大的 x 使得 f(x) = true"""
    lo -= 1
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # 向上取整
        if f(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

def first_true(lo: int, hi: int, f: Callable[[int], bool]) -> int:
    """查找最小的 x 使得 f(x) = true"""
    hi += 1
    while lo < hi:
        mid = lo + (hi - lo) // 2  # 向下取整
        if f(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

滑动窗口

1. 固定窗口大小（求最大/最小窗口和）

适用场景：给定固定大小 k，求所有窗口中最大/最小的和

def sliding_window(arr, k):
    """求大小为 k 的窗口的最大和"""
    window_sum = sum(arr[:k])  # 初始化第一个窗口的和
    max_sum = window_sum
    for i in range(k, len(arr)):
        # 滑动窗口：加入新元素 arr[i]，移除旧元素 arr[i-k]
        window_sum += arr[i] - arr[i-k]
        max_sum = max(max_sum, window_sum)
    return max_sum

2. 对撞指针（双指针从两端向中间）

适用场景：有序数组中找两个数之和等于目标值

# 找到两个索引 i 和 j，使得 a_i + a_j = x
# 前提：数组已排序
n = int(input())
x = int(input())
nums = [(int(input()), i) for i in range(n)]  # (值, 原索引)
nums.sort()  # 按值排序

l = 0
r = n - 1
while l < r:
    s = nums[l][0] + nums[r][0]
    if s == x:
        print(nums[l][1] + 1, nums[r][1] + 1)  # 输出原索引（1-indexed）
        exit()
    elif s < x:
        l += 1  # 和太小，左指针右移
    else:
        r -= 1  # 和太大，右指针左移
print("IMPOSSIBLE")

3. 可变窗口（双指针同向）

场景一：满足条件的最长/最短窗口

适用场景：窗口和 ≤ t 的最大长度

# 求时间总和不超过 t 的最多任务数
n = int(input())
t = int(input())
timeNeed = [int(input()) for _ in range(n)]

l = 0
sum_time = 0
ans = 0
for r in range(n):
    sum_time += timeNeed[r]  # 右指针扩展窗口
    while sum_time > t and l <= r:  # 窗口不满足条件，左指针收缩
        sum_time -= timeNeed[l]
        l += 1
    ans = max(ans, r - l + 1)  # 更新最大窗口长度
print(ans)

场景二：无重复元素的最长窗口

适用场景：求不含重复元素的最长子串/子数组

# 求无重复字符的最长子串长度
s = input().strip()
n = len(s)
arr = list(s)

window = set()
l = 0
ans = 0
for r in range(n):
    while arr[r] in window:  # 当前字符已存在，收缩窗口
        window.remove(arr[l])
        l += 1
    window.add(arr[r])
    ans = max(ans, r - l + 1)
print(ans)

# 示例：
# 输入："abcabcbb"
# 输出：3（"abc"）

滑动窗口通用模板

# 通用框架
l = 0
ans = 0  # 或其他初始化
for r in range(n):
    # 1. 将 arr[r] 加入窗口（扩展右边界）
    # ...

    # 2. 窗口不满足条件时，收缩左边界
    while 不满足条件:
        # 移除 arr[l]
        # ...
        l += 1

    # 3. 更新答案
    ans = max(ans, r - l + 1)

场景三：离线区间查询（莫队思想）

适用场景：多个区间查询，按端点排序后用双指针处理

# 区间不同种类数查询（离线 + 双指针）
# 输入: n=种类数, w=区间跨度, K=查询数, M=记录数
# 记录格式: (时间, 种类ID)
# 查询: 给定起始时间 S，求 [S, S+w-1] 区间内的不同种类数

# 1. 构建查询 (起始, 结束, 索引)
queries = [(S[i], S[i] + w - 1, i) for i in range(K)]
queries.sort(key=lambda x: x[1])  # 按结束时间排序（离线处理关键）

# 2. 记录按时间排序
records.sort()

# 3. 双指针滑动窗口
ans = [0] * K
l = r = 0
cnt = 0
appear = {}  # 种类ID -> 出现次数

for start, end, idx in queries:
    # 右指针：扩展到 end
    while r < len(records) and records[r][0] <= end:
        id = records[r][1]
        appear[id] = appear.get(id, 0) + 1
        if appear[id] == 1:
            cnt += 1
        r += 1

    # 左指针：收缩到 start
    while l < len(records) and records[l][0] < start:
        id = records[l][1]
        appear[id] -= 1
        if appear[id] == 0:
            cnt -= 1
        l += 1

    ans[idx] = cnt

# 离线处理优势：利用区间端点的单调性，避免重复计算
# 时间复杂度：O(M log K + M) = O(M log K)

最大子数组和（Kadane 算法）

适用场景：求连续子数组的最大和

算法思想：动态规划，cur 表示以当前位置结尾的最大子数组和

• 若 cur >= 0：继续累加（对后续有贡献）
• 若 cur < 0：重置为 0（负数只会让和更小，不如重新开始）

n = int(input())
a = [int(x) for x in input().split()]

cur = 0  # 以当前位置结尾的最大子数组和
ans = float('-inf')  # 全局最大和
for i in range(n):
    cur += a[i]
    ans = max(ans, cur)
    if cur < 0:
        cur = 0  # 负数没有贡献，重新开始
print(ans)

BFS/DFS

图论基础：BFS 适合求最短路，DFS 适合遍历/搜索

# 邻接表
adj = [[] for _ in range(n)]
# 无向图
adj[u].append(v)
adj[v].append(u)

adj[u].append((v, w))    # 带权重

DFS（深度优先搜索）

特点：递归/栈实现，一条路走到黑

visited = [False] * n

def dfs(u):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            dfs(v)

# 处理不连通图
for i in range(n):
    if not visited[i]:
        dfs(i)

BFS（广度优先搜索）

特点：队列实现，按层遍历，求无权图最短路

from collections import deque

visited = [False] * n

def bfs(start):
    q = deque([start])
    visited[start] = True
    while q:
        u = q.popleft()
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                q.append(v)

# 处理不连通图
for i in range(n):
    if not visited[i]:
        bfs(i)

前缀和

# 一维前缀和
prefix = [0] * (n + 1)
for i in range(n):
  prefix[i + 1] = prefix[i] + a[i]  # a 是 0-indexed

# 查询区间 [l, r]（1-indexed）
def query(l, r):
  return prefix[r] - prefix[l - 1]

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

全排列

from itertools import permutations, combinations

# 全排列
for perm in permutations(arr):
    print(list(perm))  # [1, 2, 3]

# 组合
for comb in combinations(arr, r):
    pass

差分数组

diff = [0] * (n + 1)

# 对区间 [l, r] 加 v
diff[l] += v
diff[r+1] -= v

# 还原
arr = [0] * n
curr = 0
for i in range(n):
    curr += diff[i]
    arr[i] = curr

动态规划

# ===== 1. 背包问题 =====
# 01 背包（每个物品选0或1次）
def knapsack_01(n, W, weights, values):
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(W, weights[i] - 1, -1):  # 倒序遍历
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

# 完全背包（每个物品可选无限次）
def knapsack_complete(n, W, weights, values):
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(weights[i], W + 1):  # 正序遍历
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

# 多重背包（每个物品可选有限次）- 二进制优化
def knapsack_multi(n, W, weights, values, counts):
    items = []  # 转化为01背包
    for i in range(n):
        k = 1
        c = counts[i]
        while c > 0:
            take = min(k, c)
            items.append((weights[i] * take, values[i] * take))
            c -= take
            k *= 2
    dp = [0] * (W + 1)
    for w, v in items:
        for j in range(W, w - 1, -1):
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[W]

# ===== 计数DP（爬楼梯/骰子问题）=====
# 每次可以走1~k步，求到达n级台阶的走法数
def count_ways(n, k):
    dp = [0] * (n + 1)
    dp[0] = 1  # 基础情况：到达0级只有1种方式（不走）
    for i in range(1, n + 1):
        dp[i] = sum(dp[max(0, i-k):i]) % MOD
    return dp[n]

# 简化为：每次走1~6步（骰子问题）
dp = [1]
for i in range(int(input())):
    dp.append(sum(dp[-6:]) % MOD)
print(dp[-1])

# ===== 2. 最长上升子序列 (LIS) =====
def lis(arr):
    import bisect
    dp = []
    for x in arr:
        pos = bisect.bisect_left(dp, x)
        if pos == len(dp):
            dp.append(x)
        else:
            dp[pos] = x
    return len(dp)

# ===== 3. 最长公共子序列 (LCS) =====
def lcs(s1, s2):
    n, m = len(s1), len(s2)
    dp = [[0] * (m+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, m+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[n][m]

# ===== 4. 编辑距离 =====
def edit_distance(s1, s2):
    n, m = len(s1), len(s2)
    dp = [[0] * (m+1) for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = i
    for j in range(m+1):
        dp[0][j] = j
    for i in range(1, n+1):
        for j in range(1, m+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[n][m]

# ===== 5. 区间 DP =====
def interval_dp(n, cost):
    # dp[i][j] = 合并 i~j 的最小代价
    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] = min(dp[i][k] + dp[k+1][j] for k in range(i, j))
    return dp[0][n-1]

数论

向上取整

# 向上取整到 k 的倍数
(n + k - 1) // k * k

import math
math.ceil(n / k) * k      # 更易读

四舍五入

# 1. 四舍五入（通用模板，避免浮点误差）
def round_div(a, b):
    # 计算 a / b，四舍五入到整数
    # 原理：判断小数部分是否 >= 0.5
    return a // b + (2 * (a % b) >= b)
# 示例：7 // 4 = 1，但 round_div(7, 4) = 2

# 2. 四舍五入（浮点数版本）
n = float(input())
if n - int(n) >= 0.5:
    print(int(n) + 1)
else:
    print(int(n))

质因数分解

def prime_factors(n):
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors

约瑟夫环

# n 个人围成一圈，每数到 k 就淘汰一人，求最后存活者的初始位置
def josephus(n, k):
    if n == 1:
        return 0
    return (josephus(n-1, k) + k) % n

K进制转换

# 数字 -> k进制字符串（每位对应字符集 s）
def idx_to_password(idx, k, m, s):
    res = []
    for _ in range(m):
        res.append(s[idx % k])
        idx //= k
    return ''.join(reversed(res))

# k进制字符串 -> 数字
def password_to_idx(password, k, s):
    idx = 0
    for ch in password:
        idx = idx * k + s.index(ch)
    return idx

约数

def get_divisors(n: int):
    """返回 1 到 n 所有数的约数列表"""
    divs = [[] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            divs[j].append(i)
    return divs

# 最大公约数 / 最小公倍数
g = math.gcd(a, b)
lcm = a * b // g

# 约数枚举：求出 n 的所有约数（因数）
def divisors(n):
    small, large = [], []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            small.append(i)
            if i != n // i:
                large.append(n // i)
    return small + large[::-1]

素数

# 素数判断。直接调用 is_prime(n)
def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

位运算

1 << i           # 2^i（左移，i=3 → 8）
# 判断
x & (1 << k)     # 检查第 k 位是否为 1
x >> k & 1       # 获取第 k 位的值

x.bit_length()   # 整数的二进制位数（5→3, 1→1, 0→0）
x.bit_count()    # 二进制中 1 的个数

x & -x           # 最低位 1（获取二进制最低位的 1）
x | 1            # 将最低位设为 1
x & ~1           # 将最低位设为 0
x ^ 1            # 翻转最低位

# 遍历检查某一位
for i in range(bit_count):
    if (S >> i) & 1:  # 检查第 i 位是否为 1
        # 第 i 位为 1
        pass

# 设置
x | (1 << k)     # 将第 k 位设为 1
x & ~(1 << k)    # 将第 k 位设为 0
x ^ (1 << k)     # 翻转第 k 位

# 常用
x & (x - 1)      # 清除最低位的 1
x | (x - 1)      # 将最低位 0 变成 1
x ^ (x + 1)      # 获取最低位不同的数

# 子集枚举
for sub in range(mask + 1):
    sub = (sub - 1) & mask  # 枚举子集（不包括 0）

# 最低位 1 的位置
bit = (x & -x).bit_length() - 1

埃拉托斯特尼筛法

minp = []
primes = []

def sieve(n: int):
    """埃拉托斯特尼筛法 - 计算 minp 和 primes"""
    global minp, primes
    minp = [0] * (n + 1)
    primes = []

    for i in range(2, n + 1):
        if minp[i] == 0:
            minp[i] = i
            primes.append(i)

        for p in primes:
            if i * p > n:
                break
            minp[i * p] = p
            if p == minp[i]:
                break

快速幂

# 快速幂：计算 a^b mod mod，高效处理大数幂运算
# 使用：pow_mod(2, 10, 1000) = 24 (2^10=1024 mod 1000)
def pow_mod(a, b, mod):
    res = 1
    a %= mod
    while b:
        if b & 1:
            res = res * a % mod
        a = a * a % mod
        b >>= 1
    return res

组合数

# 组合数（预计算）：计算组合数 C(n, k) = n! / (k!(n-k)!)
# - 使用：fact, inv_fact = comb_init(1000000, MOD)
# 		 print(C(100, 50, MOD, fact, inv_fact))
# - 注意：需要 MOD 为质数（常用 10^9+7）
def comb_init(n, mod):
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i-1] * i % mod
    inv_fact = [1] * (n + 1)
    inv_fact[n] = pow(fact[n], mod-2, mod)
    for i in range(n, 0, -1):
        inv_fact[i-1] = inv_fact[i] * i % mod
    return fact, inv_fact

def C(n, k, mod, fact, inv_fact):
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % mod * inv_fact[n-k] % mod

乘法逆元

# 乘法逆元：求 a 在模 mod 下的逆元（即 a^(-1) mod mod）
# 使用：modinv(3, 7) = 5（因为 3*5=15≡1 mod 7）
def modinv(a, mod):
    return pow(a, mod-2, mod)

扩展欧几里得

# 扩展欧几里得（求逆元）
def exgcd(a, b):
    if b == 0:
        return 1, 0, a
    x, y, g = exgcd(b, a % b)
    return y, x - (a // b) * y, g

高级数据结构

并查集 (DSU)

1. 基础用法（函数式）

n = 5
parent = list(range(n))

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    px, py = find(x), find(y)
    if px != py:
        parent[px] = py

union(0, 1)
union(1, 2)
print(find(0) == find(2))  # True

2. 朋友圈/连通分量

def count_components(n, edges):
    parent = list(range(n))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        px, py = find(x), find(y)
        if px != py:
            parent[px] = py

    for u, v in edges:
        union(u, v)

    return len(set(find(i) for i in range(n)))

3. 类实现（推荐）

class DSU:
    """并查集 (Disjoint Set Union) - 带路径压缩 + 按秩合并"""

    def __init__(self, n: int = 0):
        self.init(n)

    def init(self, n: int):
        self.n = n
        self.cnt = n
        self.f = list(range(n))
        self.siz = [1] * n

    def find(self, x: int) -> int:
        while x != self.f[x]:
            self.f[x] = self.f[self.f[x]]
        return self.f[x]

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def merge(self, x: int, y: int) -> bool:
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.siz[x] < self.siz[y]:
            x, y = y, x
        self.f[y] = x
        self.siz[x] += self.siz[y]
        self.cnt -= 1
        return True

    def size(self, x: int) -> int:
        return self.siz[self.find(x)]

    def count(self) -> int:
        return self.cnt

# 竞赛输入输出模板
size, query_num = [int(i) for i in input().split()]
dsu = DSU(size)
for _ in range(query_num):
    q_type, u, v = [int(i) for i in input().split()]
    if q_type == 0:
        dsu.merge(u, v)
    else:
        print(1 if dsu.same(u, v) else 0)

树状数组 (Fenwick Tree)

class Fenwick:
    """树状数组 (Fenwick Tree / Binary Indexed Tree)"""

    def __init__(self, n: int = 0):
        self.n = n
        self.a = [0] * n

    def init(self, n: int):
        self.n = n
        self.a = [0] * n

    def add(self, x: int, v):
        """在位置 x 加上 v (0-indexed)"""
        i = x + 1
        while i <= self.n:
            self.a[i - 1] = self.a[i - 1] + v
            i += i & -i

    def sum(self, x: int):
        """求前缀和 [0, x] (0-indexed, 包含 x)"""
        ans = 0
        i = x + 1
        while i > 0:
            ans = ans + self.a[i - 1]
            i -= i & -i
        return ans

    def range_sum(self, l: int, r: int):
        """求区间和 [l, r] (0-indexed, 包含两端)"""
        if l == 0:
            return self.sum(r)
        return self.sum(r) - self.sum(l - 1)

    def select(self, k):
        """找到满足 sum(i) <= k 的最大 i"""
        x = 0
        cur = 0
        i = 1 << (self.n.bit_length() - 1)
        while i:
            if x + i <= self.n and cur + self.a[x + i - 1] <= k:
                x += i
                cur = cur + self.a[x - 1]
            i >>= 1
        return x

区间最值查询 (RMQ)

class RMQ:
    """区间最值查询 (Range Minimum Query)"""

    def __init__(self, v=None):
        if v is not None:
            self.init(v)

    def init(self, v):
        """初始化数组 v"""
        import math
        n = len(v)
        self.n = n
        self.B = 64

        self.pre = v[:]
        self.suf = v[:]
        self.ini = v[:]

        if n == 0:
            return

        M = (n - 1) // self.B + 1
        lg = math.log2(M)

        self.a = [[None] * M for _ in range(int(lg) + 1)]

        # 预处理每个块内的最小值
        for i in range(M):
            self.a[0][i] = v[i * self.B]
            for j in range(1, self.B):
                if i * self.B + j < n:
                    self.a[0][i] = min(self.a[0][i], v[i * self.B + j])

        # 前缀最小值
        for i in range(1, n):
            if i % self.B:
                self.pre[i] = min(self.pre[i], self.pre[i - 1])

        # 后缀最小值
        for i in range(n - 2, -1, -1):
            if i % self.B != self.B - 1:
                self.suf[i] = min(self.suf[i], self.suf[i + 1])

        # Sparse Table
        j = 1
        while (1 << j) <= M:
            for i in range(M - (1 << j) + 1):
                self.a[j][i] = min(self.a[j - 1][i], self.a[j - 1][i + (1 << (j - 1))])
            j += 1

    def query(self, l: int, r: int):
        """查询区间 [l, r] 的最小值"""
        import math
        if l > r:
            return float('inf')
        if l // self.B != (r - 1) // self.B:
            ans = min(self.suf[l], self.pre[r - 1])
            l = l // self.B + 1
            r = r // self.B
            if l < r:
                k = int(math.log2(r - l))
                ans = min(ans, self.a[k][l], self.a[k][r - (1 << k)])
            return ans
        else:
            x = self.B * (l // self.B)
            # 简化的同块查询
            return min(self.ini[l:r + 1])

矩阵快速幂

def mat_mul(A, B):
    n = len(A)
    m = len(B[0])
    k = len(B)
    return [[sum(A[i][p] * B[p][j] for p in range(k)) % MOD for j in range(m)] for i in range(n)]

def mat_pow(A, n):
    # 单位矩阵
    result = [[int(i==j) for j in range(len(A))] for i in range(len(A))]
    while n:
        if n & 1:
            result = mat_mul(result, A)
        A = mat_mul(A, A)
        n >>= 1
    return result

# 使用示例：计算斐波那契数列第 n 项
# 矩阵 [[1,1], [1,0]] 的 n 次方
fib_matrix = [[1,1], [1,0]]
result = mat_pow(fib_matrix, 10)
print(result[0][1])  # 第 10 项斐波那契数

二维网格操作

# 4方向移动
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for dx, dy in dirs:
    nx, ny = x + dx, y + dy

# 8方向移动
dirs8 = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]

# 判断边界
if 0 <= nx < n and 0 <= ny < m:
    # 有效

图论

二分图检测

def is_bipartite(n, adj, node):
    """检测图是否为二分图，返回 (is_bipartite, min_changes)"""
    color = [-1] * n  # -1: 未染色, 0/1: 颜色
    ans = 0

    for i in range(n):
        if color[i] != -1:
            continue
        q = deque([i])
        color[i] = 0
        res = [0, 0]

        while q:
            u = q.popleft()
            for v in adj[u]:
                if color[v] == -1:
                    color[v] = color[u] ^ 1
                    q.append(v)
                elif color[v] == color[u]:
                    return False, 0
            res[0] += color[u] ^ node[u]
            res[1] += (color[u] ^ 1) ^ node[u]

        ans += min(res)

    return True, ans

拓扑排序

def topological_sort():
    in_degree = [0] * n
    for u in range(n):
        for v in adj[u]:
            in_degree[v] += 1
    q = deque([i for i in range(n) if in_degree[i] == 0])
    result = []
    while q:
        u = q.popleft()
        result.append(u)
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                q.append(v)
    return result if len(result) == n else []  # 有环返回空

Dijkstra（单源最短路）

def dijkstra(start):
    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 adj[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

Kruskal（最小生成树）

def kruskal(edges, n):
    edges.sort()
    parent = list(range(n))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        px, py = find(x), find(y)
        if px != py:
            parent[px] = py
            return True
        return False

    return sum(w for w, u, v in edges if union(u, v))