Python 竞赛模板

输入输出

import sys
input = sys.stdin.readline          # 加速输入
sys.setrecursionlimit(10**6)        # 递归深度

# 读取单个或多个值
n = int(input())
a, b = map(int, input().split())

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

# 读取多行
for _ in range(n):
    x = int(input())

# 读取到文件结尾
for line in sys.stdin:
    # 处理每一行
    list1 = map(int, line.strip().split())
    print(sum(list1))

# 格式化输出
print(" ".join(map(str, ans)))
print(*ans)                         # 空格分隔

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

常用数据结构

列表操作

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

# 二维列表
grid = [[0] * m for _ in range(n)]

# 列表推导式
squares = [x * x for x in range(n)]

# 列表推导式详解
# 基本格式: [表达式 for 变量 in 可迭代对象 if 条件]
# 等价于:
result = []
for x in iterable:
    if condition:
        result.append(expression)

# 示例: 读取 q 行整数
S_list = [int(input()) for _ in range(q)]

# 等价于:
S_list = []
for _ in range(q):
    S_list.append(int(input()))

# 条件表达式（三元运算符）
a = 'yes' if True else 'no'      # 'yes'
a = 'yes' if False else 'no'     # 'no'
path.extend(['RR' if flag else 'LL', 'D'])

# 反转
a.reverse()
a = a[::-1]

# 排序
a.sort()           # 原地排序
b = sorted(a)      # 返回新列表
# 降序排序
a.sort(reverse=True)      
b = sorted(a, reverse=True) 

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

集合

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          # 对称差集

# ❌ 错误：set 没有 sort() 方法
s = {3, 1, 5}
s.sort()  # AttributeError

# ✅ 正确：用 sorted()
s = {3, 1, 5}
lst = sorted(s)  # → [1, 3, 5]

字典

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

# 计数器
from collections import Counter
cnt = Counter(arr)

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

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

堆（优先队列）

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)

双端队列

from collections import deque

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

常用算法

二分查找

import bisect

pos = bisect.bisect_left(arr, target)  # 左边界
pos = bisect.bisect_right(arr, target) # 右边界

全排列

from itertools import permutations, combinations

# 全排列
for perm in permutations(arr):
    pass

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

BFS/DFS

# DFS（递归）
def dfs(node):
    visited[node] = True
    for nxt in adj[node]:
        if not visited[nxt]:
            dfs(nxt)

# BFS
from collections import deque
q = deque([start])
while q:
    node = q.popleft()
    for nxt in adj[node]:
        if not visited[nxt]:
            visited[nxt] = True
            q.append(nxt)

并查集

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

前缀和

# 一维前缀和
prefix = [0]
for x in arr:
    prefix.append(prefix[-1] + x)

# 区间和 [l, r]
区间和 = prefix[r+1] - prefix[l]

# 二维前缀和
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]

差分数组

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

数据范围参考

类型	范围
int	±2×10^9
float	±10^308
Python int	无限制（但注意性能）

时间复杂度参考

• 10^7 ~ 10^8：1 秒左右（Python 约 10^7）
• 10^6：轻松通过
• 10^5：需要 O(n) 或 O(n log n)

常用库

import sys
import math
import collections
import itertools
import bisect
import heapq
from collections import deque, Counter, defaultdict

常见错误（必须记住！）

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

# ❌ 3. 浮点数比较
a == b        # 可能不准确
abs(a - b) < 1e-9  # 正确

# ❌ 4. 整数除法
5 / 2         # Python3 返回 float: 2.5
5 // 2        # 整数除法: 2

# ❌ 5. 循环中修改列表
for x in a:
    a.remove(x)  # 错误！改用切片或新列表

# ❌ 6. 默认参数用可变对象
def func(a=[]):  # 危险！默认参数只初始化一次
def func(a=None):
    if a is None:
        a = []

边界条件速查

# 数组索引
arr[n-1]      # 最后一个元素
arr[-1]       # 最后一个元素（Python特有）
arr[-2]       # 倒数第二个

# 区间
[0, n)        # 0 到 n-1
[0, n-1]      # 0 到 n-1 闭区间
[l, r]        # l 到 r 闭区间
[l, r)        # l 到 r-1 半开区间

# 空集合/字典
if not s:     # s 为空
if d:         # d 非空

二分搜索模板

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

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

滑动窗口

# 固定窗口大小 k
def sliding_window(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i-k]
        max_sum = max(max_sum, window_sum)
    return max_sum

# 可变窗口（双指针）
def min_window(s):
    left = 0
    for right in range(len(s)):
        # 收缩左指针
        while condition:
            left += 1

复杂度速查

操作	时间复杂度
列表 append/pop 末尾	O(1)
列表 insert/pop 开头	O(n)
列表 in 检查	O(n)
集合/字典 in 检查	O(1)
排序	O(n log n)
遍历所有元素	O(n)
堆 push/pop	O(log n)

调试技巧

# 快速打印调试
print(f"{i}: {value}")  # f-string

# 条件断点
if condition:
    import pdb; pdb.set_trace()

常用代码片段

# 1. 扩展欧几里得（求逆元）
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

# 2. 约瑟夫环
def josephus(n, k):
    if n == 1:
        return 0
    return (josephus(n-1, k) + k) % n

# 3. 回文判断
def is_palindrome(s):
    return s == s[::-1]

# 4. 统计字符出现次数
from collections import Counter
cnt = Counter(s)

# 5. defaultdict 用法
from collections import defaultdict
d = defaultdict(int)   # 默认值为 0
d = defaultdict(list)  # 默认值为 []
d[key].append(value)

# 6. 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)

# 7. 合并 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

完整竞赛模板

import sys
import math
import collections
import itertools
import bisect
import heapq
from collections import deque, Counter, defaultdict

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

# ===== 递归深度 =====
sys.setrecursionlimit(10**6)

# ===== 主函数 =====
def main():
    n = int(input())
    # TODO: 在这里写代码

if __name__ == "__main__":
    main()

位运算技巧

# 基本操作
1 << i           # 2^i（左移，i=3 → 8）
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            # 翻转最低位

# 判断
x & (1 << k)     # 检查第 k 位是否为 1
x >> k & 1       # 获取第 k 位的值

# 设置
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

字符串操作

s = "hello"
lst = list(s)        # 字符串转列表
lst[0] = 'H'
s = ''.join(lst)     # 列表转字符串

s[::-1]              # 反转
s[::2]               # 隔一个取一个

s.isdigit()          # 全是数字
s.isalpha()          # 全是字母

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

# join 用法
print(''.join(path))        # 列表元素直接拼接: ['R','R','D'] → 'RRD'
print(' '.join(path))       # 空格分隔: 'R R D'
print(','.join(map(str, lst)))  # 整数列表转字符串

数学公式

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

# 素数判断
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

# 埃拉托斯特尼筛法
def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n + 1, i):
                is_prime[j] = False
    return [i for i in range(2, n + 1) if is_prime[i]]

# 快速幂
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

# 组合数（预计算）
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

# 乘法逆元
def modinv(a, mod):
    return pow(a, mod-2, mod)

# 约数枚举
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]

# 质因数分解
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

动态规划模板

# ===== 1. 背包问题 =====
# 01 背包
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]

# ===== 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]

图论模板

# ===== 建图 =====
# 邻接表
adj = [[] for _ in range(n)]
adj[u].append(v)      # 有向边
adj[u].append((v, w))  # 带权重

# 无向图
adj[u].append(v)
adj[v].append(u)

# ===== BFS（无权图最短路）=====
def bfs(start):
    dist = [-1] * n
    dist[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

# ===== DFS（连通分量/拓扑排序）=====
def dfs(u):
    visited[u] = True
    stack.append(u)
    for v in adj[u]:
        if not visited[v]:
            dfs(v)

# ===== 拓扑排序 =====
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 用）=====
class DSU:
    def __init__(self, n):
        self.parent = list(range(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):
        self.parent[self.find(x)] = self.find(y)

# ===== Kruskal（最小生成树）=====
def kruskal(edges, n):  # edges = [(w, u, v), ...]
    edges.sort()
    dsu = DSU(n)
    total = 0
    for w, u, v in edges:
        if dsu.find(u) != dsu.find(v):
            dsu.union(u, v)
            total += w
    return total

多组测试用例

# ===== 方式1：T 组数据 =====
T = int(input())
for _ in range(T):
    n = int(input())
    # 处理每组

# ===== 方式2：多行数据 =====
data = sys.stdin.read().strip().split()
idx = 0
while idx < len(data):
    n = int(data[idx]); idx += 1
    # 处理

# ===== 方式3：读到文件结束 =====
lines = sys.stdin.read().split()

常用常量

INF = 10**18          # 无穷大
MOD = 10**9 + 7       # 取模
PI = math.pi          # π
E = math.e            # e

房间分配（优先队列）

# 最少房间数：按到达时间排序，用小顶堆存储离开时间
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)

二分答案

# 在单调数组中查找第一个满足条件的值
def binary_search_left(l, r, check):
    while l < r:
        mid = (l + r) // 2
        if check(mid):
            r = mid
        else:
            l = mid + 1
    return l

# 查找最大的满足条件的值
def binary_search_right(l, r, check):
    while l < r:
        mid = (l + r + 1) // 2  # 上取整
        if check(mid):
            l = mid
        else:
            r = mid - 1
    return l

# 示例：最大值最小化
def min_max_fair(arr, k):
    def can_fair(mid):
        count = sum((x + mid - 1) // mid for x in arr)
        return count <= k

    l, r = 1, max(arr)
    while l < r:
        mid = (l + r) // 2
        if can_fair(mid):
            r = mid
        else:
            l = mid + 1
    return l

矩阵快速幂

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

树状数组（Fenwick Tree）

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, delta):
        while i <= self.n:
            self.bit[i] += delta
            i += i & -i

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def range_sum(self, l, r):
        return self.sum(r) - self.sum(l-1)

二维网格操作

# 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:
    # 有效