Template chuẩn
import sys
input = sys.stdin.readline # đọc nhanh hơn input() thông thường
def main():
n = int(input())
a = list(map(int, input().split()))
# code here
main()
Thay
input()bằngsys.stdin.readlinegiúp đọc input nhanh hơn đáng kể khi có nhiều dữ liệu.
Đọc Input
# Một số nguyên
n = int(input())
# Nhiều số trên một dòng
a, b, c = map(int, input().split())
# Một mảng
a = list(map(int, input().split()))
# N dòng, mỗi dòng một số
a = [int(input()) for _ in range(n)]
# N dòng, mỗi dòng nhiều số
a = [list(map(int, input().split())) for _ in range(n)]
# Đọc toàn bộ input một lần (nhanh nhất)
import sys
data = sys.stdin.read().split()
idx = 0
n = int(data[idx]); idx += 1
a = [int(data[idx+i]) for i in range(n)]; idx += n
Các cấu trúc dữ liệu
# List (mảng động)
a = []
a.append(x) # O(1)
a.pop() # O(1)
a.pop(i) # O(N)
a[i] # O(1)
len(a)
# Deque (stack + queue hiệu quả)
from collections import deque
dq = deque()
dq.append(x); dq.appendleft(x) # O(1)
dq.pop(); dq.popleft() # O(1)
# Dict (hash map)
mp = {}
mp[key] = val
mp.get(key, default)
key in mp
del mp[key]
for k, v in mp.items(): ...
# Set (hash set)
s = set()
s.add(x); s.remove(x); s.discard(x)
x in s # O(1)
# Counter
from collections import Counter
cnt = Counter(a)
cnt.most_common(3) # 3 phần tử xuất hiện nhiều nhất
Sắp xếp
a.sort() # in-place tăng dần
a.sort(reverse=True) # giảm dần
b = sorted(a) # trả về list mới
# Sắp xếp theo nhiều tiêu chí
pairs.sort(key=lambda x: (x[0], -x[1])) # tăng theo [0], giảm theo [1]
# Sắp xếp ổn định theo key tùy chỉnh
from functools import cmp_to_key
def cmp(a, b): return -1 if a < b else (1 if a > b else 0)
a.sort(key=cmp_to_key(cmp))
Tìm kiếm nhị phân
import bisect
a = sorted([1, 3, 3, 5, 7])
bisect.bisect_left(a, 3) # 1 — vị trí đầu tiên >= 3
bisect.bisect_right(a, 3) # 3 — vị trí đầu tiên > 3
# Đếm số lần xuất hiện
cnt = bisect.bisect_right(a, x) - bisect.bisect_left(a, x)
Heap (Priority Queue)
import heapq
# Min-heap
h = []
heapq.heappush(h, x)
heapq.heappop(h) # xóa và trả về min
h[0] # xem min, không xóa
# Max-heap: dùng giá trị âm
heapq.heappush(h, -x)
-heapq.heappop(h)
# Xây heap từ list O(N)
heapq.heapify(a)
# K phần tử lớn nhất / nhỏ nhất
heapq.nlargest(k, a)
heapq.nsmallest(k, a)
Toán học
from math import gcd, lcm, sqrt, log2, ceil, floor, inf
from math import comb, perm # C(n,k), P(n,k)
abs(x)
pow(a, b, mod) # a^b mod m, O(log b)
divmod(a, b) # (a//b, a%b)
# Số nguyên lớn: Python xử lý tự động, không tràn số
factorial = 1
for i in range(1, n+1): factorial *= i
Các thư viện hữu ích
from collections import defaultdict, Counter, deque
from itertools import combinations, permutations, product
from functools import lru_cache # memoization
# lru_cache — memoization tự động
@lru_cache(maxsize=None)
def dp(i, j):
if i == 0: return 0
return dp(i-1, j) + dp(i, j-1)
# defaultdict — dict với giá trị mặc định
graph = defaultdict(list)
graph[u].append(v)
# combinations / permutations
for combo in combinations([1,2,3], 2): # (1,2),(1,3),(2,3)
print(combo)
Lưu ý hiệu năng
| Vấn đề | Giải pháp |
|---|---|
input() chậm |
Dùng sys.stdin.readline |
| Nối chuỗi trong vòng lặp | Dùng "".join(list) |
| Đệ quy sâu | Tăng limit: sys.setrecursionlimit(300000) |
| Python chậm hơn C++ ~10-50x | Dùng PyPy nếu được phép, hoặc tối ưu thuật toán |
# Tăng giới hạn đệ quy nếu cần
import sys
sys.setrecursionlimit(300000)
Bình luận