Python 速成
关于 Python
Python 是一门已在世界上广泛使用的解释型语言。它提供了高效的高级数据结构，还能简单有效地面向对象编程，也可以在算法竞赛。
Python 的优点
Python 是一门 解释型 语言：Python 不需要编译和链接，可以在一定程度上减少操作步骤。
Python 是一门 交互式 语言：Python 解释器实现了交互式操作，可以直接在终端输入并执行指令。
Python 易学易用 ：Python 提供了大量的数据结构，也支持开发大型程序。
Python 兼容性强 ：Python 同时支持 Windows、macOS 和 Unix 操作系统。
Python 实用性强 ：从简单的输入输出到科学计算甚至于大型 WEB 应用，都可以写出适合的 Python 程序。
Python 程序简洁、易读 ：Python 代码通常比实现同种功能的其他语言的代码短。
Python 支持拓展 ：Python 会开发 C 语言程序（即 CPython），支持把 Python 解释器和用 C 语言开发的应用链接，用 Python 扩展和控制该应用。
学习 Python 的注意事项
目前主要使用的 Python 版本是 Python 3.7 及以上的版本，Python 2 和 Python 3.6 及以前的 Python 3 已经 不被支持 ，但仍被一些老旧系统与代码所使用。本文将 介绍较新版本的 Python 。如果遇到 Python 2 代码，可以尝试 2to3
Python 的设计理念和语法结构 与一些其他语言的差异较大 ，隐藏了许多底层细节，所以呈现出实用而优雅的风格。
Python 是高度动态的解释型语言，因此其 程序运行速度相对较慢 ，尤其在使用其内置的 for 循环语句时。在使用 Python 时，应尽量使用 filter、map 等内置函数，或使用 列表生成 语法的手段来提高程序性能。
环境搭建
参见 Python 3 。或者：
此外，也可以通过 venv、conda、Nix 等工具管理 Python 工具链和 Python 软件包，创建隔离的虚拟环境，避免出现依赖问题。
作为一种解释型语言，Python 的执行方式和 C++ 有所不同，这种差异在使用 IDE 编程时往往得不到体现，因此这里需要强调一下运行程序的不同方式。
当在命令行中键入 python3 或刚刚打开 IDLE 时，你实际进入了一种交互式的编程环境，也称「REPL」（「读取 - 求值 - 输出」循环），初学者可以在这里输入语句并立即看到结果，这让验证一些语法变得极为容易，我们也将在后文中大量使用这种形式。
但若要编写完整的程序，你最好还是新建一个文本文件（通常后缀为 .py），然后在命令行中执行 python3 filename.py，就能够运行代码看到结果了。
通过镜像下载安装文件
目前国内关于 源码 的镜像缓存主要是 北京交通大学自由与开源软件镜像站 和 华为开源镜像站 ，可以到那里尝试下载 Python 安装文件。
使用 pip 安装第三方库
Python 的生命力很大程度上来自于丰富的第三方库，编写一些实用程序时「调库」是常规操作，pip 是首选的安装第三方库的程序。自 Python 3.4 版本起，它被默认包含在 Python 二进制安装程序中。
pip 中的第三方库主要存储在 Python 包索引（PyPI） 上，用户也可以指定其它第三方库的托管平台。使用方法可参照 pypi 镜像使用帮助 - 清华大学开源软件镜像站 等使用帮助。你可以在 MirrorZ 上获取更多 PyPI 镜像源。
基本语法
Python 的语法简洁而易懂，也有许多官方和第三方文档与教程。这里仅介绍一些对 OIer 比较实用的语言特性，你可以在 Python 文档 和 Python Wiki 等网页上了解更多关于 Python 的教程。
注释
加入注释并不会对代码的运行产生影响，但加入注释可以使代码更加易懂易用。
# 用 # 字符开头的是单行注释
"""
跨多行字符串会用三引号
（即三个单引号或三个双引号）
包裹，但也通常被用于注释
"""
加入注释代码并不会对代码产生影响。我们鼓励加入注释来使代码更加易懂易用。
基本数据类型
一切皆对象
在 Python 中，你无需事先声明变量名及其类型，直接赋值即可创建各种类型的变量：
1
2
3
4
5
6
7
8
9
10
11
12
13 >>> x = - 3 # 语句结尾不用加分号
>>> x
-3
>>> f = 3.1415926535897932384626 ; f # 实在想加分号也可以，这里节省了一行
3.141592653589793
>>> s1 = "O"
>>> s1 # 怎么显示成单引号了？有区别吗？
'O'
>>> b = 'A' == 65 # 明明在 C/C++ 中是成立的
>>> b # 与众不同的是 True, False 首字母均大写，可能与内置常量的命名约定有关
False
>>> True + 1 == 2 and not False != 0 # Python 可能喜欢单词胜过符号
True
但这不代表 Python 没有类型的概念，实际上解释器会根据赋值或运算自动推断变量类型，你可以使用内置函数 type() 查看这些变量的类型：
>>> type ( x )
<class 'int'>
>>> type ( f )
<class 'float'>
>>> type ( s1 ) # 请注意，不要给字符串起名为 str，不信试试看是否真的可以这么做
<class 'str'>
>>> type ( b )
<class 'bool'>
内置函数 在 C/C++ 中，很多常用函数都分散在不同的头文件中，但 Python 的解释器内置了许多实用且通用的函数，你可以直接使用而无需注意它们的存在，但这也带来了小问题，这些内置函数的名称多为常见单词，你需要注意避免给自己的变量起相同的名字，否则可能会产生奇怪的结果。
正如我们所看到的，Python 内置有整数、浮点数、字符串和布尔类型，可以类比为 C++ 中的 int，float，string 和 bool。但有一些明显的不同之处，比如没有 char 字符类型，也没有 double 类型（但 float 其实对应 C 中的双精度），如果需要更精确的浮点运算，可以使用标准库中的 decimal 模块，如果需要用到复数，Python 还内置了 complex 类型（而这也意味着最好不要给变量起名为 complex）。
可以看到这些类型都以 class 开头，而这正是 Python 不同于 C++ 的关键之处，Python 程序中的所有数据都是由对象或对象间关系来表示的，函数是对象，类型本身也是对象：
>>> type ( int )
<class 'type'>
>>> type ( pow ) # 求幂次的内置函数，后文会介绍
<class 'builtin_function_or_method'>
>>> type ( type ) # type() 也是内置函数，但有些特殊，感兴趣可自行查阅
<class 'type'>
你或许会觉得这些概念一时难以理解且没有用处，所以我们暂时不再深入，在后文的示例中你或许能慢慢体会到，Python 的对象提供了强大的方法，我们在编程时应当优先考虑围绕对象而不是过程进行操作，这会让我们的代码显得更加紧凑明晰。
数字运算
有人说，你可以把你系统里装的 Python 当作一个多用计算器，这是事实。>>> 后面输入一个表达式，就像其他大部分语言（如 C++）一样使用运算符 +、-、*、/、% 来对数字进行运算，也可以使用 () 来进行符合结合律的分组，读者可以自行试验，在这里我们仅展示与 C++ 差异较大的部分：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 >>> 5.0 * 6 # 浮点数的运算结果是浮点数
30.0
>>> 15 / 3 # 与 C/C++ 不同，除法永远返回浮点 float 类型
5.0
>>> 5 / 100000 # 位数太多，结果显示成科学计数法形式
5e-05
>>> 5 // 3 # 使用整数除法（地板除）则会向下取整，输出整数类型
1
>>> - 5 // 3 # 符合向下取整原则，注意这与 C/C++ 不同
-2
>>> 5 % 3 # 取模
2
>>> - 5 % 3 # 负数取模结果一定是非负数，这点也与 C/C++ 不同，不过都满足 (a//b)*b+(a%b)==a
1
>>> x = abs ( - 1e4 ) # 求绝对值的内置函数
>>> x += 1 # 没有自增/自减运算符
>>> x # 科学计数法默认为 float
10001.0
在上面的实践中可以发现，除法运算（/）永远返回浮点类型（在 Python 2 中返回整数）。如果你想要整数或向下取整的结果的话，可以使用整数除法（//）。同样的，你也可以像 C++ 中一样，使用模（%）来计算余数，科学计数法的形式也相同。
特别地，Python 用 ** 即可进行幂运算，还通过内置的 pow(a, b, mod) 提供了 快速幂 的高效实现。
Python 的字符串类型包含 Unicode 字符，这意味着任何字符串都会存储为 Unicode。ord() 将其转换为对应的 Unicode 编码，逆向的转换使用内置函数 chr()。
如果想把数转换为对应的字符串，可使用 Python 内置函数 str()，也可以使用 f-string 实现；反之，可以使用 int() 和 float() 两个函数。
Python 的字符串类型还有 许多方便的功能 。由于本文篇幅有限，这里不一一介绍。
数据类型判断
对于一个变量，可以使用 type(object) 返回变量的类型，例如 type(8) 和 type('a') 的值分别为 <class 'int'> 和 <class 'str'>。
输出和输入
输出
对于一个变量，可以使用 type(object) 返回变量的类型，例如 type(8) 和 type('a') 的值分别为 <class 'int'> 和 <class 'str'>。
Python 中，还可以使用 ** 运算符和内置的 pow(base, exp, mod=None) 函数进行幂运算，使用 abs(x) 求数的绝对值。
>>> 3 ** 4 # 幂运算
81
>>> 2 ** 512
13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096
>>> pow ( 2 , 512 , int ( 1e4 )) # 即 2**512 % 10000 的快速实现, 1e4 是 float 所以要转 int
4096
>>> 2048 ** 2048 # 在IDLE里试试大整数？
>>> 0.1 + 0.1 + 0.1 - 0.3 == 0. # 和 C/C++ 一样需要注意浮点数不能直接判相等
False
字符串
Python 3 提供了强大的基于 Unicode 的字符串类型，使用起来和 C++ 中的 string 类似，一些概念如转义字符也都相通，除了加号拼接和索引访问，还额外支持数乘 * 重复字符串，和 in 操作符。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 >>> s1 = "O" # 单引号和双引号都能包起字符串，有时可节省转义字符
>>> s1 += 'I-Wiki' # 为和 C++ 同步建议使用双引号
>>> 'OI' in s1 # 检测子串很方便
True
>>> len ( s1 ) # 类似 C++ 的 s.length()，但更通用
7
>>> s2 = """ 感谢你的阅读
... 欢迎参与贡献!
""" # 使用三重引号的字符串可以跨越多行
>>> s1 + s2
'OI-Wiki 感谢你的阅读\n欢迎参与贡献!'
>>> print(s1 + s2) # 这里使用了 print() 函数打印字符串
OI-Wiki 感谢你的阅读
欢迎参与贡献!
>>> s2[2] * 2 + s2[3] + s2[-1] # 负数索引从右开始计数，加上len(s)，相当于模n的剩余类环
'谢谢你!'
>>> s1[0] = 'o' # str 是不可变类型，不能原地修改，其实 += 也是创建了新的对象
Traceback (most recent call last):
File "<stdin>" , line 1 , in <module>
TypeError : 'str' object does not support item assignment
Python 支持多种复合数据类型，可将不同值组合在一起。最常用的 list，类型是用方括号标注、逗号分隔的一组值。例如，[1, 2, 3] 和 ['a','b','c'] 都是列表。
除了索引，字符串还支持切片 ，它的设计非常精妙又符合直觉，格式为 s[左闭索引:右开索引:步长]：
1
2
3
4
5
6
7
8
9
10
11
12
13 >>> s = 'OI-Wiki 感谢你的阅读 \n 欢迎参与贡献!'
>>> s [: 8 ] # 省略左闭索引则从头开始
'OI-Wiki '
>>> s [ 8 : 14 ] # 左闭右开设计的妙处，长度恰好为14-8=6，还和上一个字符串无缝衔接
'感谢你的阅读'
>>> s [ - 4 :] # 省略右开索引则直到结尾
'与贡献!'
>>> s [ 8 : 14 : 2 ] # 步长为2
'感你阅'
>>> s [:: - 1 ] # 步长为 -1 时，获得了反转的字符串
'!献贡与参迎欢\n读阅的你谢感 ikiW-IO'
>>> s # 但原来的字符串并未改变
'OI-Wiki 感谢你的阅读\n欢迎参与贡献!'
C/C++ 中 char 类型可以和 对应的 ASCII 码互转，而在 Python 中你可以对一个 Unicode 字符使用内置函数 ord() 将其转换为对应的 Unicode 编码，逆向的转换使用内置函数 chr()。
如果想把数字转换成对应的字符串，可以使用内置函数 str()，反之可以使用 int() 和 float()，你可以类比为 C/C++ 中的强制类型转换，但括号不是加在类型上而是作为函数的一部分括住参数。
Python 的字符串类型提供了许多强大的方法，包括计算某字符的索引与出现次数，转换大小写等等，这里就不一一列举，强烈建议查看 官方文档 熟悉常用方法，遇到字符串操作应当首先考虑使用这些方法而非自力更生。
开数组
从 C++ 转过来的同学可能很迷惑怎么在 Python 中开数组，这里就介绍在 Python 开「数组」的语法，需要强调我们介绍的其实是几种 序列类型 ，和 C 的数组有着本质区别，而更接近 C++ 中的 vector。
使用 list
列表（list）大概是 Python 中最常用也最强大的序列类型，列表中可以存放任意类型的元素，包括嵌套的列表，这符合数据结构中「广义表」的定义。请注意不要将其与 C++ STL 中的双向链表 listlist 以免造成误解。
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
26
27
28
29 >>> [] # 创建空列表，注意列表使用方括号
[]
>>> nums = [ 0 , 1 , 2 , 3 , 5 , 8 , 13 ]; nums # 初始化列表，注意整个列表可以直接打印
[0, 1, 2, 3, 5, 8, 13]
>>> nums [ 0 ] = 1 ; nums # 支持索引访问，还支持修改元素
[1, 1, 2, 3, 5, 8, 13]
>>> nums . append ( nums [ - 2 ] + nums [ - 1 ]); nums # append() 同 vector 的 push_back()，也都没有返回值
[1, 1, 2, 3, 5, 8, 13, 21]
>>> nums . pop () # 弹出并返回末尾元素，可以当栈使用；其实还可指定位置，默认是末尾
21
>>> nums . insert ( 0 , 1 ); nums # 同 vector 的 insert(position, val)
[1, 1, 1, 2, 3, 5, 8, 13]
>>> nums . remove ( 1 ); nums # 按值移除元素（只删第一个出现的），若不存在则抛出错误
[1, 1, 2, 3, 5, 8, 13]
>>> len ( nums ) # 求列表长度，类似 vector 的 size()，但 len() 是内置函数
7
>>> nums . reverse (); nums # 原地逆置
[13, 8, 5, 3, 2, 1, 1]
>>> sorted ( nums ) # 获得排序后的列表
[1, 1, 2, 3, 5, 8, 13]
>>> nums # 但原来的列表并未排序
[13, 8, 5, 3, 2, 1, 1]
>>> nums . sort (); nums # 原地排序，可以指定参数 key 作为排序标准
[1, 1, 2, 3, 5, 8, 13]
>>> nums . count ( 1 ) # 类似 std::count()
2
>>> nums . index ( 1 ) # 返回值首次出现项的索引号，若不存在则抛出错误
0
>>> nums . clear (); nums # 同 vector 的 clear()
以上示例展现了列表与 vector 的相似之处，vector 中常用的操作一般也都能在列表中找到对应方法，不过某些方法如 len(),sorted() 会以内置函数的面目出现，而 STL 算法中的函数如 find(),count(),max_element(),sort(),reverse() 在 Python 中又成了对象的方法，使用时需要注意区分，更多方法请参见官方文档的 列表详解 。下面将展示列表作为 Python 的基本序列类型的一些强大功能：
Python 支持多种复合数据类型，可将不同值组合在一起。最常用的 list，类型是用方括号标注、逗号分隔的一组值。例如，[1, 2, 3] 和 ['a','b','c'] 都是列表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 >>> lst = [ 1 , '1' ] + [ "2" , 3.0 ] # 列表直接相加生成一个新列表
>>> lst # 这里存放不同的类型只是想说明可以这么做，但这不是好的做法
[1, '1', '2', 3.0]
>>> 3 in lst # 实用的成员检测操作，字符串也有该操作且还支持子串检测
True
>>> [ 1 , '1' ] in lst # 仅支持单个成员检测，不会发现「子序列」
False
>>> lst [ 1 : 3 ] = [ 2 , 3 ]; lst # 切片并赋值，原列表被修改
[1, 2, 3, 3.0]
>>> lst [:: - 1 ] # 获得反转后的新列表
[3.0, 3, 2, 1]
>>> lst *= 2 ; lst # 数乘拼接
[1, 2, 3, 3.0, 1, 2, 3, 3.0]
>>> del lst [ 4 :]; lst # 也可写 lst[4:] = []，del 语句不止可以用于删除序列中元素
[1, 2, 3, 3.0]
以上示例展现了列表作为序列的一些常用操作，可以看出许多操作如切片是与字符串相通的，但字符串是「不可变序列」而列表是「可变序列」，故可以通过切片灵活地修改列表。在 C/C++ 中我们往往会通过循环处理字符数组，下面将展示如何使用 「列表推导式」 在字符串和列表之间转换：
1
2
3
4
5
6
7
8
9
10
11
12
13 >>> # 建立一个 [65, 70) 区间上的整数数组，range 也是一种类型，可看作左闭右开区间，第三个参数为步长可省略
>>> nums = list ( range ( 65 , 70 )) # 记得 range 外面还要套一层 list()
[65, 66, 67, 68, 69]
>>> lst = [ chr ( x ) for x in nums ] # 列表推导式的典型结构，[exp for var in iterable if cond]
>>> lst # 上两句可以合并成 [chr(x) for x in range(65,70)]
['A', 'B', 'C', 'D', 'E']
>>> s = '' . join ( lst ); s # 用空字符串 '' 拼接列表中的元素生成新字符串
'ABCDE'
>> list(s) # 字符串生成字符列表
['A', 'B', 'C', 'D', 'E']
>>> # 如果你不知道有 s.lower() 方法就可能写出下面这样新瓶装旧酒的表达式
>>> '' . join ([ chr ( ord ( ch ) - 65 + 97 ) for ch in s if ch >= 'A' and ch <= 'Z' ])
'abcde'
下面演示一些在 OI 中更常见的场景，比如二维「数组」：
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
26
27
28 >>> vis = [[ 0 ] * 3 ] * 3 # 开一个3*3的全0数组
>>> vis
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
>>> vis [ 0 ][ 0 ] = 1 ; vis # 怎么会把其他行也修改了？
[[1, 0, 0], [1, 0, 0], [1, 0, 0]]
>>> # 先来看下一维列表的赋值
>>> a1 = [ 0 , 0 , 0 ]; a2 = a1 ; a3 = a1 [:] # 列表也可以直接被赋给新的变量
>>> a1 [ 0 ] = 1 ; a1 # 修改列表 a1，似乎正常
[1, 0, 0]
>>> a2 # 怎么 a2 也被改变了
[1, 0, 0]
>>> a3 # a3 没有变化
[0, 0, 0]
>>> id ( a1 ) == id ( a2 ) and id ( a1 ) != id ( a3 ) # 内置函数 id() 给出对象的「标识值」，可类比为地址，地址相同说明是一个对象
True
>>> vis2 = vis [:]; # 拷贝一份二维列表看看
>>> vis [ 0 ][ 1 ] = 2 ; vis # vis 肯定还是被批量修改
>>> [[ 1 , 2 , 0 ], [ 1 , 2 , 0 ], [ 1 , 2 , 0 ]]
>>> vis2 # 但 vis2 是切片拷贝的怎么还是被改了
>>> [[ 1 , 2 , 0 ], [ 1 , 2 , 0 ], [ 1 , 2 , 0 ]]
>>> id ( vis ) != id ( vis2 ) # vis 和 vis2 确实不是一个对象啊
True
>>> # 谜底揭晓，vis2 虽然不是 vis 的引用，但其中对应行都指向相同的对象
>>> [[ id ( vis [ i ]) == id ( vis2 [ i ]) for i in range ( 3 )]
[True, True, True]
>>> # 回看二维列表自身
>>> [ id ( x ) for x in vis ] # 具体数字和这里不一样但三个值一定相同，说明是三个相同对象
[139760373248192, 139760373248192, 139760373248192]
其实我们一直隐瞒了一个重要事实，Python 中赋值只传递了引用而非创建新值，你可以创建不同类型的变量并赋给新变量，验证发现二者的标识值是相同的，只不过直到现在我们才介绍了列表这一种可变类型，而给数字、字符串这样的不可变类型赋新值时实际上创建了新的对象，故而前后两个变量互不干扰。但列表是可变类型，所以我们修改一个列表的元素时，另一个列表由于指向同一个对象所以也被修改了。创建二维数组也是类似的情况，示例中用乘法创建二维列表相当于把 [0]*3 这个一维列表重复了 3 遍，所以涉及其中一个列表的操作会同时影响其他两个列表。更不幸的是，在将二维列表赋给其他变量的时候，就算用切片来拷贝，也只是「浅拷贝」，其中的元素仍然指向相同的对象，解决这个问题需要使用标准库中的 deepcopy
>>> vis1 = [[ 0 ] * 3 for _ in range ( 3 )] # 把用不到的循环计数变量设为下划线 _ 是一种惯例
>>> # 但在 REPL 中 _ 默认指代上一个表达式输出的结果，故也可使用双下划线
>>> vis1
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
>>> [ id ( x ) for x in vis1 ] # 具体数字和这里不一样但三个值一定不同，说明是三个不同对象
[139685508981248, 139685508981568, 139685508981184]
>>> vis1 [ 0 ][ 0 ] = 1
[[1, 0, 0], [0, 0, 0], [0, 0, 0]]
>>> a2 [ 0 ][ 0 ] = 10 # 访问和赋值二维数组
我们未讲循环的用法就先介绍了列表推导式，这是由于 Python 是高度动态的解释型语言，因此其程序运行有大量的额外开销。尤其是 for 循环在 Python 中运行的奇慢无比 。因此在使用 Python 时若想获得高性能，尽量使用使用列表推导式，或者 filter,map 等内置函数直接操作整个序列来避免循环，当然这还是要根据具体问题而定。
使用 NumPy
什么是 NumPy
NumPy 是著名的 Python 科学计算库，提供高性能的数值及矩阵运算。在测试算法原型时可以利用 NumPy 避免手写排序、求最值等算法。NumPy 的核心数据结构是 ndarray，即 n 维数组，它在内存中连续存储，是定长的。此外 NumPy 核心是用 C 编写的，运算效率很高。不过需要注意，它不是标准库的一部分，可以使用 pip install numpy 安装，但不保证 OI 考场环境中可用。
下面的代码将介绍如何利用 NumPy 建立多维数组并进行访问。
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
26
27
28
29
30
31 >>> import numpy as np # 请自行搜索 import 的意义和用法
>>> np . empty ( 3 ) # 开容量为3的空数组，注意没有初始化为0
array([0.00000000e+000, 0.00000000e+000, 2.01191014e+180])
>>> np . zeros (( 3 , 3 )) # 开 3*3 的数组，并初始化为0
array([[0., 0., 0.],
[0., 0., 0.],
[0., 0., 0.]])
>>> a1 = np . zeros (( 3 , 3 ), dtype = int ) # 开3×3的整数数组
>>> a1 [ 0 ][ 0 ] = 1 # 访问和赋值
>>> a1 [ 0 , 0 ] = 1 # 更友好的语法
>>> a1 . shape # 数组的形状
(3, 3)
>>> a1 [: 2 , : 2 ] # 取前两行、前两列构成的子阵，无拷贝
array([[1, 0],
[0, 0]])
>>> a1 [ 0 , 2 ] # 获取第 1、3 列，无拷贝
array([[1, 0],
[0, 0],
[0, 0]])
>>> np . max ( a1 ) # 获取数组最大值
1
>>> a1 . flatten () # 将数组展平
array([1, 0, 0, 0, 0, 0, 0, 0, 0])
>>> np . sort ( a1 , axis = 1 ) # 沿行方向对数组进行排序，返回排序结果
array([[0, 0, 1],
[0, 0, 0],
[0, 0, 0]])
>>> a1 . sort ( axis = 1 ) # 沿行方向对数组进行原地排序
使用 array
array
若无特殊说明，后文出现「数组」一般指「列表」。
Python 中的输入输出主要通过内置函数 input() 和 print() 完成，print() 的用法十分符合直觉：
>>> a = [ 1 , 2 , 3 ]; print ( a [ - 1 ]) # 打印时默认末尾换行
3
>>> print ( ans [ 0 ], ans [ 1 ]) # 可以输出任意多个变量，默认以空格间隔
1 2
>>> print ( a [ 0 ], a [ 1 ], end = '' ) # 令 end='', 使末尾不换行
1 2>>>
>>> print ( a [ 0 ], a [ 1 ], sep = ', ' ) # 令 sep=', '，改变间隔样式
1, 2
>>> print ( str ( a [ 0 ]) + ', ' + str ( a [ 1 ])) # 输出同上，但是手动拼接成一整个字符串
算法竞赛中通常只涉及到基本的数值和字符串输出，以上用法基本足够，只有当涉及到浮点数位数时需要用到格式化字符串输出。格式化有三种方法，第一种也是最老旧的方法是使用 printf() 风格的 % 操作符；另一种是利用 format 函数f-string ，最为简洁，但不保证考场中的 Python 版本足够新。详细丰富的说明可以参考 这个网页 ，尽管更推荐使用 format() 方法，但为了获得与 C 接近的体验，下面仅演示与 printf() 类似的老式方法：
>>> pi = 3.1415926 ; print ( ' %.4f ' % pi ) # 格式为 %[flags][width][.precision]type
3.1416
>>> ' %.4f - %8f = %d ' % ( pi , 0.1416 , 3 ) # 右边多个参数用 () 括住，后面会看到其实是「元组」
'3.1416 - 0.141600 = 3'
input() 函数的行为接近 C++ 中的 getline()，即将一整行作为字符串读入，且末尾没有换行符，但在算法竞赛中，常见的输入形式是一行输入多个数值，因此就需要使用字符串的 split() 方法并搭配列表推导式得到存放数值类型的列表，下面以输入 n 个数求平均值为例演示输入 n 个数得到「数组」的方法：
>>> s = input ( '请输入一串数字: ' ); s # 自己调试时可以向 input() 传入字符串作为提示
请输入一串数字: 1 2 3 4 5 6
'1 2 3 4 5 6'
>>> a = s . split (); a
['1', '2', '3', '4', '5', '6']
>>> a = [ int ( x ) for x in a ]; a
[1, 2, 3, 4, 5, 6]
>>> # 以上输入过程可写成一行 a = [int(x) for x in input().split()]
>>> sum ( a ) / len ( a ) # sum() 是内置函数
3.5
有时题目会在每行输入固定几个数，比如边的起点、终点、权重，如果只用上面提到的方法就只能每次读入数组然后根据下标赋值，这时可以使用 Python 的「拆包」特性一次赋值多个变量：
>>> u , v , w = [ int ( x ) for x in input () . split ()]
1 2 4
>>> print ( u , v , w )
1 2 4
题目中经常遇到输入 N 行的情况，可我们还没有讲最基本的循环语句，但 Python 强大的序列操作能在不使用循环的情况下应对多行输入，下面假设将各条边的起点、终点、权值分别读入三个数组：
1
2
3
4
5
6
7
8
9
10
11
12
13 >>> N = 4 ; mat = [[ int ( x ) for x in input () . split ()] for i in range ( N )]
1 3 3
1 4 1
2 3 4
3 4 1
>>> mat # 先按行读入二维数组
[[1, 3, 3], [1, 4, 1], [2, 3, 4], [3, 4, 1]]
>>> u , v , w = map ( list , zip ( * mat ))
# *将 mat 解包得到里层的多个列表
# zip() 将多个列表中对应元素聚合成元组，得到一个迭代器
# map(list, iterable) 将序列中的元素（这里为元组）转成列表
>>> print ( u , v , w ) # 直接将 map() 得到的迭代器拆包，分别赋值给 u, v, w
[1, 1, 2, 3] [3, 4, 3, 4] [3, 1, 4, 1]
上述程序实际上相当于先读入一个 N 行 3 列的矩阵，然后将其转置成 3 行 N 列的矩阵，也就是外层列表中嵌套了 3 个列表，最后将代表这起点、终点、权值的 3 个列表分别赋值给 u, v, w。内置函数 zip()map() 其实是函数式编程的一种操作，它将一个给定函数作用于 zip() 所产生序列的元素，这里就是用 list() 将元组变成列表。你可以自行练习使用 * 和 zip()map()zip() 和 map() 创建的不再返回列表而是返回迭代器，这里暂不解释它们之间的异同，你可以认为迭代器可以产生列表中的各个元素，用 list() 套住迭代器就能生成列表。
尽管我们已经学习了 Python 的许多特性，但到目前为止我们展示的 Python 代码都是单行语句，这掩盖了 Python 和 C 在代码风格上的重大差异：首先，Python 中不用 {} 而是用缩进表示块结构，如果缩进没有对齐会直接报错，如果 tab 和 空格混用也会报错；其次，块结构开始的地方比如 if 和 for 语句的行末要有冒号 :。这有助于代码的可读性，但你也可能怀念 C 那种自由的体验，毕竟如果复制粘贴时因为丢失缩进而不得不手动对齐是很恼人的。
循环结构
列表推导式能在一行内高效地完成批量操作，但有时为了压行我们已经显得过分刻意，许多场景下还是只能使用循环结构，所以我们再以读入多行数据为例展示 Python 中的循环是如何编写的：
# 请注意从现在开始我们不再使用 REPL，请自行复制多行数据
u , v , w = ([] for i in range ( 3 )) # 多变量赋值
for i in range ( 4 ): # 这里假设输入 4 行数据
_u , _v , _w = [ int ( x ) for x in input () . split ()]
u . append ( _u ), v . append ( _v ), w . append ( _w )
# 不可进行类似 cin >> u[i] >> v[i] >> w[i] 的操作，因为必定超出列表当前的长度
# 当然你可以选择初始化长度为 MAXN 的全 0 列表，不过需要记住真实长度并删掉多余元素
print ( u , v , w )
需要注意，Python 中的 for 循环和 C/C++ 有较大的差别，其作用类似 C++ 11 引入的 「基于范围的循环」 ，实质是迭代序列中的元素，比如编写循环遍历数组下标需要迭代 range(len(lst))，而非真正定义起始和终止条件，所以使用起来并没有 C/C++ 灵活。
下面再用 while 循环展示行数不定的情况下如何输入：
u , v , w = [], [], [] # 多变量赋值，其实同上
s = input () # 注意 Python 中赋值语句不能放在条件表达式中
while s : # 不能像 C 那样 while(!scanf())
# 用切片拼接避免了 append()，注意列表推导式中又嵌套了列表
u [ len ( u ):], v [ len ( v ):], w [ len ( w ):] = [[ int ( x )] for x in s . split ()]
s = input ()
# Python 3.8 引入了 walrus operator 海象运算符后，你可以节省两行，但考场环境很可能不支持
while s := input ():
u [ len ( u ):], v [ len ( v ):], w [ len ( w ):] = [[ int ( x )] for x in s . split ()]
print ( u , v , w )
选择结构
和 C/C++ 大同小异，一些形式上的差别都在下面的示例中有所展示，此外还需注意条件表达式中不允许使用赋值运算符（Python 3.8 以上可用 :=没有 switch 语句 。
1
2
3
4
5
6
7
8
9
10
11
12
13 # 条件表达式两侧无括号
if 4 >= 3 > 2 and 3 != 5 == 5 != 7 :
print ( "关系运算符可以连续使用" )
x = None or [] or - 2
print ( "&& || !" , "与 或 非" , "and or not" , sep = ' \n ' )
print ( "善用 and/or 可节省行数" )
if not x :
print ( "负数也是 True，不执行本句" )
elif x & 1 :
print ( "用 elif 而不是 else if \n "
"位运算符与 C 相近，偶数&1 得 0，不执行本句" )
else :
print ( "也有三目运算符" ) if x else print ( "注意结构" )
异常处理
尽管 C++ 中有 try 块 用于异常处理，但竞赛中一般从不使用，而 Python 中常见的是 EAFP 风格，故而代码中可能大量使用 try-exceptdict 这一结构时还会用到，这里展示：
1
2
3
4
5
6
7
8
9
10
11
12
13 s = "OI-wiki"
pat = "NOIP"
x = s . find ( pat ) # find() 找不到返回 -1
try :
y = s . index ( pat ) # index() 找不到则抛出错误
print ( y ) # 这句被跳过
except ValueError :
print ( "没找到" )
try :
print ( y ) # 此时 y 并没有定义，故又会抛出错误
except NameError as e :
print ( "无法输出 y" )
print ( "原因:" , e )
Python 内置函数 open()with
a = []
with open ( 'in.txt' ) as f :
N = int ( f . readline ()) # 读入第一行的 N
a [ len ( a ):] = [[ int ( x ) for x in f . readline () . split ()] for i in range ( N )]
with open ( 'out.txt' , 'w' ) as f :
f . write ( '1 \n ' )
关于文件读写的函数有很多，分别适用于不同的场景，由于 OI 赛事尚不支持使用 Python，这里从略。
内置容器
Python 内置了许多强大的容器类型，只有熟练使用并了解其特点才能真正让 Python 在算法竞赛中有用武之地，除了上面详细介绍的 list（列表），还有 tuple（元组）、dictset（集合）这几种类型。
元组可以简单理解成不可变的列表，不过还需注意「不可变」的内涵，如果元组中的某元素是可变类型比如列表，那么仍可以修改该列表的值，元组中存放的是对列表的引用所以元组本身并没有改变。元组的优点是开销较小且「可哈希 」，后者在创建字典和集合时非常有用。
tup = tuple ([[ 1 , 2 ], 4 ]) # 由列表得到元组
# 等同于 tup = ([1,2], 4)
tup [ 0 ] . append ( 3 )
print ( tup )
a , b = 0 , "I-Wiki" # 多变量赋值其实是元组拆包
print ( id ( a ), id ( b ))
b , a = a , b
print ( id ( a ), id ( b )) # 你应该会看到 a, b 的 id 值现在互换了
# 这更说明 Python 中，变量更像是名字，赋值只是让其指代对象
字典就像 C++ STL 中的 mapmap()JSON ，但 JSON 中键必须是字符串且以双引号括住，字典则更加灵活强大，可哈希的对象都可作为字典的键。需要注意 Python 几次版本更新后字典的特性有了较多变化，包括其中元素的顺序等，请自行探索。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 dic = { 'key' : "value" } # 基本形式
dic = { chr ( i ): i for i in range ( 65 , 91 )} # 大写字母到对应 ASCII 码的映射，注意断句
dic = dict ( zip ([ chr ( i ) for i in range ( 65 , 91 )], range ( 65 , 91 ))) # 效果同上
dic = { dic [ k ]: k for k in dic } # 将键值对逆转，for k in dic 迭代其键
dic = { v : k for k , v in dic . items ()} # 和上行作用相同，dic.items() 以元组存放单个键值对
dic = { k : v for k , v in sorted ( dic . items (), key = lambda x : - x [ 1 ])} # 字典按值逆排序，用到了 lambda 表达式
print ( dic [ 'A' ]) # 返回 dic 中 以 'A' 为键的项，这里值为65
dic [ 'a' ] = 97 # 将 d[key] 设为 value，字典中原无 key 就是直接插入
if 'b' in dic : # LBYL(Look Before You Leap) 风格
print ( dic [ 'b' ]) # 若字典中无该键则会出错，故先检查
else :
dic [ 'b' ] = 98
# 经典场景 统计出现次数
# 新键不存在于原字典，需要额外处理
try : # EAFP (Easier to Ask for Forgiveness than Permission) 风格
cnter [ key ] += 1
except KeyError :
cnter [ key ] = 1
集合就像 C++ STL 中的 set{} 括住，不过单用 {} 会创建空字典而不是空集合，这里就不再给出示例。
编写函数
Python 中定义函数无需指定参数类型和返回值类型，无形中为 OI 选手减少了代码量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 def add ( a , b ):
return a + b # 动态类型的优势，a和b也可以是字符串
def add_no_swap ( a , b ):
print ( 'in func #1:' , id ( a ), id ( b ))
a += b
b , a = a , b
print ( 'in func #2:' , id ( a ), id ( b )) # a, b 已交换
return a , b # 返回多个值，其实就是返回元组，可以拆包接收
lst1 = [ 1 , 2 ]; lst2 = [ 3 , 4 ]
print ( 'outside func #1:' , id ( lst1 ), id ( lst2 ))
add_no_swap ( lst1 , lst2 )
# 函数外 lst1, lst2 并未交换
print ( 'outside func #2:' , id ( lst1 ), id ( lst2 ))
# 不过值确实已经改变
print ( lst1 , lst2 )
默认参数
Python 中函数的参数非常灵活，有关键字参数、可变参数等，但在算法竞赛中这些特性的用处并不是很大，这里只介绍一下默认参数，因为 C++ 中也有默认参数，且在 Python 中使用默认参数很有可能遇到坑。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 def append_to ( element , to = []):
to . append ( element )
return to
lst1 = append_to ( 12 )
lst2 = append_to ( 42 )
print ( lst1 , lst2 )
# 你可能以为输出是 [12] [42]
# 但运行结果其实是 [12] [12, 42]
# 这是因为默认参数的值仅仅在函数定义的时候赋值一次
# 默认参数的值应该是不可变对象，使用 None 占位是一种最佳实践
def append_to ( element , to = None ):
if to is None :
to = []
to . append ( element )
return to
类型标注
Python 是一个动态类型检查的语言，以灵活但隐式的方式处理类型，Python 解释器仅仅在运行时检查类型是否正确，并且允许在运行时改变变量类型，俗话说「动态类型一时爽，代码重构火葬场」，程序中的一些错误可能在运行时才会暴露：
>>> if False :
... 1 + "two" # This line never runs, so no TypeError is raised
... else :
... 1 + 2
...
3
>>> 1 + "two" # Now this is type checked, and a TypeError is raised
TypeError: unsupported operand type(s) for +: 'int' and 'str'
Python 3.5 后引入了类型标注，允许设置函数参数和返回值的类型，但只是作为提示，并没有实际的限制作用，需要静态检查工具才能排除这类错误（例如 PyCharm 和 Mypy ），所以显得有些鸡肋，对于 OIer 来说更是只需了解，可按如下方式对函数的参数和返回值设置类型标注：
def headline (
text , # type: str
width = 80 , # type: int
fill_char = "-" , # type: str
): # type: (...) -> str
return f " { text . title () } " . center ( width , fill_char )
print ( headline ( "type comments work" , width = 40 ))
除了函数参数，变量也是可以类型标注的，你可以通过调用 __annotations__ 来查看函数中所有的类型标注。变量类型标注赋予了 Python 静态语言的性质，即声明与赋值分离：
>>> nothing : str
>>> nothing
NameError: name 'nothing' is not defined
>>> __annotations__
{'nothing': <class 'str'>}
装饰器
装饰器是一个函数，接受一个函数或方法作为其唯一的参数，并返回一个新函数或方法，其中整合了修饰后的函数或方法，并附带了一些额外的功能。简而言之，可以在不修改函数代码的情况下，增加函数的功能。相关知识可以参考 官方文档 。
部分装饰器在竞赛中非常实用，比如 lru_cache
@lru_cache(maxsize=128,typed=False)
传入的参数有 2 个：maxsize 和 typed，如果不传则 maxsize 的默认值为 128，typed 的默认值为 False。
其中 maxsize 参数表示的是 LRU 缓存的容量，即被装饰的方法的最大可缓存结果的数量。如果该参数值为 128，则表示被装饰方法最多可缓存 128 个返回结果；如果 maxsize 传入为 None 则表示可以缓存无限个结果。
如果 typed 设置为 True，不同类型的函数参数将被分别缓存，例如，f(3) 和 f(3.0) 会缓存两次。
以下是使用 lru_cache 优化计算斐波那契数列的例子：
@lru_cache ( maxsize = None )
def fib ( n ):
if n < 2 :
return n
return fib ( n - 1 ) + fib ( n - 2 )
常用内置库
在这里介绍一些写算法可能用得到的内置库，具体用法可以自行搜索或者阅读 官方文档 。
从例题对比 C++ 与 Python
例题 洛谷 P4779【模板】单源最短路径（标准版） 给定一个
声明常量
声明前向星结构体和其它变量
C++ Python
1
2
3
4
5
6
7
8
9
10
11
12 struct qxx {
int nex , t , v ;
};
qxx e [ M ];
int h [ N ], cnt ;
void add_path ( int f , int t , int v ) { e [ ++ cnt ] = ( qxx ){ h [ f ], t , v }, h [ f ] = cnt ; }
typedef pair < int , int > pii ;
priority_queue < pii , vector < pii > , greater < pii >> q ;
int dist [ N ];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 class qxx : # 前向星类（结构体）
def __init__ ( self ):
self . nex = 0
self . t = 0
self . v = 0
e = [ qxx () for i in range ( M )] # 链表
h = [ 0 for i in range ( N )]
cnt = 0
dist = [ INF for i in range ( N )]
q = pq . PriorityQueue () # 定义优先队列，默认第一元小根堆
def add_path ( f , t , v ): # 在前向星中加边
# 如果要修改全局变量，要使用 global 来声明
global cnt , e , h
# 调试时的输出语句，多个变量使用元组
# print("add_path(%d,%d,%d)" % (f,t,v))
cnt += 1
e [ cnt ] . nex = h [ f ]
e [ cnt ] . t = t
e [ cnt ] . v = v
h [ f ] = cnt
Dijkstra 算法
主函数
C++ Python
1
2
3
4
5
6
7
8
9
10
11
12
13 int n , m , s ;
int main () {
scanf ( "%d%d%d" , & n , & m , & s );
for ( int i = 1 ; i <= m ; i ++ ) {
int u , v , w ;
scanf ( "%d%d%d" , & u , & v , & w );
add_path ( u , v , w );
}
dijkstra ( s );
for ( int i = 1 ; i <= n ; i ++ ) printf ( "%d " , dist [ i ]);
return 0 ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13 if __name__ == '__main__' :
# 一行读入多个整数。注意它会把整行都读进来
n , m , s = map ( int , input () . split ())
for i in range ( m ):
u , v , w = map ( int , input () . split ())
add_path ( u , v , w )
dijkstra ( s )
for i in range ( 1 , n + 1 ):
print ( dist [ i ], end = ' ' )
print ()
完整代码
C++ Python
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46 #include <bits/stdc++.h>
using namespace std ;
const int N = 1e5 + 5 , M = 2e5 + 5 ;
struct qxx {
int nex , t , v ;
};
qxx e [ M ];
int h [ N ], cnt ;
void add_path ( int f , int t , int v ) { e [ ++ cnt ] = ( qxx ){ h [ f ], t , v }, h [ f ] = cnt ; }
typedef pair < int , int > pii ;
priority_queue < pii , vector < pii > , greater < pii >> q ;
int dist [ N ];
void dijkstra ( int s ) {
memset ( dist , 0x3f , sizeof ( dist ));
dist [ s ] = 0 , q . push ( make_pair ( 0 , s ));
while ( q . size ()) {
pii u = q . top ();
q . pop ();
if ( dist [ u . second ] < u . first ) continue ;
for ( int i = h [ u . second ]; i ; i = e [ i ]. nex ) {
const int & v = e [ i ]. t , & w = e [ i ]. v ;
if ( dist [ v ] <= dist [ u . second ] + w ) continue ;
dist [ v ] = dist [ u . second ] + w ;
q . push ( make_pair ( dist [ v ], v ));
}
}
}
int n , m , s ;
int main () {
scanf ( "%d%d%d" , & n , & m , & s );
for ( int i = 1 ; i <= m ; i ++ ) {
int u , v , w ;
scanf ( "%d%d%d" , & u , & v , & w );
add_path ( u , v , w );
}
dijkstra ( s );
for ( int i = 1 ; i <= n ; i ++ ) printf ( "%d " , dist [ i ]);
return 0 ;
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71 try : # 引入优先队列模块
import Queue as pq # python version < 3.0
except ImportError :
import queue as pq # python3.*
N = int ( 1e5 + 5 )
M = int ( 2e5 + 5 )
INF = 0x3f3f3f3f
class qxx : # 前向星类（结构体）
def __init__ ( self ):
self . nex = 0
self . t = 0
self . v = 0
e = [ qxx () for i in range ( M )] # 链表
h = [ 0 for i in range ( N )]
cnt = 0
dist = [ INF for i in range ( N )]
q = pq . PriorityQueue () # 定义优先队列，默认第一元小根堆
def add_path ( f , t , v ): # 在前向星中加边
# 如果要修改全局变量，要使用 global 来声名
global cnt , e , h
# 调试时的输出语句，多个变量使用元组
# print("add_path(%d,%d,%d)" % (f,t,v))
cnt += 1
e [ cnt ] . nex = h [ f ]
e [ cnt ] . t = t
e [ cnt ] . v = v
h [ f ] = cnt
def nextedgeid ( u ): # 生成器，可以用在 for 循环里
i = h [ u ]
while i :
yield i
i = e [ i ] . nex
def dijkstra ( s ):
dist [ s ] = 0
q . put (( 0 , s ))
while not q . empty ():
u = q . get ()
if dist [ u [ 1 ]] < u [ 0 ]:
continue
for i in nextedgeid ( u [ 1 ]):
v = e [ i ] . t
w = e [ i ] . v
if dist [ v ] <= dist [ u [ 1 ]] + w :
continue
dist [ v ] = dist [ u [ 1 ]] + w
q . put (( dist [ v ], v ))
# 如果你直接运行这个python代码（不是模块调用什么的）就执行命令
if __name__ == '__main__' :
# 一行读入多个整数。注意它会把整行都读进来
n , m , s = map ( int , input () . split ())
for i in range ( m ):
u , v , w = map ( int , input () . split ())
add_path ( u , v , w )
dijkstra ( s )
for i in range ( 1 , n + 1 ):
# 两种输出语法都是可以用的
print ( " {} " . format ( dist [ i ]), end = ' ' )
# print("%d" % dist[i],end=' ')
print () # 结尾换行
参考文档
Python Documentation，https://www.python.org/doc/
Python 官方中文教程，https://docs.python.org/zh-cn/3/tutorial/
Learn Python3 In Y Minutes，https://learnxinyminutes.com/docs/python3/
Real Python Tutorials，https://realpython.com/
廖雪峰的 Python 教程，https://www.liaoxuefeng.com/wiki/1016959663602400/
GeeksforGeeks: Python Tutorials,https://www.geeksforgeeks.org/python-programming-language/
参考资料和注释
2024/2/23 16:16:31 ，更新历史 在 GitHub 上编辑此页！ cmpute , Henry-ZHR , ranwen , abc1763613206 , billchenchina , chinggg , ChungZH , CoelacanthusHex , countercurrent-time , Dong Tsing-hsuen , Early0v0 , Enter-tainer , F1shAndCat , Great-designer , hensier , HeRaNO , Hszzzx , imba-tjd , Ir1d , ksyx , lingxier , LovelyBuggies , Marcythm , mgt , Mooos-MoSheng , NachtgeistW , ouuan , shawlleyw , shuzhouliu , sshwy , SukkaW , Suyun514 , Tiphereth-A , tLLWtG , wineee , wxh06 , Xeonacid , yusancky , zyouxam , zzjjbb CC BY-SA 4.0 和 SATA
