Python 竞赛模板
Python 竞赛模板
输入输出
import sys input = sys.stdin.readline # 加速输入 sys.setrecursionlimit(10**6) # 递归深度 # 读取单个或多个值 n = int(input()) a, b = map(int, input().split()) # 读取一行整数 arr = list(m
矩阵路径构造题解
矩阵路径构造题解
题目概述
构造一个 n × m
的矩阵（n × m ≤ 200），对于每个查询的非负整数
S，需要找到一条从 (1, 1) 到 (n, m) 的路径，满足：
每个单元格至多被经过一次
路径上所有数字之和等于 S
构造思路
矩阵构造
设 n = ⌊log2(max S)⌋ + 1，即最大查询值
Smax
的二进制位数，m = 3。
构造一个 n ×
use_python
输入
readline()
、readlines() 和 read() 区别
import sys # 输入： # Hello # World # ! # 使用 readline() line1 = sys.stdin.readline() # "Hello\n" line2 = sys.stdin.readline() # "World\n"
05_Priority Queues 优先队列
Priority Queues 优先队列
简介
优先队列（Priority Queue 或 Heap）支持以下操作： - 插入元素 -
删除最高优先级元素 - 获取最高优先级元素
以上操作的时间复杂度均为 O(log N)。
优先队列比集合更简单更快，应尽可能使用优先队列。
Python 实现
注意：Python（与 C++
不同）中删除和获取的是最小元素。
heapq
不是封
Greedy Algorithms with Sorting 贪心算法与排序
Greedy Algorithms with
Sorting
贪心算法与排序
贪心算法在每一步选择当前最优的选项，通常与排序配合使用。
一、贪心算法基础
贪心算法的核心是价值函数：决定哪个选择是最优的。
要最大化某个值 → 每次选择最大的
要最小化某个值 → 每次选择最小的
关键：贪心算法需要证明其正确性，通常通过交换参数证法（exchange
argument）。
数据结构
Queues 队列
队列是一种先进先出 First In First
Out（FIFO）的数据结构，支持三种操作，所有操作的时间复杂度均为 𝒪(1) 。
std::queue
push: 在队列的末尾插入
pop: 从队列的前端删除
front: 获取前端元素但不将其移除
queue<int> q; q.push(1); //
cf
模板
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "algo/debug.h" #else #define debug(...) 42 #endif int main() { ios::sync_with_stdio(false); cin.t
Graph 图
Graph 图
邻接表
python
N, M = map(int, input().split()) adj = [[] for _ in range(N)] for i in range(M): u, v = map(int, input().split()) adj[u].append(v) adj[v].append(u) u = 1 # print number of v