红魔咖啡馆


头发越掉越多，头发越掉越少

【杂项】Python在算法竞赛中的常用技巧

  • ~5.39K 字
  1. 1. 火车头
  2. 2. IO
    1. 2.1. 快读快写
    2. 2.2. 未知数据组数
    3. 2.3. 一行读入多个变量
    4. 2.4. 读入列表
      1. 2.4.1. 一维
      2. 2.4.2. 二维
      3. 2.4.3. 列表初始化
    5. 2.5. 建图
      1. 2.5.1. 带权无向图
      2. 2.5.2. 带权有向图
  3. 3. 常用数据结构API
    1. 3.1. 列表
    2. 3.2. 队列
    3. 3.3. 优先队列
    4. 3.4. 字典
      1. 3.4.1. 结合zip使用
    5. 3.5. Counter
      1. 3.5.1. 实例化
      2. 3.5.2. 方法
    6. 3.6. map映射函数
    7. 3.7. 排序
      1. 3.7.1. 内置排序
      2. 3.7.2. 重载小于号
      3. 3.7.3. 重载排序规则
    8. 3.8. 内置库二分
  4. 4. 语法糖
    1. 4.1. enumerate
    2. 4.2. zip并行遍历
    3. 4.3. 解包
    4. 4.4. any/all
    5. 4.5. max/min 的key属性

火车头

1
2
3
4
5
6
7
8
9
10
11
12
13
from sys import stdin, stdout, setrecursionlimit
from math import inf, ceil, sqrt
from collections import Counter, deque
setrecursionlimit(1000000)
input=lambda:stdin.readline()
write=lambda x:stdout.write(str(x))
writeln=lambda x:stdout.write(str(x)+'\n')
def solve():
 
 
if __name__ == '__main__':
# for _ in range(int(input())):
  solve()

IO

快读快写

1
2
3
4
from sys import stdin, stdout, setrecursionlimit
sys.setrecursionlimit(1000000)
input=lambda:stdin.readline()
write=lambda x:stdout.write(str(x)+'\n')

未知数据组数

1
2
3
4
import sys

for line in sys.stdin:
    line = line.strip()

一行读入多个变量

1
n, m = map(int, input().split())

读入列表

一维

1
arr = [int(_) for _ in input().split()]

二维

读入类似于下面的二维数组：

1
2
3
4
n m
1 2 3
4 5 6
7 8 9
1
2
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]

读入字符矩阵：

1
2
n, m = map(int, input().split())
grid = [list(input().strip()) for _ in range(n)]

列表初始化

1
2
n, m = map(int, input().split())
a = [[val]*m for _ in range(n)]

建图

不带权直接删除w即可

带权无向图

1
2
3
4
5
6
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    u, v, w = map(int, input().split())
    g[u].append((v, w))
    g[v].append((u, w))

带权有向图

1
2
3
4
5
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    u, v, w = map(int, input().split())
    g[u].append((v, w))

常用数据结构API

列表

int->list:

1
2
num = 123
nums = list(map(int, str(num)))

list->int:

1
2
nums = [1, 2, 3]
num = int(''.join(map(str, nums)))

去重：

1
2
arr = list(set(arr))
arr = sorted(set(arr))

注意，列表自带字典序比较

队列

1
2
3
4
5
6
7
8
9
10
from collections import deque
list1 = [0, 1, 2, 3]
q = deque(list1)
q.append(4)  # 向右侧加 
q.appendleft(-1)  # 向左侧加
q.extend(可迭代元素)  # 向右侧添加可迭代元素
q.extendleft(可迭代元素)    
q = q.pop()  # 移除最右端并返回元素值
l = q.popleft()  # 移除最左端
q.count(1)  # 统计元素个数 1

优先队列

python库queue中自带的PriorityQueue是基于堆实现的优先队列

  • put()方法向队列中插入元素，可以是一个元组，第一个元素是优先级，第二个元素是实际数据
  • get()方法从队列中拿出优先级最高（数字最小）的元素
  • empty()方法用于判空
  • qsize()方法用于返回队列大小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import queue

# 创建一个优先级队列
q = queue.PriorityQueue()

# 向队列中添加元素，元素为元组 (优先级, 数据)
q.put((3, 'Low priority'))
q.put((1, 'High priority'))
q.put((2, 'Medium priority'))

# 从队列中获取元素
print(q.get())  # 输出: (1, 'High priority')
print(q.get())  # 输出: (2, 'Medium priority')
print(q.get())  # 输出: (3, 'Low priority')

字典

1
2
3
4
5
6
7
d.pop(key)  # 返回 key 对应的 value，并在字典中删除这个键值对
d.get(key, default_value=None)  # 返回 key 对应的 value，不存在则返回 default_value
d.keys()  # 键构成的可迭代对象
d.values()  # 值构成的可迭代对象
d.items()  # 键值对构成的可迭代对象
d = defaultdict(list)  # 指定了具有默认值空列表的字典
d[key] = value  # 创建一个键值对

结合zip使用

zip函数可以将多个可迭代对象中的对应元素打包成一个个元组

1
2
3
keys = ['name', 'age']
values = ['Alice', 24]
d = dict(zip(keys, values))

Counter

python的counter类是字典的子类，键为待计数的元素，值为对应元素出现的次数

出现的次数允许0或负值，counter将不存在的元素次数设为0

实例化

必须进行实例化，可以为构造函数传参

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from collections import Counter

# 实例化元素为空的 Counter 对象
a = Counter()

# 从可迭代对象中实例化 Counter 对象
b = Counter('chenkc')
b2 = Counter(['c', 'h', 'e', 'n', 'k', 'c']) # list

# 从 mapping 中实例化 Counter 对象
c = Counter({'a':1, 'b':2, 'c':3})

# 从关键词参数中实例化 Counter 对象
d = Counter(a = 1, b = 2, c = 3)

之后可以用类似于字典添加元素的方式添加元素

1
2
3
a['a'] = 1
a['b'] = 2
a['c'] = 3

方法

  • elements()：返回一个迭代器，输出对应出现次数的元素
1
2
3
c = Counter({'a':1, 'b':2, 'c':3})
print(list(c.elements()))
# ['a', 'b', 'b', 'c', 'c', 'c']

  • most_common()：返回一个出现次数从大到小的前k个元素的列表，复杂度

    • 缺省值为返回所有

    • 输入k小于最长长度，返回前k个数

  • subtract()：将两个counter对象中的元素对应计数相减

常规字典方法也对counter对象有效

map映射函数

可以将一个函数作用于一个或多个可迭代对象的元素上

一般使用lambda函数

1
2
3
4
5
numbers = [1, 2, 3, 4, 5]
squared_numbers = map(lambda x: x * x, numbers)

print(list(squared_numbers))
# 输出: [1, 4, 9, 16, 25]

类似的可以使用函数推导式

1
2
3
4
5
numbers = [1, 2, 3, 4, 5]
squared_numbers = [x * x for x in numbers]

print(squared_numbers)
# 输出: [1, 4, 9, 16, 25]

排序

内置排序

使用sorted()函数对可迭代对象排序

1
2
sorted([5, 2, 3, 1, 4])
# [1, 2, 3, 4, 5]

也可以使用list自带的方法list.sort()

使用reverse=True参数降序排序

重载小于号

对于自定义类型，可以通过重载小于号来自定义排序

1
2
3
4
5
6
7
8
9
10
11
12
from typing import Self

class Item:
    def __init__(self, height: int, score: int, age: int):
        self.height = height
        self.score = score
        self.age = age

    def __lt__(self, other: Self) -> bool:
        if self.score == other.score:
            return self.age < other.age
        return self.score > other.score

重载排序规则

可以将lambda函数传入key来自定义排序规则

key的排序规则是：先比较 key 的第一个元素，如果相同，再比较第二个

默认排序是升序，在元素前加上负号就可以变为降序了

1
2
3
4
5
6
7
8
class Item:
    def __init__(self, height: int, score: int, age: int):
        self.height = height
        self.score = score
        self.age = age

a = [Item(180, 90, 21), Item(175, 92, 24), Item(185, 90, 22)]
a.sort(key=lambda x: (-x.score, x.age))

内置库二分

使用内置库bisect可以进行二分，第一个参数为查找的列表，第二个参数为要查找的数，返回值为结果的索引

  • bisect/bisect_right类似于upper_bound
  • bisect_left类似于lower_bound
1
2
from bisect import *
bisect(a, x, lo = 0, hi = len(nums))

给定一个单调不减的数组a，在区间中，返回第一个严格大于x的下标位置

时间复杂度

语法糖

enumerate

enumerate() 函数用于将一个可遍历对象组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中

1
2
3
4
5
6
7
8
seq = ['one', 'two', 'three']
for i, element in enumerate(seq):
    print i, element
'''
0 one
1 two
2 three
'''

zip并行遍历

同时遍历两个可迭代对象：

1
2
for a, b in zip(A, B):
    print(a, b)

构造pair

1
pairs = list(zip(A, B))

解包

1
x, y = point

还可以用星号解包

1
2
3
4
5
a, *b = [1,2,3,4]
# a = 1, b = [2,3,4]

*_, last = [1,2,3,4]
# last = 4

any/all

any用于判断是否存在满足条件的

1
any(x>5 for x in arr)

all用于判断是否全部满足条件

1
all(x>0 for x in arr)

max/min 的key属性

可以设定key按照某个属性进行比较，对于自定义数据类型

1
2
best = max(arr, key=lambda x:x.score)
mn = min(arr, key=lambda x:abs(x))
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
赞助喵
非常感谢您的喜欢！
赞助喵