头部

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)

语法说明

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

说明

1. readline()可以读取一行输入，输入会包含一个换行符，单独使用时一定要用：readline().strip() 才能获得没有换行符的字符串
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开始，更方便

标准库

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. 用来应付恶心的日期题

collections

from collections import deque, defaultdict

deque

append：右端入队

appendleft：左端入队

pop：右端出队

popleft：左端入队

defaultdict

可以给定一个默认的value类型

可以避免麻烦的键不存在的问题，每次用一个键去访问值时至少能获得一个默认值。

注意这里有个大坑，如果要判断一个键在不在defaultdict里面，如果使用的不是 in，而是用值来判断，此时有可能会多加了一些无效的键值对。

细节

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

栈模拟递归

Python不能应对很深的递归，需要使用栈模拟实现递归。（看数据范围，一般1000以内是可以用递归的）

递归分成两个阶段，递归向下（压栈）和递归向上（弹栈）。向下即为遍历所有子节点。向上即为由子节点算当前节点。

需要用一个vst[args]来表示当前是在向下还是在向上。

vst = __import__('collections').defaultdict(bool) # 默认值为False的字典

不带循环的递归如下：

def dfs(*args):
    before
    dfs(*args)
    after

用栈模拟：

def dfs(*args):
    vst = __import__('collections').defaultdict(bool)
    stk = [args]
    use f[args] to record results
    while stk:
        if not vst[stk[-1]]: # 递归下降
            vst[stk[-1]] = True
            before
            stk.append(args) # 使用stk[-1]来决定args，比如加入孩子节点
        else:                # 递归上升 （子节点的值已经得到了）
            args = stk.pop()
            f[args] = ...    # 根据子节点的值计算当前节点结果
            after

情况一

带循环的递归：

def dfs(*args):
    before1
    loop:
        before2 # before2不受dfs影响
        dfs(*args)
        after2
    after1

用栈模拟：

def dfs(*args):
    vst = __import__('collections').defaultdict(bool)
    stk = [args]
    use f[args] to record results
    while stk:
        if not vst[stk[-1]]:  # 递归下降
            vst[stk[-1]] = True
            before1
            loop:
                before2 # before2不受dfs影响
                stk.append(args)
        else:                 # 递归上升 （子节点的值已经得到了）
            loop:
                args = stk.pop()
                f[args] = ... # 根据子节点的值计算当前节点结果
                after2
            after1

情况二

def dfs(*args):
    while condition:
        before2 # before2受dfs影响
        dfs(*args)
        after2

def dfs(*args):
    stk = [args]
    while stk:
        while condition:
            before2
            stk.append(args)
            break # 相当于递归调用
        # 栈帧结束
        args = stk.pop()
        after2