1. 输入输出处理 (Input/Output)

Python ACM 模式输入模板

在笔试（ACM模式）中，Python 的 input() 有时较慢，推荐使用 sys.stdin.readline。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import sys

# 1. 快速读取一行字符串（去除末尾换行符）
def input():
    return sys.stdin.readline().strip()

# 2. 读取一个整数
n = int(input())

# 3. 读取一行以空格分隔的整数列表
nums = list(map(int, input().split()))

# 4. 读取多行输入（行数已知）
n = int(input())
lines = [input() for _ in range(n)]

# 5. 读取多行输入（行数未知，直到 EOF）
try:
    while True:
        line = input()
        if not line: break
        parts = list(map(int, line.split()))
        # do something
except EOFError:
    pass

常见输入模式案例 (Case Study)

案例：跳过首行/处理固定行数

很多题目第一行是 Case 数 T，后面跟 T 行数据。

推荐写法 (Standard Way): 利用 sys.stdin 是一个迭代器的特性，先手动读取第一行消耗掉，再循环。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

import sys

# 假设第一行是 T，后面是 T 行 "a b"
# 1. 消耗掉第一行
sys.stdin.readline() 

# 2. 循环处理剩下的行
for line in sys.stdin:
    line = line.strip()
    if not line: continue
    parts = line.split()
    a, b = int(parts[0]), int(parts[1])
    print(a + b)

案例：N 个整数可能跨行 (The read() trick)

题目说“输入 N 个整数”，但数据可能写在同一行，也可能分多行。 千万不要只用 sys.stdin.readline().split()，因为它只读一行，如果数据换行了就会报错。

万能写法 (Recommended): 使用 sys.stdin.read().split() 读取所有剩余输入，它会自动忽略所有空白符（空格、换行、制表符）。这是 ACM 模式处理复杂输入的神器。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import sys

# 1. 一次性读入所有剩余内容 -> 字符串列表
# input_data = ['3', '10', '20', '30']
input_data = sys.stdin.read().split() 

# 2. 转为迭代器 (Iterator) 方便逐个提取
iterator = iter(input_data)

try:
    # 提取第一个数 N
    n = int(next(iterator))
    
    # 提取剩下的 N 个数
    nums = []
    for _ in range(n):
        nums.append(int(next(iterator)))
    
    print(sum(nums))
    
except StopIteration:
    pass

案例：单行秒杀 (One-Liner)

如果确定输入即为一行空格分隔的整数（如：1 2 3 4 5），直接使用 map。

1
2

nums = list(map(int, sys.stdin.readline().split()))
print(sum(nums))

案例：二维矩阵处理 (Matrix)

题目输入 n 行 m 列的矩阵。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import sys

# 1. 读入 n, m
line_data = sys.stdin.readline().split()
if not line_data: exit()
n, m = int(line_data[0]), int(line_data[1])

# 2. 读入矩阵 (List of Lists)
# 方式 A: 列表推导式 (如果需要后续 DP，必须存下来)
matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

# 方式 B: 逐行累加 (如果只是求和，不需要存矩阵，空间 O(1))
total_sum = 0
for _ in range(n):
    total_sum += sum(map(int, sys.stdin.readline().split()))
print(total_sum)

输出技巧

• 列表转字符串: print(" ".join(map(str, ans)))
• 格式化输出 (Formatting):
  • 保留小数: f"{x:.3f}" (保留 3 位小数，自动四舍五入) -> 1.235
  • 补前导零: cnt.zfill(5) 或 f"{cnt:05d}" -> 00123
  • 百分比: f"{x:.2%}" -> 12.34%
• 快速输出: 必须输出大量行 (10^5 级) 时，print 可能超时。

  1	sys.stdout.write('\n'.join(map(str, result_list)) + '\n')

2. 循环与控制流 (Loops & Control Flow)

while 循环 (While Loop)

• 特定次数或条件: 比如 BFS 队列循环，二分查找。

1
2
3
4
5
6
7
8

# 1. 基本用法
while i < n:
    i += 1
    if i % 2 == 0: continue # 跳过本次
    if i > 100: break       # 跳出循环

# 2. 常见坑: 死循环
# 务必检查 while 条件内的变量是否在变化 (i+=1, l=mid+1)

for 循环 (For Loop)

• range() 函数: range(start, stop, step) 左闭右开。

  • range(5) -> 0, 1, 2, 3, 4
  • range(1, 4) -> 1, 2, 3
  • range(5, 0, -1) -> 5, 4, 3, 2, 1 (倒序遍历常考)

• enumerate(): 同时获取索引和值 (推荐)。

1
2

for i, val in enumerate(nums):
    print(i, val)

• zip(): 同时遍历两个列表。

1
2
3

names = ['a', 'b']; scores = [90, 80]
for name, score in zip(names, scores):
    print(name, score)

• else 子句: 当循环正常结束（没有被 break 中断）时执行。
  • 常见场景：判断质数，查找失败后的兜底逻辑。

1
2
3
4
5
6

for x in nums:
    if x == target:
        print("Found")
        break
else:
    print("Not Found") # 若循环走完都没 break，则执行

3. 基础数据结构 (Data Structures)

常用容器

1. 列表 (List)

• 创建:
  • arr = [] (空列表)
  • arr = [0] * n (初始化 n 个 0, 比如 DP 数组)
  • matrix = [[0] * m for _ in range(n)] (n 行 m 列二维数组，千万别用 [[0]*m]*n)
• 常用操作:
  • arr.append(x): 末尾添加 O(1)
  • arr.pop(): 弹出末尾 O(1)
  • arr.insert(i, x): 在 i 处插入 O(N) (慎用)
  • len(arr): 长度 O(1)
  • arr.sort(): 原地排序 O(N log N)
  • arr.reverse(): 原地翻转 O(N)
• 切片 (Slicing): arr[start:end:step]
  • arr[::-1]: 翻转列表

2. 集合 (Set)

• 创建:
  • s = set() (空集合，注意不是 {}，{} 是空字典)
  • s = {1, 2, 3}
  • s = set(arr) (列表转集合去重)
• 常用操作:
  • s.add(x): 添加 O(1)
  • s.remove(x): 删除 O(1) (不存在报错)
  • x in s: 判断存在 O(1)
• 集合运算:
  • s1 | s2 (并), s1 & s2 (交), s1 - s2 (差)

3. 字典 (Dict / HashMap)

• 创建:
  • d = {} (空字典)
  • d = {'a': 1, 'b': 2}
• 常用操作:
  • d['k'] = v: 设置/更新
  • val = d.get('k', default): 安全获取 (不存在返回 default)
  • key in d: 判断 key 是否存在 O(1)
  • del d['k']: 删除 key
• 遍历:
  • for k, v in d.items(): ... (遍历键值对)
  • for k in d: ... (只遍历键)

高级数据结构 (collections / heapq)

4. 双端队列 (collections.deque)

• 比 list 强在哪: list.pop(0) 是 O(N) 的（因为要移动数组），而 deque.popleft() 是 O(1) 的。
• BFS 必备:

1
2
3
4
5
6

from collections import deque
q = deque([1, 2, 3])
q.append(4)      # [1, 2, 3, 4]
q.appendleft(0)  # [0, 1, 2, 3, 4]
head = q.popleft() # 0
tail = q.pop()     # 4

5. 计数器 (collections.Counter)

• 作用: 快速统计元素频率，实际上是一个 Dict 的子类。

1
2
3
4
5

from collections import Counter
s = "abacaba"
counts = Counter(s) # Counter({'a': 4, 'b': 2, 'c': 1})
counts['d']         # 返回 0 (不会报错)
top2 = counts.most_common(2) # [('a', 4), ('b', 2)]

6. 默认字典 (collections.defaultdict)

• 作用: 自动处理 key 不存在的情况，省去 if key not in d 的判断。

1
2
3
4
5
6
7
8

from collections import defaultdict
# 初始化值默认为空列表 []
adj = defaultdict(list)
adj[0].append(1) # {0: [1]}

# 初始化值默认为 0
freq = defaultdict(int)
freq['apple'] += 1 # { 'apple': 1 }

7. 堆 (Heaps / Priority Queue)

• 作用: 动态维护最小值/最大值，插入和删除最值都是 O(log N)。
• 注意: Python 只有最小堆。想用最大堆？存入负数 -val。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import heapq
nums = [3, 1, 4, 1, 5]

# 1. 建堆 (O(N))
heapq.heapify(nums) # nums 变为 [1, 1, 4, 3, 5] (堆顺序)

# 2. 推入 (O(log N))
heapq.heappush(nums, 2)

# 3. 弹出最小值 (O(log N))
min_val = heapq.heappop(nums) # 1

# 4. 获取前 K 大元素 (O(N log K))
top3 = heapq.nlargest(3, nums) # [5, 4, 3]

3. 常用内置函数及技巧 (Built-in Functions & Tricks)

1. 字符与编码 (ASCII)

处理字符串偏移（如 ‘a’->‘b’）时必用。

• ord(char): 字符 -> ASCII 数值。
  • ord('a') 是 97, ord('A') 是 65, ord('0') 是 48。
• chr(int): ASCII 数值 -> 字符。
  • chr(97) 是 ‘a’。

1
2
3

# 字母移位（凯撒密码）
c = 'a'
next_c = chr(ord(c) + 1) # 'b'

2. 进制转换

• bin(n): 转二进制字符串 (e.g., '0b101').
• hex(n): 转十六进制字符串 (e.g., '0xa').
• int(string, base): 任意进制转十进制。
  • int('101', 2) -> 5
  • int('A', 16) -> 10

3. 数学与数字处理

• 大整数 (Big Int): Python 的 int 是任意精度的（自动扩容），不会溢出。不用担心 C++ 中的 int vs long long 问题，可以直接计算超大整数。
• divmod(a, b): 返回 (a // b, a % b)，商和余数。
• pow(a, b, mod): 快速幂求模 (a ** b) % mod，比 (a**b)%mod 快得多。
• abs(x): 绝对值。
• round(x, n): 四舍五入保留 n 位小数。
• math 模块：
  • math.ceil(x), math.floor(x): 向上/向下取整 (注意: int 默认是向 0 取整)。
  • math.gcd(a, b): 最大公约数。
  • math.lcm(a, b): 最小公倍数 (Python 3.9+)。
  • math.pi: 圆周率 (3.1415926…)，比用 3.14 精确。
  • math.sqrt(x): 平方根 (返回 float)。
  • math.isqrt(x): 整数平方根 (返回 int, 向下取整, 比 floor(sqrt) 准)。
  • math.inf: 无穷大 (常用于初始化最小值 min_val = float('inf'))。
• 注意: / 得到的是 float，整数整除必须用 //。

4. 字符串操作 (Strings)

字符串是不可变对象 (Immutable)，所有修改操作都会返回新字符串。

• 大小写:

  • s.lower(), s.upper(): 转小写/大写
  • s.capitalize(): 首字母大写
  • s.title(): 每个单词首字母大写

• 查找与判断:

  • s.startswith(prefix), s.endswith(suffix): 前后缀判断
  • s.find(sub): 返回第一个索引，找不到返 -1 (推荐)
  • s.index(sub): 返回第一个索引，找不到报错 (慎用)
  • s.count(sub): 统计子串出现次数
  • s.isdigit(): 是否全数字
  • s.isalpha(): 是否全字母
  • s.isalnum(): 是否全数字或字母

• 拆分与合并:

  • s.strip(): 去除两端空白 (经常用于处理 input)
  • s.split(sep): 按 sep 分割，默认按空白符 (空格、换行、制表)
    • line = " a b "; line.split() -> ['a', 'b'] (自动去空，结果无需再 strip)
  • sep.join(iterable): 将列表组合成字符串 (效率高，千万别用 + 循环拼接)
    • ' '.join(['a', 'b']) -> 'a b' (空格连接)
    • "".join(['a', 'b']) -> 'ab' (无缝拼接，替代 s += x)

• List <-> Str 互转 (修改字符串技巧):

  • list(s): 字符串转字符列表 (为了修改)。
    • s = "abc"; chars = list(s) # ['a', 'b', 'c']
    • chars[0] = 'X'
  • "".join(chars): 列表转回字符串。
    • new_s = "".join(chars) # "Xbc"

• 替换与切片:

  • s.replace(old, new, count): 替换，count 可选替换次数
  • s[::-1]: 字符串翻转 (最快写法)

5. 高阶函数与数据处理 (Functional & Data)

学会这些，一行代码顶十行。

map(function, iterable)

• 作用: 将 function 作用于 iterable 中的每一个元素。
• 返回: 迭代器 (iterator)。需要用 list() 包裹才能看到完整列表（除非只是用来遍历或求和）。
• 常见用法:
  • 类型转换: map(int, ['1', '2']) -> [1, 2]
  • 多变量赋值: a, b = map(int, input().split())

filter(function, iterable)

• 作用: 保留 function(x) 为 True 的元素。
• 用法:
  • nums = [1, 2, 3, 4]
  • evens = list(filter(lambda x: x % 2 == 0, nums)) -> [2, 4]

lambda 表达式 (匿名函数)

• 作用: 定义短小的、一次性的函数。
• 语法: lambda arguments: expression
• 场景: 配合 sort, max, map, filter 使用。
  • 自定义排序: 按元组第二个元素排序 arr.sort(key=lambda x: x[1])
  • 自定义最大值规则: longest = max(strings, key=lambda s: len(s))

reduce(function, iterable) (from functools)

• 作用: 对序列进行累积操作（折叠）。
• 用法:
  • from functools import reduce
  • product = reduce(lambda x, y: x * y, [1, 2, 3, 4]) -> 24

sum(iterable, start)

• 作用: 求和。不要忘了如果元素是列表，可以用 sum 展平一层（虽然慢点）。
• 用法:
  • sum([1, 2, 3]) -> 6
  • sum([[1, 2], [3, 4]], []) -> [1, 2, 3, 4] (慎用，O(N^2))

sorted(iterable, key=…, reverse=…)

• 作用: 返回一个新的已排序列表（不改变原列表）。
• 区别: list.sort() 是原地排序，无返回值。
• Tip: 只要是可以迭代的对象（字符串、元组）都可以丢给 sorted。
  • sorted("bca") -> ['a', 'b', 'c']

6. 其他常用技巧

• 解包 (Unpacking): a, b = b, a (交换); x, *rest = [1, 2, 3] (x=1, rest=[2,3]).
• Zip: 同时遍历两个列表 for x, y in zip(list1, list2):.
• Enumerate: 带索引遍历 for i, val in enumerate(list):.
• Any/All: if any(x > 0 for x in nums): (是否存在); if all(...) (是否所有).

4. 常见算法模板 (Algorithms)

1. 查找与二分 (Binary Search)

Python 标准库 bisect 非常好用。

• bisect.bisect_left(arr, x): 寻找插入点，使得左边都 < x (即第一个 >= x 的位置)。
• bisect.bisect_right(arr, x): 寻找插入点，使得左边都 <= x (即第一个 > x 的位置)。

也可手动实现二分：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def binary_search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            l = mid + 1
        else:
            r = mid - 1
    return -1

2. 双指针 (Two Pointers) / 滑动窗口 (Sliding Window)

常用于处理数组、字符串子串问题。

1
2
3
4
5
6
7

l = 0
for r in range(len(arr)):
    current_val += arr[r]
    while not check(current_val):  # 窗口不满足条件时收缩
        remove_val(arr[l])
        l += 1
    update_result()

3. 搜索 (BFS / DFS)

BFS (最短路径/层序遍历):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

from collections import deque
q = deque([start_node])
visited = {start_node}
step = 0
while q:
    size = len(q)
    for _ in range(size):
        curr = q.popleft()
        if curr == target: return step
        for neighbor in adj[curr]:
            if neighbor not in visited:
                visited.add(neighbor)
                q.append(neighbor)
    step += 1

DFS (全排列/连通性):

1
2
3
4
5
6
7
8

def dfs(node, path):
    if node is None or meets_condition(path):
        return
    visited.add(node)
    for neighbor in adj[node]:
        if neighbor not in visited:
            dfs(neighbor, path + [neighbor])
    visited.remove(node) # 回溯

Tip: 遇到 RecursionError 需要增加递归深度：sys.setrecursionlimit(2000)

4. 并查集 (Union-Find)

处理集合合并、连通分量问题。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

parent = list(range(n))
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x]) # 路径压缩
    return parent[x]

def union(x, y):
    rootX = find(x)
    rootY = find(y)
    if rootX != rootY:
        parent[rootX] = rootY

5. 动态规划 (Dynamic Programming)

• 背包问题 (0/1 背包，完全背包)
• 股票买卖
• 编辑距离，最长公共子序列 (LCS) 关键是定义状态 dp[i][j] 和状态转移方程。

1
2
3
4
5

# 0/1 背包一维优化
dp = [0] * (V + 1)
for i in range(N):
    for j in range(V, weights[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - weights[i]] + values[i])

5. 时空复杂度 (Complexity)

时间复杂度优化 Tips

1. 避免列表查找: if x in list 是 O(N)，改为 if x in set 是 O(1) 平均。
2. 字符串拼接: 永远不要用 s += "a" 在循环中拼接字符串（O(N^2)），使用 "".join(list_of_strings)（O(N)）。
3. 输入输出: 大量数据必须用 sys.stdin.readline 和 sys.stdout.write。
4. 排序: Python 的 Timsort 非常快，但如果只需 top K，用 heapq.nlargest 更优。
5. 递归: 深度过深会爆栈 RecursionError，记得 sys.setrecursionlimit(20000)。
6. 列表生成: [x*2 for x in huge_list] 比 append 快，也会比 map 好调试（虽然 map 有时极微快）。
7. 缓存/记忆化: 使用 @functools.lru_cache(None) 装饰器自动缓存递归结果 (DP)。

空间复杂度优化 Tips

1. 生成器 (Generators): 处理大序列尽量用生成器表达式 (x**2 for x in range(1000000)) 而不是列表 [...]，这就只占一个迭代器内存。
2. 原地操作: 尽量使用 nums.sort() (in-place) 而不是 sorted(nums) (new list)，除非需要保留原数组。
3. 稀疏数组: 遇到很大范围但稀疏的数据，用 dict 或 defaultdict 代替大数组。
4. Slot: 在类中使用 __slots__ 可以极大减少对象内存占用（笔试通常不用，工程中有用）。
5. Itertools: 善用 itertools.islice, chain, count 等，避免生成中间列表。

常见复杂度参考

• N <= 20: O(2^N) DFS/Backtracking
• N <= 100: O(N^4) DP
• N <= 500: O(N^3) Floyd/DP
• N <= 2000: O(N^2) Bubble Sort/DP
• N <= 10^5: O(N log N) Sort/Heap/Merge Sort
• N <= 10^6: O(N) Hash/Two Pointers/Linear Scan
• N > 10^8: O(log N) Binary Search/Math

祝好运！