Python 竞赛编程语法

英文版本

输入

一行包含一个整数

x = int(input())

一行包含一个字符串

x = input()

包含多个整数的行

# one
x, y, z = map(int, input().split())
# two
xyz = [int(t) for t in input().split()]

包含多个整数的行

如果读入数据较大，input() 会很慢，可以使用 stdin.readline() 来加速

stdin.readline() 需要调用 sys 库，默认输入为字符串形式，需要 int 或者 float 来强制类型转换

⚠️注意

stdin.readline() 会将末尾的 \n 也读进去，可以加 .strip() 去掉或者使用切片删除

from sys import stdin
n = int(input())
for _ in range(n):
  x, y, z = map(int, stdin.readline().split())
# or back list[[], [], []...[]]
	xyz = [list(map(int, stdin.readline().split())) for _ in range(n)]

多行输入，每行一个字符串

from sys import stdin
for _ in range(n):
  s = stdin.readline()[:-1]
# or back list [[], [], [], ...[]]
s = [stdin.readline()[:-1] for _ in range(n)]

输出

输出YES或者NO

当 condition 为真的时候，首字符是 N，每隔一个取一个字符，得到 No

反之首字符为 Y，得到 Yes

print("YNeos"[condition::2])

可以利用切片来简化代码

n = input()
if (n == '3') or (n == '5') or (n == '7'):
    print('YES')
else:
    print('NO')

print('NYOE S'[input()in'357'::2])

列表（数组）

一维列表

x = [0 for _ in range(n)]
# or
x = [0] * n

二维列表

x = [[0] * m for _ in range(n)]

扁平化嵌套列表

外层循环 for y in data 拿到 data 里的每一个子列表

内层循环 for x in y 拿到 y 列表的每一个元素，这些元素都会逐个添加到 L 当中

data = [[1,2,3],[4,5,6],[7,8,9]]
L = [x for y in data for x in y]
print(b)

[1,2,3,4,5,6,7,8,9]

二维列表排序

按照第二个元素进行排序

L = [[1, 4, 3], [2, 3, 4], [3, 4, 5], [4, 5, 6], [2, 3, 4], [1, 5, 3], [2, 3, 4], [5, 6, 7]]
L = sorted(L, key=lambda x: x[1])
print(L)

[[2, 3, 4], [2, 3, 4], [2, 3, 4], [1, 4, 3], [3, 4, 5], [4, 5, 6], [1, 5, 3], [5, 6, 7]]

字符串

字符串拼接

直接在字符串后面加入一个字符是非常慢的，时间复杂度为 $\mathcal{O}(N^2)$

最好的做法是：先加入到一个列表中，最后通过 join 方法加到字符串末尾，时间复杂度 $\mathcal{O}(N \log N)$

last = []
for x in s:
  if condition:
    last.append(x)
res = ''.join(last)

循环结构

利用列表加速循环

在不需要循环的索引值的时候，可以不使用 range，而是采用以下写法

N = 10
for _ in [0] * N:
  ....

或者利用列表加速双重循环

在内层循环中，往往涉及到一些不必要的重复运算，可以使用列表一次性计算好

使用列表优化第二重循环，可以更好利用缓存以及减少生成器的开销

range() 函数返回一个生成器，并且是一个惰性函数，即会动态求出下一个的迭代值，在密集计算情况下，频繁调用生成器可能会增加一定的时间开销

这个做法是以空间换时间，因为提前生成列表会吃掉一部分使用空间，大概快个 1.5 倍。

for i in range(X):
  tmp_Y = list(range(Y))
  for j in tmp_Y:
    .....

更快的速度

全局变量会稍慢，可以创建一个 main 函数，将代码放在 main 函数下面，然后调用即可

import 和变量一样，如果把它放在函数中，把它变成局部函数，速度会更快

from sys import stdin
def main():
  from builtins import input, in...
  ....
main()

加快stdin.readline()

把 stdin.readline() 方法写入变量中会更快

from sys import stdin
def main():
  readline = stdin.readline
  a, b = map(int, readline().split())

无穷大

将 float('inf') 分配给一个变量，会更快

INF = float('inf')

杂项

collections 库

Counter 对象是一个字典，实现了加法和减法，可以快速统计重复元素的个数，如果出现次数为负数，那么该键值对会丢失掉。

键值对 = (权值：出现次数)

from collections import Counter
L1 = [1,2,3,4,5]
L2 = [1,2,3,4,5,6]

a = Counter(L1)
b = Counter(L2)

print(a+b)

print(b-a)

a = a + b
print(a.items())

print(a.keys())

print(a.values())

for k, v in a.items():
  print(k, v)

Counter({1: 2, 2: 2, 3: 2, 4: 2, 5: 2, 6: 1})
Counter({6: 1})
dict_items([(1, 2), (2, 2), (3, 2), (4, 2), (5, 2), (6, 1)])
dict_keys([1, 2, 3, 4, 5, 6])
dict_values([2, 2, 2, 2, 2, 1])
1 2
2 2
3 2
4 2
5 2
6 1

Math 库

整数平方根

from math import isqrt
isqrt(5)

如果想向上取整，采用以下写法 1 + isqrt(x-1)

from math import isqrt
1 + isqrt(5-1)

最小公倍数，最大公约数

Python3.9 以后支持任意数量的参数

from math import lcm, gcd
gcd(10, 5)
lcm(10, 5)

5
10

itertools 库

accumulate

计算累积和，返回值是一个序列

from itertools import*
L = [1,2,3]
print(list(accumulate(L)))

[1, 3, 6]

groupby

对连续相同的元素进行分组，不连续的元素单独成组

from itertools import groupby

L = [1, 1, 2, 3, 3, 3, 1, 2, 2]

for key, value in groupby(L):
    print(key, list(value))

1 [1, 1]
2 [2]
3 [3, 3, 3]
1 [1]
2 [2, 2]

还可以结合 lambda 表达式来使用

下列代码将余数为 1 的分为一组，余数为 0 的分为另一组

from itertools import groupby

a = [1, 3, 2, 4, 3, 1, 1, 2, 4]

for key, value in groupby(a, key=lambda x: x % 2):
    print(key, list(value))

1 [1, 3]
0 [2, 4]
1 [3, 1, 1]
0 [2, 4]

进制转换

int() 函数可以通过传入第二个参数 base 来转换成十进制数

其中字符串前缀以 0b 开始的是二进制，以 0x 开始的为十六进制

print(int("1010", 2))
print(int("1A", 16))
print(int('0b1010'), 2)
print(int("0xAC"), 16)

利用 bin() 可以转二进制，hex() 可以转十六进制

print(bin(255)) 
print(hex(255))

0b11111111
0xff

Python 竞赛语法