Python 竞赛模板

基础设置

输入输出

输入

# 单个整数
n = int(input())

# 多个整数（空格分隔）
a, b = map(int, input().split())

# 一行整数转列表
arr = list(map(int, input().split()))

# 去除换行符
s = input().strip()  # 去除首尾空白（含 \n）

# 读取 n 行到列表
arr = [int(input()) for _ in range(n)]

# 读取到文件结尾（EOF）：直接遍历 sys.stdin
for line in sys.stdin:
    a, b = map(int, line.strip().split())
    print(a + b)

# ⚠️ input() 会保留换行符，需要 strip()
s = input().strip()  # 去除 '\n'

# ⚠️ int() 会自动去除空白和符号
int("  123  ")  # 123
int("-123")     # -123
int("+123")     # 123

输出

print(x)           # 单个值
print(a, b, c)     # 多个值（默认空格分隔）

# 空格分隔的列表
print(*ans)                    # 解包输出
print(" ".join(map(str, ans))) # join 输出

# 不换行输出
print(x, end='')     # 末尾不换行
print(x, end=' ')    # 末尾加空格

# 交互题：必须加 flush！强制刷新缓冲区
print(f"? {mid}")
sys.stdout.flush()

常用配置

# 加速输入
import sys
input = sys.stdin.readline
# 设置递归深度（DFS 必备）
sys.setrecursionlimit(10**6)

# 常用导入
import math
import itertools
import bisect
from collections import deque, Counter, defaultdict

# 常用常量
INF = 10**18          # 无穷大（整数，推荐）
MOD = 10**9 + 7       # 取模

# ⚠️ 禁止用浮点数作为 INF，会导致 TLE
# INF = 1e9           # 错误！浮点数运算慢
# INF = float('inf')  # 错误！浮点数运算慢

# ⚠️ 常见陷阱

# 列表 * n 可能是浅拷贝
a = [[0] * 3] * 3     # 错误！三个引用同一列表
a = [[0] * 3 for _ in range(3)]  # 正确

# 浮点数比较
abs(a - b) < 1e-9     # 判断浮点数相等

字符串

基本操作

s = "hello"
lst = list(s)        # 字符串转列表

# 大小写转换
s.upper()            # 转大写
s.lower()            # 转小写
s.capitalize()       # 首字母大写
s.swapcase()         # 大小写互换

# 去除空白
s.strip()            # 去除首尾空白
s.lstrip()           # 去除左边空白
s.rstrip()           # 去除右边空白

查找与替换

# 查找
s.find('a')          # 返回第一个 'a' 的索引，不存在返回 -1
s.rfind('a')         # 从右边找
s.index('a')         # 同 find，但不存在会报错
s.count('a')         # 统计字符出现次数
s.count('abc')       # 统计子串出现次数

# 替换
s.replace('old', 'new')       # 替换所有
s.replace('old', 'new', 1)    # 只替换第一个
s.replace(c, ' ')             # 字符替换为空格

判断方法

# 字符/字符串判断
'a'.isdigit()        # 单字符判断：False
'5'.isdigit()        # 数字字符：True
s.isdigit()          # 全是数字
s.isalpha()          # 全是字母
s.islower()          # 全是小写
s.isupper()          # 全是大写

# 回文判断
s == s[::-1]         # 字符串是否回文

格式化与对齐

# 填充对齐
s = s.ljust(width, '0')   # 左边补 '0' 到指定长度
s = s.rjust(width, '0')   # 右边补 '0'
s = s.center(width, '0')  # 居中补 '0'

# 补零
s = s.zfill(5)            # 左边补 '0' 到宽度 5

# 分割与连接
s.split()                 # 按空白分割（默认）
s = ' '.join(lst)        # 用空格连接（⚠️ lst 必须是字符串列表！）
s = ''.join(lst)          # 直接连接

# ⚠️ join() 要求所有元素都是字符串
nums = [1, 2, 3]
# ' '.join(nums)          # ❌ TypeError: sequence item 0: expected str instance, int found
' '.join(map(str, nums))  # ✅ '1 2 3'

去重与排序

# 字符串去重（保持顺序）
s = ''.join(dict.fromkeys(s))

# 字符串排序
sorted_s = ''.join(sorted(s))           # 按字符排序
words.sort()                            # 列表按字典序排序
# Python 字符串默认按字典序比较：'A' < 'Z' < 'a' < 'z'

ASCII 码与进制转换

# ord() 和 chr()
ord('A')      # 字符转 ASCII 码: 65
chr(97)       # ASCII 码转字符: 'a'

# 字母序号转换（A-Z → 0-25）
ord('A') - ord('A')  # 0

# 数字字符转数字
int('5')           # 5
ord('5') - ord('0') # 5

# 进制转换
int("FF", 16)      # 十六进制转十进制: 255
int("101", 2)      # 二进制转十进制: 5
int("77", 8)       # 八进制转十进制: 63

# 十进制转其他进制
bin(255)           # '0b11111111'
oct(255)           # '0o377'
hex(255)           # '0xff'

最长数字子串

import re

# 提取连续数字串
s = "abc123xyz456"
arr = re.findall(r'\d+', s)  # ['123', '456']

# 找最长数字子串
max_len = max(len(x) for x in arr)
res = ''.join(x for x in arr if len(x) == max_len)

最长回文子串

s = input().strip()

res = ""

def expand(l, r):
    """从中心 (l, r) 向两边扩展，返回最长回文子串"""
    while l >= 0 and r < len(s) and s[l] == s[r]:
        l -= 1
        r += 1
    return s[l + 1: r]

for i in range(len(s)):
    res = max(res, expand(i, i), key=len)     # 奇数长度回文
    res = max(res, expand(i, i + 1), key=len) # 偶数长度回文

print(len(res))

数论

向上取整

# 向上取整到 k 的倍数
(n + k - 1) // k * k

import math
math.ceil(n / k) * k      # 更易读

四舍五入

# 1. 四舍五入（通用模板，避免浮点误差）
def round_div(a, b):
    # 计算 a / b，四舍五入到整数
    # 原理：判断小数部分是否 >= 0.5
    return a // b + (2 * (a % b) >= b)
# 示例：7 // 4 = 1，但 round_div(7, 4) = 2

# 2. 四舍五入（浮点数版本）
n = float(input())
if n - int(n) >= 0.5:
    print(int(n) + 1)
else:
    print(int(n))

质因数分解

def prime_factors(n):
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors

约瑟夫环

# n 个人围成一圈，每数到 k 就淘汰一人，求最后存活者的初始位置
def josephus(n, k):
    if n == 1:
        return 0
    return (josephus(n-1, k) + k) % n

K进制转换

# 数字 -> k进制字符串（每位对应字符集 s）
def idx_to_password(idx, k, m, s):
    res = []
    for _ in range(m):
        res.append(s[idx % k])
        idx //= k
    return ''.join(reversed(res))

# k进制字符串 -> 数字
def password_to_idx(password, k, s):
    idx = 0
    for ch in password:
        idx = idx * k + s.index(ch)
    return idx

约数

def get_divisors(n: int):
    """返回 1 到 n 所有数的约数列表"""
    divs = [[] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            divs[j].append(i)
    return divs

# 最大公约数 / 最小公倍数
g = math.gcd(a, b)
lcm = a * b // g

# 约数枚举：求出 n 的所有约数（因数）
def divisors(n):
    small, large = [], []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            small.append(i)
            if i != n // i:
                large.append(n // i)
    return small + large[::-1]

素数

# 素数判断。直接调用 is_prime(n)
def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

位运算

1 << i           # 2^i（左移，i=3 → 8）
# 判断
x & (1 << k)     # 检查第 k 位是否为 1
x >> k & 1       # 获取第 k 位的值

x.bit_length()   # 整数的二进制位数（5→3, 1→1, 0→0）
x.bit_count()    # 二进制中 1 的个数

x & -x           # 最低位 1（获取二进制最低位的 1）
x | 1            # 将最低位设为 1
x & ~1           # 将最低位设为 0
x ^ 1            # 翻转最低位

# 遍历检查某一位
for i in range(bit_count):
    if (S >> i) & 1:  # 检查第 i 位是否为 1
        # 第 i 位为 1
        pass

# 设置
x | (1 << k)     # 将第 k 位设为 1
x & ~(1 << k)    # 将第 k 位设为 0
x ^ (1 << k)     # 翻转第 k 位

# 常用
x & (x - 1)      # 清除最低位的 1
x | (x - 1)      # 将最低位 0 变成 1
x ^ (x + 1)      # 获取最低位不同的数

# 子集枚举
for sub in range(mask + 1):
    sub = (sub - 1) & mask  # 枚举子集（不包括 0）

# 最低位 1 的位置
bit = (x & -x).bit_length() - 1

埃拉托斯特尼筛法

minp = []
primes = []

def sieve(n: int):
    """埃拉托斯特尼筛法 - 计算 minp 和 primes"""
    global minp, primes
    minp = [0] * (n + 1)
    primes = []

    for i in range(2, n + 1):
        if minp[i] == 0:
            minp[i] = i
            primes.append(i)

        for p in primes:
            if i * p > n:
                break
            minp[i * p] = p
            if p == minp[i]:
                break

快速幂

# 快速幂：计算 a^b mod mod，高效处理大数幂运算
# 使用：pow_mod(2, 10, 1000) = 24 (2^10=1024 mod 1000)
def pow_mod(a, b, mod):
    res = 1
    a %= mod
    while b:
        if b & 1:
            res = res * a % mod
        a = a * a % mod
        b >>= 1
    return res

组合数

# 组合数（预计算）：计算组合数 C(n, k) = n! / (k!(n-k)!)
# - 使用：fact, inv_fact = comb_init(1000000, MOD)
# 		 print(C(100, 50, MOD, fact, inv_fact))
# - 注意：需要 MOD 为质数（常用 10^9+7）
def comb_init(n, mod):
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i-1] * i % mod
    inv_fact = [1] * (n + 1)
    inv_fact[n] = pow(fact[n], mod-2, mod)
    for i in range(n, 0, -1):
        inv_fact[i-1] = inv_fact[i] * i % mod
    return fact, inv_fact

def C(n, k, mod, fact, inv_fact):
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % mod * inv_fact[n-k] % mod

乘法逆元

# 乘法逆元：求 a 在模 mod 下的逆元（即 a^(-1) mod mod）
# 使用：modinv(3, 7) = 5（因为 3*5=15≡1 mod 7）
def modinv(a, mod):
    return pow(a, mod-2, mod)

扩展欧几里得

# 扩展欧几里得（求逆元）
def exgcd(a, b):
    if b == 0:
        return 1, 0, a
    x, y, g = exgcd(b, a % b)
    return y, x - (a // b) * y, g

图论

二分图检测

def is_bipartite(n, adj, node):
    """检测图是否为二分图，返回 (is_bipartite, min_changes)"""
    color = [-1] * n  # -1: 未染色, 0/1: 颜色
    ans = 0

    for i in range(n):
        if color[i] != -1:
            continue
        q = deque([i])
        color[i] = 0
        res = [0, 0]

        while q:
            u = q.popleft()
            for v in adj[u]:
                if color[v] == -1:
                    color[v] = color[u] ^ 1
                    q.append(v)
                elif color[v] == color[u]:
                    return False, 0
            res[0] += color[u] ^ node[u]
            res[1] += (color[u] ^ 1) ^ node[u]

        ans += min(res)

    return True, ans

拓扑排序

def topological_sort():
    in_degree = [0] * n
    for u in range(n):
        for v in adj[u]:
            in_degree[v] += 1
    q = deque([i for i in range(n) if in_degree[i] == 0])
    result = []
    while q:
        u = q.popleft()
        result.append(u)
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                q.append(v)
    return result if len(result) == n else []  # 有环返回空