算法竞赛 Python 内置函数、标准库与数据结构速查手册

面向 Python 组算法竞赛。本文对应原 C++常见STL使用.md 的定位：按数据结构、内置算法和标准库工具整理，强调能直接在比赛中使用的写法、复杂度和易错点。默认环境按 Python 3.10+ / PyPy3 思考。

零、竞赛级 I/O 与输出格式

1. 常用导入模板

import sys
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right, insort
from itertools import accumulate, permutations, combinations, product
from functools import lru_cache, cache
from math import gcd, lcm, isqrt, inf

input = sys.stdin.readline

说明：

• input = sys.stdin.readline 适合大多数按行输入。
• 超大输入用 sys.stdin.buffer.read() 一次读完再解析。
• 递归 DFS 前通常加 sys.setrecursionlimit(1_000_000)，但 Python 深递归仍可能慢，必要时改显式栈。

2. 快速输入

按行读：

n = int(input())
a = list(map(int, input().split()))

一次性读入全部整数：

data = list(map(int, sys.stdin.buffer.read().split()))
it = iter(data)
n = next(it)
m = next(it)

多行矩阵：

n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]

字符矩阵：

n, m = map(int, input().split())
grid = [list(input().strip()) for _ in range(n)]

3. 快速输出

大量输出不要循环 print：

out = []
for ans in answers:
    out.append(str(ans))
sys.stdout.write("\n".join(out))

输出一行数组：

print(*a)
sys.stdout.write(" ".join(map(str, a)) + "\n")

4. 浮点与格式化

保留小数位：

x = 3.1415926535
print(f"{x:.2f}")     # 3.14
print(f"{x:.6f}")     # 3.141593

总有效数字：

print(f"{123.4567:.4g}")  # 123.5

宽度、对齐、填充：

print(f"{42:>8}")     # 右对齐，总宽度 8
print(f"{42:<8}")     # 左对齐
print(f"{42:0>8}")    # 00000042

进制：

x = 255
print(bin(x))         # 0b11111111
print(oct(x))         # 0o377
print(hex(x))         # 0xff
print(format(x, "b")) # 11111111

一、核心数据结构

1. 动态数组 list

Python 的 list 对应 C++ 的 vector，底层是动态数组。

a = [10, 20, 30]
a.append(40)          # 尾部追加，均摊 O(1)
a.extend([50, 60])    # 批量追加
a.insert(1, 15)       # 中间插入，O(n)
x = a.pop()           # 弹出尾部，O(1)
y = a.pop(0)          # 弹出头部，O(n)，队列不要这么写
a[0] = 99

常用操作：

len(a)
sum(a)
min(a), max(a)
a[::-1]               # 反转副本
a.reverse()           # 原地反转
b = a[:]              # 浅拷贝

二维数组正确初始化：

g = [[0] * m for _ in range(n)]

易错点：

bad = [[0] * m] * n   # 错误：每一行引用同一个 list

复杂度要点：

• append/pop() 尾部操作均摊 O(1)。
• insert(i, x)、pop(i)、remove(x) 通常 O(n)。
• x in a 是线性查找 O(n)，高频存在性判断用 set。

2. 元组 tuple

tuple 不可变，常用于坐标、边、字典键、多关键字排序。

p = (3, 5)
x, y = p

edges = [(w, u, v), (2, 0, 1)]
edges.sort()          # 按第 0 项、第 1 项、第 2 项字典序排序

多返回值：

def div_pair(a, b):
    return a // b, a % b

q, r = div_pair(10, 3)

3. 字符串 str

字符串不可变，频繁拼接不要用 s += part 循环，改用 join。

s = "algorithm"
len(s)
s[0], s[-1]
s[1:4]
s.find("go")          # 找不到返回 -1
s.count("t")
s.startswith("algo")
s.endswith("hm")
s.replace("algo", "data")

分割与拼接：

parts = "a,b,c".split(",")
s = "".join(parts)

字符与编码：

ord("a")              # 97
chr(97)               # 'a'
"7".isdigit()         # True
"abc".isalpha()       # True
"abc123".isalnum()    # True

4. 哈希表 dict

对应 C++ unordered_map。平均查找、插入、删除 O(1)。

mp = {}
mp["alice"] = 10
mp["alice"] += 1

if "alice" in mp:
    print(mp["alice"])

val = mp.get("bob", 0)

遍历：

for k in mp:
    ...
for k, v in mp.items():
    ...

计数：

cnt = {}
for x in a:
    cnt[x] = cnt.get(x, 0) + 1

易错点：

• dict 保持插入顺序，但不是有序集合；不能按 key 做 lower_bound。
• key 必须可哈希：int/str/tuple 可以，list/dict/set 不可以。

5. 默认字典 defaultdict

常用于图邻接表、分组和计数。

g = defaultdict(list)
g[u].append(v)

cnt = defaultdict(int)
cnt[x] += 1

sets = defaultdict(set)
sets[u].add(v)

6. 计数器 Counter

适合频率统计、多重集合。

cnt = Counter(a)
cnt[x] += 1
cnt[x] -= 1
if cnt[x] == 0:
    del cnt[x]

cnt.most_common(3)    # 出现次数最多的 3 个

集合式运算：

c1 & c2               # 每个键取较小计数
c1 | c2               # 每个键取较大计数
c1 + c2               # 计数相加
c1 - c2               # 只保留正计数

7. 集合 set / frozenset

对应 C++ unordered_set。平均查找、插入、删除 O(1)。

s = set()
s.add(3)
s.discard(4)          # 不存在也不报错
s.remove(3)           # 不存在会 KeyError

if x in s:
    ...

集合运算：

a | b                 # 并集
a & b                 # 交集
a - b                 # 差集
a ^ b                 # 对称差

不可变集合可作为字典键：

key = frozenset([1, 2, 3])

8. 双端队列 deque

对应 C++ deque，也是 BFS 队列首选。

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

常见用法：

q = deque([1, 2, 3])
q.rotate(1)           # 右移一位
q.rotate(-1)          # 左移一位

复杂度：

• 两端 append/pop 为 O(1)。
• 中间索引和插入不是强项。

固定长度队列：

q = deque(maxlen=k)

9. 栈 stack

Python 直接用 list 当栈。

st = []
st.append(x)
top = st[-1]
x = st.pop()

10. 队列 queue

BFS 用 deque：

q = deque([start])
while q:
    u = q.popleft()

不要用 list.pop(0)，它是 O(n)。

11. 堆 heapq

Python 标准库堆是小根堆，对应 C++ priority_queue 的反向默认行为。

h = []
heappush(h, 5)
heappush(h, 2)
heappush(h, 8)
print(h[0])           # 最小值 2
x = heappop(h)

已有数组建堆：

h = [5, 2, 8]
heapify(h)            # O(n)

大根堆写法：

h = []
heappush(h, -x)
mx = -heappop(h)

带优先级：

heappush(h, (dist, node))
d, u = heappop(h)

Top-K：

import heapq
small = heapq.nsmallest(k, a)
large = heapq.nlargest(k, a)

高频动态删除时，heapq 不支持任意位置删除，常用“懒删除”：额外用 Counter 记录已删除元素，弹堆顶时跳过。

12. 有序查找 bisect

对应 C++ lower_bound / upper_bound，要求数组已经升序。

from bisect import bisect_left, bisect_right

a = [10, 20, 30, 30, 50]
i = bisect_left(a, 30)    # 第一个 >= 30 的位置，2
j = bisect_right(a, 30)   # 第一个 > 30 的位置，4

安全判断是否存在：

i = bisect_left(a, x)
exists = i < len(a) and a[i] == x

统计等于 x 的个数：

cnt = bisect_right(a, x) - bisect_left(a, x)

统计范围：

# [L, R] 中元素个数
cnt = bisect_right(a, R) - bisect_left(a, L)

less_than_x = bisect_left(a, x)
less_equal_x = bisect_right(a, x)
greater_equal_x = len(a) - bisect_left(a, x)
greater_than_x = len(a) - bisect_right(a, x)

插入并保持有序：

insort(a, x)

易错点：

• bisect 查找是 O(log n)，但 insort 插入需要移动元素，总体 O(n)。
• Python 标准库没有真正的 ordered_set。大量动态排名/前驱后继问题通常用树状数组、线段树、堆懒删除或离散化。
• 对对象按某个字段二分，比赛中最稳的是维护单独的 key 数组。

items = [(10, "a"), (20, "b"), (30, "c")]
keys = [x for x, _ in items]
pos = bisect_left(keys, 20)

13. 位集合：用整数当 bitset

Python int 任意精度，适合当动态 bitset。

mask = 0
mask |= 1 << i        # 加入 i
mask &= ~(1 << i)     # 删除 i
ok = (mask >> i) & 1  # 判断 i 是否存在
mask ^= 1 << i        # 翻转 i

统计与长度：

mask.bit_count()      # 二进制 1 的个数
mask.bit_length()     # 最高位长度，0 的 bit_length 为 0

最低位 1：

lowbit = x & -x
idx = lowbit.bit_length() - 1

布尔访问数组：

vis = bytearray(n)    # 比 [False] * n 更省内存
vis[i] = 1

二、排序、查找与序列算法

1. 排序 sort / sorted

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

Python 排序稳定，等价于 C++ stable_sort 的稳定性。

多关键字排序：

players.sort(key=lambda p: (-p[1], p[2], p[0]))
# 分数降序，等级升序，名字升序

按字符串长度：

words.sort(key=len)

不推荐频繁使用比较函数；如果必须使用：

from functools import cmp_to_key

def cmp(a, b):
    return (a > b) - (a < b)

a.sort(key=cmp_to_key(cmp))

2. 第 K 小、Top-K 与堆

Python 没有标准库 nth_element。

import heapq

k_small = heapq.nsmallest(k, a)      # 最小 k 个，已排序
k_large = heapq.nlargest(k, a)       # 最大 k 个，已排序
kth = heapq.nsmallest(k, a)[-1]      # 第 k 小，k 很小时可用

如果 k 接近 n，直接排序通常更快：

kth = sorted(a)[k - 1]

平均 O(n) 的快速选择模板放在算法模板文档中。

3. 查找与统计

x in a              # list 中 O(n)
x in s              # set 中平均 O(1)
a.count(x)          # list 中 O(n)

最大最小与下标：

mn = min(a)
mx = max(a)
idx_min = min(range(len(a)), key=a.__getitem__)
idx_max = max(range(len(a)), key=a.__getitem__)

条件判断：

all(x > 0 for x in a)
any(x == 0 for x in a)

4. 前缀和 itertools.accumulate

from itertools import accumulate

pre = [0] + list(accumulate(a))
range_sum = pre[r + 1] - pre[l]      # 闭区间 [l, r]

5. 反转、复制、去重、映射

反转：

a.reverse()
b = a[::-1]

浅拷贝：

b = a[:]
c = list(a)

保持原顺序去重：

uniq = list(dict.fromkeys(a))

排序后相邻去重：

a.sort()
uniq = []
for x in a:
    if not uniq or uniq[-1] != x:
        uniq.append(x)

映射：

b = [x * x for x in a]
b = list(map(int, input().split()))

划分：

odd = [x for x in a if x & 1]
even = [x for x in a if not (x & 1)]

6. 排列组合与笛卡尔积 itertools

from itertools import permutations, combinations, product

permutations(a)          # 全排列
combinations(a, k)       # 组合
product(range(2), repeat=n)  # 所有 0/1 状态

注意：这些迭代器规模可能指数级，比赛中只在 n 很小时使用。

7. 分组 itertools.groupby

groupby 只合并相邻相同元素，通常先排序。

from itertools import groupby

a.sort()
for value, group in groupby(a):
    cnt = sum(1 for _ in group)

8. 归并

两个有序序列归并：

import heapq

merged = list(heapq.merge(a, b))

多个有序链表/流也可以用 heapq.merge，它是惰性迭代器。

三、数学、进制与位运算

1. 常用数学函数 math

from math import gcd, lcm, isqrt, ceil, floor, factorial, comb, perm

gcd(a, b)
lcm(a, b)
isqrt(x)              # floor(sqrt(x))，整数安全
ceil(x)
floor(x)
factorial(n)
comb(n, k)
perm(n, k)

多参数：

g = gcd(a, b, c)
l = lcm(a, b, c)

2. 快速幂与逆元

pow(a, b)             # a ** b
pow(a, b, mod)        # 快速幂取模，O(log b)
pow(a, -1, mod)       # 模逆元，要求 gcd(a, mod) == 1

3. 除法与取模

q, r = divmod(a, b)

Python 整除是向下取整：

-3 // 2 == -2
-3 % 2 == 1

如果题目要求 C/C++ 风格向 0 截断，需要单独处理。

4. 字符串与数字互转

int("1010", 2)        # 10
int("ff", 16)         # 255
str(123)
float("3.14")

判断整数串：

def is_int(s: str) -> bool:
    if not s:
        return False
    if s[0] in "+-":
        return len(s) > 1 and s[1:].isdigit()
    return s.isdigit()

5. 位运算常用写法

x & y                 # 与
x | y                 # 或
x ^ y                 # 异或
~x                    # 按位取反，Python 中等于 -x - 1
x << k
x >> k

判断奇偶：

x & 1

判断 2 的幂：

x > 0 and (x & (x - 1)) == 0

枚举集合中的每个 1 位：

while mask:
    lb = mask & -mask
    i = lb.bit_length() - 1
    mask -= lb

四、标准库替代表

五、Python 竞赛常见性能提醒

• 热循环里尽量把全局函数绑定到局部变量，例如 heappush = heapq.heappush。
• 大量字符串拼接用 ''.join(parts)。
• 大量队头弹出用 deque.popleft()。
• 大量存在性查询用 set/dict。
• list 中间插入删除是 O(n)，动态有序集合不要硬靠 insort 扛大数据。
• deepcopy 很慢，竞赛中尽量用手写复制或状态回滚。
• @lru_cache(None) / @cache 适合记忆化搜索，但参数必须可哈希。
• Python 没有整数溢出，但大整数运算更慢；能取模就及时取模。
• 浮点比较用 eps，不要直接判断两个浮点数相等。