如何用Python参加算法竞赛
前言
本文适合有一定c++基础且初步了解Python，并想开发自己第二竞赛用语言的人群阅读。
本文仅介绍Python3，更低版本Python请自行了解。
Python的优点在于在应对代码编写简单的题目时，在无电子板子的赛场环境可以一定缩短codeing时间。但在面对代码编写要求较高、时间限制较紧的情况，并无法取代c++。因此c++仍然是打算法竞赛的第一选择。
Python的适用场合有如下几种：
- 代码简单的，如一些思维题、构造题等
- 字符串处理，Python提供的字符串处理函数比c++丰富许多。
- 对拍器和数据生成器
Python基本数据类型
python的基本数据类型有六种，常用的有int，str，，bool，float，list
int（整数）
没有长度限制，大数字乘法复杂度\(O(nlogn)\)，非常方便。
float（浮点数）
大概注意一下精度就行，\([2.2250738585072014e-308, 1.7976931348623157e+308]\)
bool（布尔）
有True，False两个值（注意大小写）
不支持c++中用0,1赋值。
list（列表）
最常用的数据类型之一，可当成c++中数组。
a = list(map(int, input().split()))#将读入创建为一个整数list
len(a)#返回a的长度
a[i]#访问a中第i个元素
a[-i]#访问a中倒数第i个元素
a[1:5]#列表切片，返回[a_1,a_2,a_3,a_4]
#列表切片还可以写成
a[:]
a[::2]
a[:5]
a[1:]
a[1:10:2]
#三维分别代码起点，终点（左闭右开），步长。可以参照下文中的range函数介绍一起理解。
a.sort()#升序排序
a.sort(reversed = True)#降序排序
str（字符串）
和c++中字符串类似，但是无法修改其中字符，因此经常用如下方法转换为一个list再进行操作。
s = '1323'
s = list(s)
Python基础语法
本部分，我将直接列出c++基础语法，并给出在Python上的等价替代。
主函数体
c++main函数基础结构：
int main() {
return 0;
}
Python主函数并不是必要的，完全直接在空文件编写代码，如：
int main() {
for (int i = 0;i < 10;i ++) {
printf("%d\n", i);
}
return 0;
}
在Python中可以直接写为：
for i in range(10):
print(i)
当然，如果实在不习惯，想要和c++风格更加类似，可以按如下写法：
if __name__ == "__main__":
for i in range(10):
print(i)
第一行if __name__ == "__main__":的意思：字面上，这是一个if判断，而__name__是一个内置的特殊变量，当我们希望将一个python模块（就是写好的py文件）导入其他python模块时，就只会执行if __name__ == "__main__":的语句，比如：
print(123)
if __name__ == "__main__":
for i in range(10):
print(i)
print(123)就不会被执行。
但对于算法竞赛来说，一般不需要多模块操作，该写法只是为了更好的向c++代码风格靠拢。
“头文件”
Python除内置库外，有一些功能需要手动导入模块，有如下几种方法
import math #导入math库
from math import *#导入math库下所有变量和函数
from math import sin, cos#导入math库下的sin，cos函数
第一种方法和后两种调用时有所区别
第一种：
import math #导入math库
print(math.sin(10))
后两种：
from math import sin, cos#导入math库下的sin，cos函数
print(sin(10))
可见区别就是使用时是否要明确库名，一般在算法竞赛中为了代码简洁，推荐使用后者，但如果要使用from math import *的方法，将存在一定变量名冲突的风险。
因此，更推荐部分导入。
“宏定义”
Python中没有宏定义，但有替代可以缩短一定码量。如下：
def abcdefgasdas(x):
print(x)
abcdefgasdas(10)
func = abcdefgasdas
func(10)
我们定义一个及其鬼畜的函数abcdefgasdas(x)并在之后给其“取别名”为func，调用func就等价调用了abcdefgasdas从而在某些要调用内置函数时，起一个更短的名字，降低码量。
读入
Python中的读入和c++还是有很大不同的，需要一定时间适应。
Python读入时都是调用input()其将返回标准输入中的一行数据（不包括末尾的\n），其返回的类型统一为字符串，因此还要对其进行变量类型转换。
在算法竞赛中，读入一行数字一般分为可数的几个整数，和一个很长的数组两种形式，我举例说明如何读入：
Input
5
1 3
2 4
2 5
3 2
1 2 3 4 5
# 上面是常用的读入一棵树，并给点赋权值的一种输入格式
# 读入方法如下
n = int(input()) # int()函数将input()获取的一行字符串转换为整数
for i in range(n - 1):
x, y = map(int, input().split())# 因为一行有多个整数，首先对input()获取的字符串
#用split()函数切割，该方法将返回一个以' '和'\n'为分隔符切片后的字符串列表
#用map()函数就可以将这个列表中字符串数据全转换为整数，并赋给左值
# do something
w = list(map(int, input().split()))
#w因为类型是列表，因此还要多一个list()，这是一个构造方法，将map对象转为list数据类型
字符串读入方法就很简单了
s = input()
读入优化
Python中的真读入优化需要码量巨大，在正式比赛中并不常用，但仍然可以使用如下方法提高一定的读入效率。
import sys
input = sys.stdin.readline
将其放在Python文件头部即可。可以提高一定效率，但没有c++那般明显。
PS：使用该方法行末的\n将不会被忽略，在读入字符串数据时尤其要注意
输出
使用print()进行输出
print(10) # 输出10并换行
print(1,2,3) # 输出1 2 3并在末尾换行
print(1, end = ' ') # 输出1并再末尾输出一个' '
将输出数据类型转换为字符串，有时可以提高一定效率，但并不明显。
函数
Python中函数定义方法很简单：
def func(x):
# do something
return
Python允许函数定义出现在函数内部
def func1():
print(1)
def func2():
print(2)
func2()
func1()
Output：
1
2
Python允许函数返回多个值
def func(x):
return x + 1, x + 2
x, y = func(10)
print(x, y)
Output:
11 12
Python中函数内部如果想修改外部数字变量，需要使用nonlocal或者global关键字
t = 10
def func(x):
global t
t += 1
return x + 1, x + 2
x, y = func(10)
print(x, y)
如果将global t注释掉程序会报错。
如果想要使用的变量不是被定义在全局区，而是某个函数体内部则要使用nonlocal关键字
def work():
t = 10
def func(x):
nonlocal t
t += 1
return x + 1, x + 2
x, y = func(10)
print(x, y)
work()
基础语句
循环：
for i in range(n):
# do something
i = 0
while i < n:
# do something
需要注意的是，for i in range(n):实际上是对range生成的对象遍历，可以简单理解为对一个\([0,1,2...,n-3,n-2,n-1]\)的列表遍历，因此我们在循环中修改\(i\)并不会改变之后的循环。比如：
for i in range(n):
i += 1
并不会让循环按照\(0 \rightarrow2\rightarrow4···\)的顺序进行。
可见，Python中的for循环不如c++中的灵活，因此while的使用频率大大提高了。
关于range函数：
range(start, end, offset)
三个参数分别代表，起点，终点和步长
range返回的区间是左闭右开的，也就是\([start,end)\)
第1和第3个参数可以缺省。
给几个使用实例
for i in range(n): #遍历[0,n)
for i in range(1, n): #遍历[1,n)
for i in range(0, n, 2):#遍历[0,n)，步长为2
for i in range(n - 1, -1, -1):#倒遍历[0,n - 1)
分支：
和c++差别不大，给个实例：
if x % 3 == 0:
# do something
elif x % 3 == 1:
# do something
else:
# do something
可以发现区别只在于Python将else if合并为了elif。
但因为引入了in这个关键字，有了一些更加方便的用法
# a是一个list x是一个int
if x not in a:
# do something
#可以发现不用再用for逐个判断a是否有x，直接可以用in关键字就可以判断了，
#但复杂度仍然是O(n)并没变小
#不止是list，一些可迭代的高级数据类型也支持这种使用方法
Python库和函数
介绍一些常用的库和函数，着重和c++的STL对比。
sort
自定义排序，Python不如c++灵活。首先它只可以对整个序列排序，而无法对部分序列排序，其次自定义方法不如c++的lamda表达式方便。
#自定义排序方法
import functools
a = [1,2,4,3,5]
def compare_personal(x,y):
if x > y: return -1 #如果x>y，让x在y前面，返回-1
return 1#否则让x在后面，返回1
a.sort(key = functools.cmp_to_key(compare_personal))
print(a)# 输出为[5, 4, 4, 3, 1]
#当然如果只是想得到降序序列，有很简单的方法:
a.sort(reversed = True)
当然，很多时候我们只是想让它根据列表的某一维度排序，这时也可以用python的lambda表达式，代码量少很多。
#a = [[6,5],[3,4],[5,6]]
a.sort(key = lambda A: (A[1],-A[0]))#按第1维升序，第二维降序排列
sort是没有返回值的原地排序，如果我们希望获取到这个排序后列表，且不想改变原来的列表时，可以用sorted函数。自定义
b = sorted(a， key = lambda A: (A[1],-A[0]))
dict、set
dict用的不多，一般使用它的子类，见下文对collections库的介绍。
set是一个集合。支持各种集合操作。
s = set()#创建一个空集合
s.add(1)#加入元素
s.remove(1)#删除1
if 1 in s: #查找1是否在集合内
set我用的不多，详细的函数参考可以[这篇blog](https://blog.csdn.net/m0_70885101/article/details/125948550?ops_request_misc={"request_id"%3A"167323238416782428612782"%2C"scm"%3A"20140713.130102334.."}&request_id=167323238416782428612782&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2alltop_positive~default-2-125948550-null-null.142v70control,201v4add_ask&utm_term=python set&spm=1018.2226.3001.4187)
collections
这个库里常用的有deque，defaultdict，Counter
deque对标c++中的双端队列，可以快速在头尾弹出和加入元素。速度比普通队列快，因此在需要队列的场合，统一使用deque
q = deque()#创建空队列
q = deque([1,2,3])#创建元素为1,2,3的队列
q.append(1)#尾插
q.appendleft(1)#头插
q.extend([1,2])#尾插可迭代对象
q.extendleft([1,2])#头插可迭代对象
q.pop()#将队列尾部的数据弹出，并作为返回值。
q.popleft()#将队列头部的数据弹出，并作为返回值。
defaultdict对标c++中的map，是普通dict的子类，它比普通dict更方便的点在于当访问到一个空键值对时，可以自动调用构造方法创建这个键值对。
mp = defaultdict(int)#创建值为int类型的键值对
#假设此时mp为空,访问mp[0]就会创建一个mp[0] = 0
#这点普通dict无法做到，它只会报错
#因此用defaultdict代替c++中map
Counter也是dict的子类，它主要是方便统计列表中不同元素的出现次数。
from collections import Counter
a = [1,1,1,2,3,3,5]
cnt = Counter(a)
print(cnt)
# 输出为 Counter({1: 3, 3: 2, 2: 1, 5: 1})
PS：dict、set和其子类都是用的hash实现，而不是c++中的红黑树，因此没有自动排序功能，目前没有太好的替代。
heapq（优先队列）
Python中其实有优先队列，但是速度没有heapq快，因此用heapq代替。
heapq提供函数对一个list进行原地的小根堆的维护。
from heapq import heapify, heappop, heappush
q = [4,2,1,4,5]
heapify(q)#一次堆排序
heappush(q, 1)#放入1，并进行一次堆排序
heappop(q)#弹出堆头
heapq并没有提供方便的重载为大根堆的方法，如果想使用大根堆，一般的技巧是加入值取负值，弹出后再恢复。
基础操作差不多这么多，还有一些其他功能可自行了解。
zip、enumerate函数
这两个函数，都是使得枚举进一步简单化的函数。
zip函数可以同时访问不同list的同偏移量的元素
a = [1,2,3,4,5]
b = [5,4,3,2,1]
for x, y in zip(a, b):
print(x, y)
Output：
1 5
2 4
3 3
4 2
5 1
enumerate则是在访问list中元素时，同时给出元素的下标，下标默认从0开始。
a = [1,2,3,4,5]
for i, x in enumerate(a):
print(i, x)
Output:
0 1
1 2
2 3
3 4
4 5
permutations、combinations
permutations，combinations分别是返回一个可迭代对象（一般是list）的所有排列和组合。使用时需要导入itertools模块
用法如下：
from itertools import permutations, combinations
a = [1, 2, 3]
for p in permutations(a):
print(p)
for p in combinations(a, 2):
print(p)
Output:
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
(1, 2)
(1, 3)
(2, 3)
“聚合函数”
Python提供了类似数据库中聚合函数的功能函数。
#下列函数可以传入数字或者可迭代数据类型，常传入list
#以list为例说明功能
max()#返回list的最大值
min()#返回list的最小值
sum()#返回list的和
any()#如果list中有True，返回True
all()#如果list中全部为True，返回True
Python小技巧
列表（其实可以是任何可以迭代对象）解析式
创建列表时，可以用如下方法简化代码
a = [x for x in range(6)]
#生成一个[1,2,3,4,5]的列表
adj = [[] for _ in range(n)]
#生成一个二维，空列表
#等同于 vector<vector<int>> adj(n);
列表解析式中中括号中返回的是一个可迭代对象，这个在很多函数中都是可接受的数据类型。结合上面说的“聚合函数”，就可以这样写
# 求列表全体偶数和
sum(x for x in a if x % 2 == 0)
#判断列表是否严格单调递增
all(a[i - 1] < a[i] for i in range(1, n))
三目表达式
和c++中的三目表达式?:类似，Python中也有何其类似的语法。
x = 10
y = 20
a = x if x == y else y
print(a)
# 输出为20，返回的是在判断x==y为假后，返回了y并赋值给a
字符串处理
find函数，和c++类似可以找到从某个下标开始，第一个指定字符的位置。
#找和左括号匹配的右括号位置。
while i < n:
if s[i] == '(':
j = s.find(')', i + 1) # find ')' from i+1 to n - 1
快速创建一个字典
mp = {}
mp = dict()
mp = {a : b for a, b in lst}#将列表元素构造为键值对放入字典