1. 线性容器与字符串#

std::vector $\rightarrow$ list Python 的列表底层实现是动态数组。

• push_back(x) $\rightarrow$ a.append(x)，时间复杂度 $O(1)$。
• pop_back() $\rightarrow$ a.pop()，时间复杂度 $O(1)$。
• clear() $\rightarrow$ a.clear()。
• 初始化大小为 $N$ 且全为 0 的数组：a = [0] * N。

std::string $\rightarrow$ str Python 的字符串是 不可变（Immutable） 的。

• 避坑： 切勿在循环中用 s += "a" 拼接，会导致 $O(N^2)$ 的时间复杂度。
• 正确做法： 使用列表收集字符，最后用 "".join(a) 合并。

std::pair / std::tuple $\rightarrow$ tuple Python 原生支持元组，且自带字典序比较，非常适合打包坐标或状态。

• make_pair(1, 2) $\rightarrow$ (1, 2)。

2. 栈与队列#

std::stack $\rightarrow$ list 直接使用 list 模拟栈。

• push(x) $\rightarrow$ st.append(x)
• top() $\rightarrow$ st[-1]
• pop() $\rightarrow$ st.pop()

std::queue $\rightarrow$ collections.deque 绝对不能用 list 模拟队列！（list.pop(0) 是 $O(N)$）。必须使用双端队列 deque。

1
from collections import deque
2
q = deque()
3
q.append(x)    # push
4
q[0]           # front
5
q.popleft()    # pop，时间复杂度 O(1)

std::priority_queue $\rightarrow$ heapq Python 只有操作列表的堆算法库，默认是小根堆。

1
import heapq
2
pq = []
3
heapq.heappush(pq, x)  # push
4
pq[0]                  # top (最小值)
5
heapq.heappop(pq)      # pop

• 大根堆实现： 存入元素时乘 -1，取出时再乘回 -1。
• 自定义排序： 存入元组 heapq.heappush(pq, (cost, node))，默认按第一个元素排序。

3. 关联容器#

核心差异： C++ map/set 底层是红黑树（增删改查 $O(\log N)$，有序）；Python dict/set 底层是哈希表（增删改查 $O(1)$，无序）。

std::set $\rightarrow$ set

• insert(x) $\rightarrow$ s.add(x)
• count(x) $\rightarrow$ x in s
• erase(x) $\rightarrow$ s.discard(x)（不存在时不报错，比 remove 安全）。

std::map $\rightarrow$ dict 1. 底层差异

• C++ map：红黑树，自带按 Key 排序，$O(\log N)$。
• Python dict：哈希表，无序，$O(1)$（完全等价于 unordered_map）。

2. 致命防坑 (KeyError)

• C++：m[k]++ （键不存在会自动建一个 0，不报错）。
• Python：d[k] += 1 （键不存在直接崩溃 RE）。

3. 竞赛防报错“三板斧”

• 统计次数 (默认 0)： from collections import defaultdict; d = defaultdict(int)
• 图论建边 (默认 [])： from collections import defaultdict; adj = defaultdict(list)
• 极速查词频： from collections import Counter; cnt = Counter(arr)

4. 遍历与排序

• 遍历键和值： for k, v in d.items():
• 按 Key 排序： 字典无法动态排序，只能全拿出来排：sorted(d.items())

4. 常用算法#

std::sort $\rightarrow$ list.sort() 或 sorted()

• 降序：a.sort(reverse=True) （纯 C 底层实现，比用 lambda 更快）。

• 多关键字排序： 利用 Python 元组自动“从左到右”字典序比较的特性，结合 lambda 表达式，可以优雅解决 95% 的多关键字问题。

  1
  # 假设 a 是一个包含多个元素的列表：[[id, score, time], ...]
  2
  a = [[1, 90, 5], [2, 90, 3], [3, 80, 10]]
  3
  
  4
  # 需求：先按 score 降序，score 相同按 time 升序，time 相同按 id 升序
  5
  a.sort(key=lambda x: (-x[1], x[2], x[0]))
  6
  print(a) # 结果: [[2, 90, 3], [1, 90, 5], [3, 80, 10]]
  

• 自定义比较器： 当排序规则无法简单地映射为几个权值（例如经典的“将数组拼接成最大的数字”问题），就需要引入 functools.cmp_to_key 来完全模拟 C++ 里的 cmp 函数。

  1
  from functools import cmp_to_key
  2
  
  3
  def compare(x, y):
  4
      # 返回负数 (-1): 代表 x 应该排在 y 前面
  5
      # 返回正数 ( 1): 代表 y 应该排在 x 前面
  6
      # 返回 0: 代表 x 和 y 相等
  7
  
  8
      str_x, str_y = str(x), str(y)
  9
      if str_x + str_y > str_y + str_x:
  10
          return -1
  11
      else:
  12
          return 1
  13
  
  14
  nums = [3, 30, 34, 5, 9]
  15
  nums.sort(key=cmp_to_key(compare))
  16
  print(nums) # 结果: [9, 5, 34, 3, 30]
  

std::lower_bound / std::upper_bound $\rightarrow$ bisect

1
import bisect
2
a = [1, 2, 2, 4, 5]
3
idx1 = bisect.bisect_left(a, 2)  # lower_bound: 返回 1
4
idx2 = bisect.bisect_right(a, 2) # upper_bound: 返回 3

std::next_permutation $\rightarrow$ itertools.permutations

1
from itertools import permutations
2
for p in permutations([1, 2, 3]):
3
    pass # p 是元组

1. 不可变性#

Python 的字符串是不可变的！ 你绝对不能像 C++ 那样直接写 s[0] = 'a'。任何对字符串的修改（替换、拼接）都不会在原地址操作，而是会在内存中生成一个全新的字符串。

2. 字符串切片#

语法：s[start : end : step] (左闭右开区间 [start, end))

• s[2:5]：截取索引 2 到 4 的子串。
• s[:3]：截取前 3 个字符（等价于 s[0:3]）。
• s[3:]：从索引 3 截取到末尾。
• s[-1]：获取最后一个字符（负数索引表示从右往左数）。
• s[::-1]：字符串翻转

3. 查、分、合#

4. 字符与 ASCII 码转换#

对应 C++ 中的 s[i] - 'a' 逻辑。

• ord(char)：字符转 ASCII 数值。例如 ord('A') 返回 65。
• chr(int)：ASCII 数值转字符。例如 chr(97) 返回 'a'。

5. 字符串的修改与排序#

1
lst = list(s)       # "abc" -> ['a', 'b', 'c']
2
lst[1] = 'x'        # ['a', 'x', 'c']
3
s = "".join(lst)    # "axc"

1
s = "dcba"
2
# sorted(s) 会对可迭代对象排序，并返回一个列表: ['a', 'b', 'c', 'd']
3
s = "".join(sorted(s)) # 重新拼回字符串: "abcd"

6. 高效格式化输出#

Python 3.6+ 引入，运行速度最快，写题调试必备。

1
ans = 123
2
pi = 3.14159
3
print(f"Result: {ans}")        # 基础变量替换
4
print(f"{ans:05d}")            # 补零占位，输出: 00123
5
print(f"{pi:.2f}")             # 保留两位小数，输出: 3.14

Python 模板#

1
import sys
2
import math
3
import heapq
4
from random import randint
5
from functools import cmp_to_key
6
from collections import defaultdict, deque
7
from itertools import permutations, combinations
8

9
input = sys.stdin.readline
10
sys.setrecursionlimit(10**7)
11

12
def I(): return input().strip()
13
def II(): return int(I())
14
def MII(): return map(int, I().split())
15
def LII(): return list(MII())
16

17
def solve():
18
  for line in sys.stdin:
19
    print(line)
20
  pass
21

22
if __name__ == "__main__":
23
    T = 1
24
    # T = II()
25
    for _ in range(T):
26
        solve()

set#

1
def solve():
2
    n = II()
3
    ans = sorted(set(MII()))
4
    print(len(ans))
5
    print(*ans)

dict#

1
from collections import defaultdict
2

3
def solve():
4
    n = II()
5
    cnt = defaultdict(int)
6
    for _ in range(n):
7
        x = II()
8
        cnt[x] += 1
9
    ans = sorted(cnt.keys())
10
    outs = [f"{k} {cnt[k]}" for k in ans]
11
    print("\n".join(outs))

dijkstra#

1
import heapq
2
N = 10**5 + 1
3
inf = 10**18
4
d = [inf for _ in range(N)]
5
vis = [False for _ in range(N)]
6
g = [[] for _ in range(N)]
7

8
def dijkstra(s):
9
    heap = [(0, s)]
10
    d[s] = 0
11
    while (heap):
12
        u = heapq.heappop(heap)[1]
13
        if vis[u]: continue
14
        vis[u] = True
15
        for v, w in g[u]:
16
            if not vis[v] and d[u] + w < d[v]:
17
                d[v] = d[u] + w
18
                heapq.heappush(heap, (d[v], v))
19

20
def solve():
21
    n, m, s = MII()
22
    for _ in range(m):
23
        u, v, w = MII()
24
        g[u].append((v, w))
25
    dijkstra(s)
26
    print(*d[1:n+1])

combinations#

1
from itertools import combinations
2

3
def solve():
4
    n, k = MII()
5
    arr = range(1, n + 1)
6
    ans = []
7
    for p in combinations(arr, k):
8
        line = [f"{x:3}" for x in p]
9
        ans.append("".join(line))
10
    print("\n".join(ans))

permutations#

1
from itertools import permutations
2

3
def solve():
4
    n = II()
5
    arr = range(1, n + 1)
6
    ans = []
7
    for p in permutations(arr):
8
        s = []
9
        for x in p:
10
            s.append(f"{x:5}")
11
        ans.append("".join(s))
12
    print("\n".join(ans))