Python-ACM常用语句

一、输入输出处理

1、快速输入（替代input()，处理大量数据）

import sys
data = sys.stdin.read().split()  # 一次性读入所有数据，按空格/换行分割为列表
ptr = 0  # 指针遍历数据列表
n = int(data[ptr])
ptr += 1

2、多组测试用例（无明确终止符时）

import sys
for line in sys.stdin:
    if not line.strip():  # 跳过空行
        continue
    n = int(line)
    # 处理逻辑

格式化输出

# 整数/浮点数输出
print(n)
print("{:.6f}".format(pi))  # 保留6位小数

# 列表/数组输出（空格分隔）
print(' '.join(map(str, arr)))

二、常用数据结构

1、列表（list）基础操作

arr = [1, 2, 3]
arr.append(4)  # 末尾添加
arr.pop()  # 弹出末尾元素
arr.insert(0, 0)  # 插入指定位置
arr.sort()  # 排序（默认升序）
arr.sort(reverse=True)  # 降序排序
arr.reverse()  # 反转列表

2、字典与集合

# 字典：键值对存储，用于计数、映射
cnt = {}
cnt[num] = cnt.get(num, 0) + 1  # 计数（不存在则初始化为0）

# 集合：去重、交集/并集
s = set(arr)  # 列表去重
s1 & s2  # 交集
s1 | s2  # 并集
s.add(x)  # 添加元素

3、双端队列（deque，高效处理首尾操作）

from collections import deque
q = deque()
q.append(1)  # 队尾入队
q.popleft()  # 队首出队（O(1)效率，比列表.pop(0)快）
q.appendleft(0)  # 队首入队
q.pop()  # 队尾出队

4、堆（Heap，优先队列）

import heapq
heap = []
heapq.heappush(heap, 3)  # 入堆（小根堆，默认最小元素在堆顶）
heapq.heappop(heap)  # 出堆（返回最小元素）
# 大根堆实现：存入负值
heapq.heappush(heap, -num)
max_num = -heapq.heappop(heap)

三、算法模版

1、排序与二分查找

# 二分查找（bisect模块，针对有序列表）
import bisect
arr = [1, 3, 5, 7]
idx = bisect.bisect_left(arr, 5)  # 查找5的插入位置（返回2）
idx = bisect.bisect_right(arr, 5)  # 返回3（右侧插入位置）

# 自定义二分查找（找目标值）
def binary_search(arr, target):
    left, right = 0, len(arr)-1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

2、前缀和（快速求区间和）

# 一维前缀和
prefix = [0] * (n+1)
for i in range(n):
    prefix[i+1] = prefix[i] + arr[i]
sum_lr = prefix[r+1] - prefix[l]  # 求arr[l..r]的和（0<=l<=r <n）

3、差分（快速区间更新）

# 一维差分：对[l..r]加val，最后求前缀和得结果
diff = [0] * (n+2)  # 避免越界
diff[l] += val
diff[r+1] -= val
# 还原数组
res = [0] * n
res[0] = diff[0]
for i in range(1, n):
    res[i] = res[i-1] + diff[i]

4、并查集（Union-Find，处理连通性）

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size
    
    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):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return
        # 按秩合并
        if self.rank[x_root] < self.rank[y_root]:
            self.parent[x_root] = y_root
        else:
            self.parent[y_root] = x_root
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[x_root] += 1

5、深度优先搜索（DFS）与广度优先搜索（BFS）

# DFS（递归版，适用于树/图）
def dfs(u):
    visited[u] = True
    for v in adj[u]:  # adj为邻接表
        if not visited[v]:
            dfs(v)

# BFS（队列实现，适用于最短路径等）
from collections import deque
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)

四、优化技巧

1、避免超时（Python 速度较慢，需注意）

• 用 sys.stdin 替代 input() 读入数据。
• 减少循环嵌套，优先使用内置函数（如 map、filter、列表推导式）。
• 对大数运算，用 math.isqrt（Python 3.8+）求整数平方根，比 int(math.sqrt(x)) 快

2、处理字符串

s = input().strip()  # 去除首尾空格/换行
s.isdigit()  # 判断是否全为数字
s.lower() / s.upper()  # 大小写转换
s.split(',')  # 按逗号分割

3、模块化代码

提前写好常用模板（如并查集、线段树），比赛时直接复用，节省时间

五、常见场景示例

• 多组数据求和

import sys
data = list(map(int, sys.stdin.read().split()))
ptr = 0
t = data[ptr]
ptr += 1
for _ in range(t):
    n = data[ptr]
    ptr += 1
    total = sum(data[ptr:ptr+n])
    ptr += n
    print(total)