Python算法题头部与模板

头部

import sys; readline = sys.stdin.readline
read = lambda: [int(x) for x in readline().split()]
alloc = lambda *s: len(s) != 1 and [alloc(*s[1:]) for i in range(int(s[0]) + 2)] or [0] * int(s[0] + 2)
bet = lambda a, b : a <= b and range(a, b + 1) or range(a, b - 1, -1)

语法说明

1. x and y or z 相当于C语言中的 x ? y : z
2. *s 是一个可变参数。s可以当成元组，保存了所有输入的参数。
3. *s[1:] 取得s中下标从1开始的所有元素形成一个元组，*表示unpack，将元组中的每个值作为alloc的参数。

说明

1. readline()可以读取一行输入
2. n, = read() 可以利用unpack来读取一个整数，逗号不能省。
3. n, m, c = read() 可以利用unpack来读取多个整数
4. tex = [read() for i in range(n)] 可以读取多行整数数列并且形成2维数组
5. f = alloc(n1, n2, n3, ..., nk) 相当于 int f[n1 + 2][n2 + 2][n3 + 2]...[nk + 2];元素初始化为0
6. alloc在每个维度在输入上加了2，迭代时下标可以从1开始，而且-1的下标也不会影响到正常的使用
7. alloc内进行强转为int，保证1e5这样的输入也能正确运行
8. 尽量不要再使用input()，使用readline或read几乎可以满足所有输入需求。使用sys.stdin.readline比input效率更高。有些题目必须用sys.stdin.readline才能过，否则会超时。
9. 通常可以arr = [0] + read()，使得下标可以从1开始，更方便
10. bet即between，因为python自带的range是左闭右开区间，每次都要在右区间加1有点麻烦而且不符合直觉

简化版alloc，自行处理维度

alloc = lambda *s: len(s) != 1 and [alloc(*s[1:]) for i in range(s[0])] or [0] * s[0]

标准库

bisect

import bisect
# arr是排好序的列表
n = len(arr)
greater = n - bisect.bisect_right(arr, x) # arr中有多少个数严格大于x
lesser = bisect.bisect_left(arr, x) # arr中有多少个数严格小于x

说明

1. bisect.bisect_left返回大于等于x的第一个下标(相当于cpp的lower_bound)。
2. bisect.bisect_right返回大于x的第一个下标(相当于cpp的upper_bound)
3. n - greater 即为小于等于x的数量
4. n - lesser 即为大于等于x的数量

datetime

import datetime
date1 = datetime.date(2022, 12, 30)
delta = datetime.timedelta(days=1)
date1 += delta # 下一天
year, month, day = date1.timetuple()[:3]
weekday = date1.isoweekday() # 星期，从1到7
passdays = date1.timetuple().tm_yday # 当年的第几天，从1到365

说明

1. 用来应付恶心的日期题

细节

if a < b: a = b 要比 a = max(a, b) 更快