第 6 章 元组与序列通论¶
配套例题：BISHI24 谐距下标对 来源：菜鸟教程 Python3 元组、Python3 数据结构（元组和序列 / 遍历技巧）
这一章有两条主线。
第一条是元组：一个「不可变的列表」。它在竞赛里的价值不在于「防止误改」，
而在于可哈希——只有可哈希的东西才能当 dict 的键、set 的元素，
而 dict/set 是记忆化、去重、状态判重的基础设施。
第二条是序列通论：list、tuple、str、range、bytes 共享一套操作协议。
把这套协议一次学透，后面所有容器都不用重新学。
6.1 元组的创建¶
t = (1, 2, 3)
t = 1, 2, 3 # 括号可以省！逗号才是元组的标志
t = () # 空元组
t = tuple([1, 2, 3]) # 从可迭代对象构造
t = tuple("abc") # ('a', 'b', 'c')
决定「这是不是元组」的是逗号，不是括号。 括号只是用来消歧义的。
单元素元组必须加逗号¶
t = (50) # ❌ 这是整数 50，括号只是普通的运算符括号
type(t) # <class 'int'>
t = (50,) # ✅ 长度为 1 的元组
type(t) # <class 'tuple'>
t = 50, # ✅ 同上，括号可省
这个坑最常见的触发场景是
以及函数返回值——%格式化：return x,会返回一个单元素元组，而不是x。多打一个逗号足以毁掉一道题。
括号什么时候不能省¶
规则：元组作为更大表达式的一部分时，括号是必须的。
6.2 不可变到底意味着什么¶
t = (1, 2, 3)
t[0] = 9 # ❌ TypeError: 'tuple' object does not support item assignment
t.append(4) # ❌ AttributeError：元组根本没有 append
del t[0] # ❌
元组只有两个方法：t.count(x) 和 t.index(x)，都是 \(O(n)\)。
「修改」元组只能造新的：
需要频繁修改就别用元组。元组的不可变不是为了省事，是为了换来「可哈希」。
不可变是「浅」的¶
这一点必须说清楚：不可变指的是「元组里存的那些引用不能变」， 而不是「引用指向的对象不能变」。
后果直接体现在哈希上：
元组可哈希 ⟺ 它的每个元素都可哈希。 只要里面藏了一个 list/dict/set，
整个元组就不能当字典键。
| 类型 | 可变 | 可哈希 | 能当 dict 键 / set 元素 |
|---|---|---|---|
int float str bool None |
否 | 是 | ✅ |
tuple（元素全可哈希） |
否 | 是 | ✅ |
tuple（含 list 等） |
否 | 否 | ❌ |
frozenset |
否 | 是 | ✅ |
list dict set bytearray |
是 | 否 | ❌ |
6.3 序列通用操作¶
Python 里的序列是一族类型，它们共享下面这张表。
只要一个类型是序列，这些操作就都能用——不管它是 list、tuple、str 还是 range。
| 操作 | 含义 | 对 list |
对 tuple |
对 str |
对 range |
|---|---|---|---|---|---|
s[i] |
索引（支持负数） | ✅ | ✅ | ✅ | ✅ |
s[i:j:k] |
切片 | ✅ | ✅ | ✅ | ✅（返回 range） |
len(s) |
长度 | ✅ | ✅ | ✅ | ✅ |
s + t |
拼接 | ✅ | ✅ | ✅ | ❌ |
s * n |
重复 | ✅ | ✅ | ✅ | ❌ |
x in s |
成员判断 | \(O(n)\) | \(O(n)\) | \(O(n)\) | \(O(1)\) |
min(s) max(s) |
极值 | ✅ | ✅ | ✅ | ✅ |
sum(s) |
求和 | ✅ | ✅ | ❌ | ✅ |
s.index(x) |
首个下标 | ✅ | ✅ | ✅ | ✅ |
s.count(x) |
出现次数 | ✅ | ✅ | ✅ | ✅ |
s < t |
字典序比较 | ✅ | ✅ | ✅ | ❌ |
for x in s |
迭代 | ✅ | ✅ | ✅ | ✅ |
reversed(s) |
反向迭代器 | ✅ | ✅ | ✅ | ✅ |
s[i] = x |
赋值 | ✅ | ❌ | ❌ | ❌ |
x in range(...)是 \(O(1)\) 的，因为range用数学公式判断而不是遍历。 所以if i in range(n)不会 TLE——但它仍然比if 0 <= i < n慢（有函数调用开销）， 竞赛里还是写链式比较。
字典序比较¶
序列之间用 <、> 比较，规则是逐元素比较，第一个不同的元素决定结果；
若一方是另一方的前缀，则短的更小：
(1, 2) < (1, 3) # True 第二个元素 2 < 3
(1, 2) < (1, 2, 0) # True 前缀相同，短的小
[1, 2, 3] < [1, 3] # True
"abc" < "abd" # True
(1, "a") < (1, 2) # ❌ TypeError：str 和 int 没法比
这条规则是元组做多关键字排序的全部原理，见 6.6。
6.4 解包¶
解包（unpacking）是 Python 相对 C++ 最舒服的语法之一。
基本解包¶
a, b = 1, 2 # 右边先打包成元组 (1,2)，再拆给左边
a, b = b, a # 交换，不需要临时变量
x, y, z = [1, 2, 3] # 任何可迭代对象都能解包
a, b = map(int, input().split()) # 竞赛第一高频写法
左右个数必须严格相等，否则 ValueError: not enough values to unpack。
星号解包（PEP 3132）¶
first, *rest = [1, 2, 3, 4] # first=1, rest=[2,3,4]
*init, last = [1, 2, 3, 4] # init=[1,2,3], last=4
a, *mid, b = [1, 2, 3, 4, 5] # a=1, mid=[2,3,4], b=5
带星号的变量永远收集成 list（哪怕右边是元组），且最多只能有一个星号。
竞赛里的典型用法——输入行的第一个数是长度，后面是数组：
嵌套解包¶
(a, b), c = (1, 2), 3
for i, (x, y) in enumerate(points): # 边遍历边拆坐标
...
for u, v, w in edges: # 边表：起点、终点、权
...
星号在函数调用处：展开参数¶
print(*a) # 等价于 print(a[0], a[1], ...)，空格分隔
print(*a, sep="\n") # 每个元素一行
f(*args, **kwargs) # 展开位置参数和关键字参数
zip(*matrix) # 矩阵转置，见 6.5
print(*a)是输出数组最短的写法，但它比sys.stdout.write(" ".join(map(str, a)))慢。数据量大时换掉。
6.5 zip、enumerate 与遍历技巧¶
enumerate：同时拿下标和值¶
比 for i in range(len(a)): x = a[i] 更快也更短——省掉了每次的下标索引。
凡是循环体里同时需要 i 和 a[i] 的，一律用 enumerate。
zip：并行遍历多个序列¶
三个必须知道的性质：
zip以最短的那个为准，多出来的部分直接丢弃，不报错：
这是个安静的 bug 来源。Python 3.10 加了
strict=True参数会在长度不等时报错， 但本教程环境是 3.9，不能用。请自己确认长度。
zip(*matrix)是转置：
g = [[1, 2, 3], [4, 5, 6]]
# * 把每一行拆成一个独立实参，等价于 zip([1,2,3], [4,5,6])；
# zip 逐位取一个元素打成一组，取出来的正好是原矩阵的列
list(zip(*g)) # [(1, 4), (2, 5), (3, 6)]
[list(r) for r in zip(*g)] # zip 给的是元组，要 list 就再转一次
zip(a, a[1:])取相邻元素对：
判断数组是否单调、求相邻差分都靠它：
其它遍历工具¶
reversed(a) # 反向迭代器，不复制（比 a[::-1] 省内存）
sorted(a) # 返回排好序的新列表
sorted(set(a)) # 去重后排序 —— 离散化的标准写法
any(x > 0 for x in a) # 存在
all(x > 0 for x in a) # 全部
sum(x > 0 for x in a) # 计数（bool 是 int 的子类，见第 2 章）
dict 的遍历：
6.6 元组的两大竞赛用途¶
用途一：可哈希的复合键¶
vis = set()
vis.add((x, y)) # 二维坐标判重
if (x, y) in vis: ...
memo = {}
memo[(i, j, k)] = ans # 多维记忆化
cnt = {}
cnt[(a, b)] = cnt.get((a, b), 0) + 1 # 对「数对」计数
list 做不到这些（unhashable），元组是唯一选择。
性能提示：元组键要为每个元素算哈希再合并，比整数键慢 2–3 倍。 坐标范围已知时，编码成一个整数更快：
\(10^6\) 级别的 BFS 里这个优化很值。但代码可读性下降，先写对再优化。
用途二：多关键字排序¶
因为元组按字典序比较（6.3），把关键字按优先级从高到低塞进元组就完成了多关键字排序：
# 按分数降序，分数相同按名字升序
a.sort(key=lambda p: (-p.score, p.name))
# 按第 0 列升序，第 1 列降序
a.sort(key=lambda t: (t[0], -t[1]))
# 直接排元组列表：默认就是按第 0 列、再第 1 列……
pairs.sort()
-x这个取反技巧只对数字有效。字符串要降序只能分两次排（利用 Timsort 的稳定性）：详见 12-自定义排序。a.sort(key=lambda p: p.name) # 先按次关键字升序 a.sort(key=lambda p: p.score, reverse=True) # 再按主关键字降序（稳定，不打乱上一步）
同样的原理让元组能直接进堆：
见 35-优先队列与堆。
元组 vs 列表：怎么选¶
| 维度 | tuple |
list |
|---|---|---|
| 可变 | 否 | 是 |
| 可哈希 | 是（元素也可哈希时） | 否 |
| 创建速度 | 略快（常量元组会被编译期缓存） | 略慢 |
| 内存 | 略小（无预留容量） | 略大 |
| 方法数 | 2 个 | 11 个 |
选择标准很简单：要放进 set/dict 就用元组，要修改就用列表，其余场景差异可以忽略。
6.7 例题：BISHI24 谐距下标对（入门，排序 / 计数）¶
给定长度 \(n \le 10^5\) 的数组 \(a\)。若 \(i < j\) 且 \(a_j - a_i = j - i\)， 则 \((i,j)\) 是一对谐距下标对。求这样的下标对数量。 题面见 BISHI24 原题（牛客）。
关键是把条件移项。\(a_j - a_i = j - i\) 两边同时减 \(a_j\) 加 \(i\)，等价于：
于是问题变成：令 \(b_i = a_i - i\)，统计有多少对下标满足 \(b_i = b_j\)。
按 \(b\) 值分组，若某个值出现了 \(c\) 次，它贡献 \(\dbinom{c}{2} = \dfrac{c(c-1)}{2}\) 对。答案就是求和：
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
cnt = {}
for i, tok in enumerate(data[1:1 + n]): # enumerate 同时拿到下标 i 和值
k = int(tok) - i # b_i = a_i - i
cnt[k] = cnt.get(k, 0) + 1
print(sum(c * (c - 1) // 2 for c in cnt.values()))
main()
验证样例：\(a = [1,2,3,4,5,6]\)，每个 \(b_i = a_i - i\)（0 起始下标）都等于 \(1\)， 所以 \(\text{cnt}[1] = 6\)，答案 \(\binom{6}{2} = 15\) ✅。
复杂度：\(O(n)\)，一遍扫描。
三个本章 / 相邻章的要点：
enumerate是这题的天然工具——条件里同时出现下标和值，正好一次拿全。- 下标从 0 还是从 1 无所谓。整体平移 \(b_i\) 不改变「哪些 \(b_i\) 相等」， 所以不用纠结题面是 1-indexed。这类「差值不变量」的题都有这个性质。
- 答案会超过 \(2^{31}\)：\(n = 10^5\) 且全部相等时答案约 \(5 \times 10^9\)。
C++ 要开
long long，Python 的int无上限，天然不用管—— 这是 Python 打笔试的一个实打实的优势，见 02-数据类型与转换。
为什么不能暴力两重循环？ \(n = 10^5\) 时 \(\binom{n}{2} = 5 \times 10^9\) 对， C++ 都要跑几十秒。看到「统计满足某等式的下标对数量」， 第一反应就是移项，把 \(i\) 的信息和 \(j\) 的信息分到等号两边，然后哈希计数。 这个套路在 36-哈希与字符串哈希、 42-前缀和与差分 里会反复出现。
用 collections.Counter 可以写得更短（见 07-字典）：
from collections import Counter
cnt = Counter(int(x) - i for i, x in enumerate(data[1:1 + n]))
print(sum(c * (c - 1) // 2 for c in cnt.values()))
6.8 本章速查¶
| 场景 | 写法 |
|---|---|
| 单元素元组 | (50,)，逗号不能少 |
| 元组的本质 | 逗号才是标志，括号只是消歧义 |
| 交换变量 | a, b = b, a |
| 读「n 后跟 n 个数」 | n, *a = map(int, input().split()) |
| 取首 / 尾 | first, *rest = a / *init, last = a |
| 展开成实参 | print(*a)、zip(*matrix) |
| 同时取下标和值 | for i, x in enumerate(a): |
| 并行遍历 | for x, y in zip(a, b):（按最短截断） |
| 相邻元素对 | zip(a, a[1:]) |
| 矩阵转置 | list(zip(*g)) |
| 判是否有序 | all(x <= y for x, y in zip(a, a[1:])) |
| 二维坐标判重 | vis.add((x, y))；追求速度用 x * m + y |
| 多维记忆化 | memo[(i, j)] = v |
| 多关键字排序 | key=lambda t: (t[0], -t[1]) |
| 堆中带权元素 | heappush(h, (dist, node)) |
| 元组可哈希条件 | 所有元素都可哈希；含 list 就不行 |
| 去重 + 排序（离散化） | sorted(set(a)) |
| 反向遍历不复制 | reversed(a) |