红魔咖啡馆

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

0%

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

发表于 更新于 分类于 ，
本文字数： 4.9k 阅读时长 ≈ 9 分钟
总结了常用的Python在算法竞赛中的输入输出，优化等方法

火车头

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个元素的列表，复杂度\(O(n\log 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，在\([lo,hi]\)区间中，返回第一个严格大于x的下标位置

时间复杂度\(O(\log n)\)

语法糖

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))