输入
输入单个变量
Python 默认读入是字符串.
若想转换成整数, 最简单的办法便是”强转”.
当然也可以读入一些其他类型, 比如说浮点.
或者是十进制小数.
1
2
3
| from decimal import Decimal
n = Decimal(input())
|
注, 请不用使用 eval , 那会超级慢!
输入多个变量
解包, 是一种将可迭代对象中的元素分成单个变量的技巧. 利用这一点我们可以简洁的读入一行多个值.
1
2
3
|
a, b, c = map(int, input().split())
|
相同的, 输入也可以是其他类型, 比如浮点.
1
| a, b, c = map(float, input().split())
|
输入一行列表
既然读入后返回的是一个迭代器 (生成器), 那我们也可以简单的转换成列表.
1
| lst = list(map(int, input().split()))
|
当然了, 输入也可以是其他类型.
1
| lst = list(map(float, input().split()))
|
或者是, 当需要拆位输入的时候.
1
| lst = list(map(int, input()))
|
混合输入
可能有一些题目会要求输入多种不同的操作.
1
| cmd, *args = map(int, input().split())
|
或者是, 一行, 第一个整数 $n$ , 后面跟 $n$ 个整数.
1
| _, *lst = map(int, input().split())
|
快读
快读小板子.
1
2
3
| import sys
input = sys.stdin.readline
|
快读大板子
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
| import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
newlines = 0
def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None
def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()
def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()
def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip()
|
输出
输出一行列表
依靠手动解包, 我们可以很简洁的输出列表
假如需要换行.
列表和迭代器
初始化
这些, 可能并不是魔法, 而是一些坑点.
1
2
3
4
| lst = [0] * 10
lst = [[0, 1]] * 10
lst = [[0, 1] for _ in range(10)]
|
请注意 list 的 * 是, 浅拷贝!
按照错误实例创建出来的数组, 每一个元素指针都是一样的.
当其中一个元素被改变 (注意被替换不是被改变), 其余元素也会被同样的改变.
值得展开的是.
1
2
3
4
5
| def func(lst=[]): ...
def func(lst=None):
if not lst:
lst = []
|
排序
对列表排序有两种办法.
1
2
3
| lst.sort()
lst = sorted(lst)
|
第二种的好处是, 任意迭代器, 包括生成器都可排序.
但是, 第一种简洁, 而且可能会占用更小的空间 (未验证).
如果希望排序后是逆序, 加入 reverse=True 即可.
1
2
| lst.sort(reverse=True)
lst = sorted(lst, reverse=True)
|
或者, 更高级的排序.
1
2
3
4
|
lst = [(1, 1), (1, 0), (2, 4)]
lst.sort(key=lambda x: x[1])
lst = sorted(lst, key=lambda x: x[1])
|
假如你希望用 cmp 函数而不是 key .
1
2
3
| from functools import cmp_to_key
lst.sort(key=cmp_to_key(cmp))
|
前缀和
前缀和并不用手动求, 用 accumulate() 可以很简洁的求得.
1
2
3
| from itertools import accumulate
prefix = list(accumulate(lst))
|
当然也可以应用在乘法上
1
2
3
4
| from itertools import accumulate
from operator import mul
prefix = list(accumulate(lst, func=mul))
|
for循环小技巧
当想要同时获取索引和元素时, 直接低级循环再取元素吗? 那太麻烦了吧!
1
2
3
4
5
6
|
for i, v in enumerate(lst):
...
for i, v in enumerate(lst, 1):
...
|
是不是方便多了?
当一个列表需要枚举所有 l 和 r 的时候.
1
2
3
4
| from itertools import product
for l, r in product(a, repeat=2):
...
|
当遇到两层 for 的时候.
1
2
3
4
| from itertools import product
for ai, bi in product(a, b):
...
|
又假如需要将两个长度相等的列表一起遍历呢?
1
2
| for ai, bi in zip(a, b):
...
|
或者说, 同一个数组想枚举相邻元素. (Python 3.10+)
1
2
3
4
| from itertools import pairwise
for i, j in pairwise(lst):
...
|
或者是, 需要分批处理. (Python 3.12+)
1
2
3
4
| from itertools import batched
for lst_n in batched(lst, n):
...
|
搜索
二分
对于二分查找, Python 有 bisect 库.
1
| idx = bisect.bisect(lst, x)
|
当然也可以使用 key 参数进行一些定制化的查找.
记忆化 dfs
比如计算 fib 时.
1
2
3
4
5
6
7
| from functools import cache
@cache
def fib(n):
if n <= 2:
return 1
return fib(n - 1) + fib(n - 2)
|
栈
Python 在 dfs 深度超过 $10^4$ 时会爆栈, 所以有以下模板.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| def calc(n):
if n <= 1:
return n
else:
a = yield calc(n - 1)
return a + 1
def event_loop(s):
stk, last_rst = [s], None
while stk:
try:
func, last_rst = stk[-1].send(last_rst), None
stk.append(func)
except StopIteration as e:
last_rst = e.value
stk.pop()
return last_rst
print(f"Final result: {event_loop(calc(1000000))}")
|
使用 yield 返回”函数”.
哈希
集合
todo
字典
defaultdict 方便了字典的创建.
比如建图的时候.
1
2
3
4
5
6
7
| from collections import defaultdict
e = defaultdict(list)
for _ in range(m):
u, v = map(int, input().split())
e[u].append(v)
e[v].append(u)
|
又或者计数? 啊不, 计数还有更好用的, Counter .
1
2
3
| from collections import Counter
ct=Counter(lst)
|
todo
