Library Checker(judge.yosupo.jp 官方题库源 yosupo06/library-checker-problems,下称 LCG)是算法/数据结构库的「验证题」集:每题对应一个经典算法的标准接口,不讲故事、不设思维陷阱,考的是「把这个模板写对、写快」。全量 253 题(Apache 2.0),本单按类目整理,站内链接直达中文题面。
怎么用这份单子
- 括号里的
snake_case是 LCG 原题名,方便对照原仓库的生成器与数据; - 标注「special judge」的题输出任意合法解,暂不可本地评测(本地 judge 仅支持 diff 比对),待 checker 支持后开放;
- LCG 自带对抗性数据生成器与 naive/wa/tle 对拍解,适合当模板正确性与复杂度的「单元测试」;
- 勾选进度按题号全局共享,跨题目单不丢;
- 在 GitHub 上阅读时,
/problem/…是站内路径,需补https://roj.ac.cn前缀。
目录
- 数据结构(47 题)
- 树(20 题)
- 图论(38 题)
- 字符串(12 题)
- 多项式(28 题)
- 卷积(16 题)
- 线性代数(18 题)
- 数论(26 题)
- 组合计数(17 题)
- 集合幂级数(5 题)
- 计算几何(10 题)
- 高精度(6 题)
- 其他(7 题)
- 入门样例(3 题)
数据结构
- 矩形加点求和(
rectangle_add_point_get) - 单点加区间求和(
point_add_range_sum) - 静态区间最小值(
staticrmq) - 并查集(
unionfind) - 矩形并面积(
area_of_union_of_rectangles) - 关联数组(
associative_array) - 双端队列(
deque) - 双端队列(带全体复合操作)(
deque_operate_all_composite) - 双端优先队列(
double_ended_priority_queue) - 动态点赋值矩形仿射矩形求和(
dynamic_point_set_rectangle_affine_rectangle_sum) - 动态序列区间仿射区间求和(
dynamic_sequence_range_affine_range_sum) - 直线加查询最小值(
line_add_get_min) - 多数投票(
majority_voting) - 有序集合(
ordered_set) - 可持久化队列(
persistent_queue) - 可持久化区间仿射区间求和(
persistent_range_affine_range_sum) - 可持久化并查集(
persistent_unionfind) - 单点加矩形求和(
point_add_rectangle_sum) - 单点赋值区间复合(
point_set_range_composite) - 单点赋值区间复合(大数组)(
point_set_range_composite_large_array) - 单点赋值区间元素出现次数(
point_set_range_frequency) - 单点赋值区间排序区间复合(
point_set_range_sort_range_composite) - 前驱问题(
predecessor_problem) - 队列(带全体复合操作)(
queue_operate_all_composite) - 区间加区间最小值(
range_add_range_min) - 区间仿射单点查询(
range_affine_point_get) - 区间仿射区间求和(
range_affine_range_sum) - 区间仿射区间求和(大数组)(
range_affine_range_sum_large_array) - 区间取 min/max、加 区间求和(
range_chmin_chmax_add_range_sum) - 区间第 k 小(
range_kth_smallest) - 区间线性加区间最小值(
range_linear_add_range_min) - 区间连边并查集(
range_parallel_unionfind) - 区间反转区间求和(
range_reverse_range_sum) - 区间赋值区间复合(
range_set_range_composite) - 矩形求和(
rectangle_sum) - 线段加查询最小值(
segment_add_get_min) - 集合异或最小值(
set_xor_min) - 静态区间不同元素个数(
static_range_count_distinct) - 静态区间元素出现次数(
static_range_frequency) - 静态区间逆序对查询(
static_range_inversions_query) - 静态区间最长上升子序列查询(
static_range_lis_query) - 静态区间众数查询(
static_range_mode_query) · special judge - 静态区间求和(
static_range_sum) - 静态区间求和(带上界)(
static_range_sum_with_upper_bound) - 静态矩形加矩形求和(
static_rectangle_add_rectangle_sum) - 带权并查集(
unionfind_with_potential) - 带权并查集(非交换群)(
unionfind_with_potential_non_commutative_group)
树
- 最近公共祖先(
lca) - 笛卡尔树(
cartesian_tree) - 公共区间分解树(
common_interval_decomposition_tree) · special judge - 动态树子树加子树求和(
dynamic_tree_subtree_add_subtree_sum) - 动态树点加路径求和(
dynamic_tree_vertex_add_path_sum) - 动态树点加子树求和(
dynamic_tree_vertex_add_subtree_sum) - 动态树点赋值路径复合(
dynamic_tree_vertex_set_path_composite) - 树上距离频数表(
frequency_table_of_tree_distance) - 树上跳转(
jump_on_tree) - 单点赋值树路径复合和(
point_set_tree_path_composite_sum) - 单点赋值树路径复合和(固定根)(
point_set_tree_path_composite_sum_fixed_root) - 有根树同构分类(
rooted_tree_isomorphism_classification) · special judge - 有根树拓扑序最小逆序对(
rooted_tree_topological_order_with_minimum_inversions) · special judge - 树的直径(
tree_diameter) · special judge - 树路径复合和(
tree_path_composite_sum) - 点加路径求和(
vertex_add_path_sum) - 点加树上等距层求和(
vertex_add_range_contour_sum_on_tree) - 点加子树求和(
vertex_add_subtree_sum) - 树上等距层加点查询(
vertex_get_range_contour_add_on_tree) - 点赋值路径复合(
vertex_set_path_composite)
图论
- 指派问题(
assignment) · special judge - 双连通分量(
biconnected_components) · special judge - 二分图边染色(
bipartite_edge_coloring) · special judge - 二分图最大匹配(
bipartitematching) · special judge - 弦图判定(
chordal_graph_recognition) · special judge - 色数(
chromatic_number) - 色多项式(
chromatic_polynomial) - 补图连通分量(
connected_components_of_complement_graph) · special judge - 四元环计数(
counting_c4) - 欧拉回路计数(
counting_eulerian_circuits) - 有向图生成树计数(
counting_spanning_tree_directed) - 无向图生成树计数(
counting_spanning_tree_undirected) - 有向图找环(
cycle_detection) · special judge - 无向图找环(
cycle_detection_undirected) · special judge - 有向图最小树形图(
directedmst) · special judge - 支配树(
dominatortree) - 动态图点加连通块求和(
dynamic_graph_vertex_add_component_sum) - 枚举团(
enumerate_cliques) - 枚举三角形(
enumerate_triangles) - 有向图欧拉路径(
eulerian_trail_directed) · special judge - 无向图欧拉路径(
eulerian_trail_undirected) · special judge - 一般图最大匹配(
general_matching) · special judge - 一般图最大权匹配(
general_weighted_matching) · special judge - 动态星形增广图全局最小割(
global_minimum_cut_of_dynamic_star_augmented_graph) - 增量最小生成森林(
incremental_minimum_spanning_forest) - 增量强连通分量(
incremental_scc) - K 次最短路(
k_shortest_walk) - 最大独立集(
maximum_independent_set) · special judge - 最小费用 b-流(
min_cost_b_flow) · special judge - 最小直径生成树(
minimum_diameter_spanning_tree) · special judge - 最小生成树(
minimum_spanning_tree) · special judge - 最小斯坦纳树(
minimum_steiner_tree) · special judge - 强连通分量(
scc) · special judge - 最短路(
shortest_path) · special judge - st 编号(
st_numbering) · special judge - 三边连通分量(
three_edge_connected_components) · special judge - 树分解(宽度 2)(
tree_decomposition_width_2) · special judge - 双边连通分量(
two_edge_connected_components) · special judge
字符串
- Z 算法(
zalgorithm) - Aho-Corasick 自动机(
aho_corasick) - 回文树(Eertree)(
eertree) - 枚举回文串(
enumerate_palindromes) - 最长公共子串(
longest_common_substring) · special judge - Lyndon 分解(
lyndon_factorization) - 子串个数(
number_of_substrings) - 双端队列回文计数(
palindromes_in_deque) - 前缀-子串 LCS(
prefix_substring_lcs) - Run 枚举(
runenumerate) - 后缀数组(
suffixarray) - 通配符模式匹配(
wildcard_pattern_matching)
多项式
- 形式幂级数复合(
composition_of_formal_power_series) - 形式幂级数复合(大模数)(
composition_of_formal_power_series_large) - 形式幂级数复合逆(
compositional_inverse_of_formal_power_series) - 形式幂级数复合逆(大模数)(
compositional_inverse_of_formal_power_series_large) - 单项式基转牛顿基(
conversion_from_monomial_basis_to_newton_basis) - 多项式除法(
division_of_polynomials) - 形式幂级数 exp(
exp_of_formal_power_series) - 形式幂级数 exp(稀疏)(
exp_of_formal_power_series_sparse) - 多项式因式分解(
factorization_of_polynomials) · special judge - 形式幂级数求逆(
inv_of_formal_power_series) - 二元形式幂级数求逆(
inv_of_formal_power_series_2d) - 形式幂级数求逆(稀疏)(
inv_of_formal_power_series_sparse) - 多项式求逆(
inv_of_polynomials) - 形式幂级数 log(
log_of_formal_power_series) - 形式幂级数 log(稀疏)(
log_of_formal_power_series_sparse) - 多点求值(
multipoint_evaluation) - 多点求值(等比数列)(
multipoint_evaluation_on_geometric_sequence) - 多项式插值(
polynomial_interpolation) - 多项式插值(等比数列)(
polynomial_interpolation_on_geometric_sequence) - 多项式求根(
polynomial_root_finding) · special judge - 多项式平移(Taylor Shift)(
polynomial_taylor_shift) - 形式幂级数快速幂(
pow_of_formal_power_series) - 形式幂级数快速幂(稀疏)(
pow_of_formal_power_series_sparse) - 多项式前缀和(
prefix_sum_of_polynomial) - 多项式序列连乘积(
product_of_polynomial_sequence) - 多项式采样点平移(
shift_of_sampling_points_of_polynomial) - 形式幂级数开方(
sqrt_of_formal_power_series) · special judge - 形式幂级数开方(稀疏)(
sqrt_of_formal_power_series_sparse) · special judge
卷积
- 按位与卷积(
bitwise_and_convolution) - 按位异或卷积(
bitwise_xor_convolution) - 卷积(F2^64 域)(
convolution_F_2_64) - 卷积(
convolution_mod) - 卷积(模 1000000007)(
convolution_mod_1000000007) - 卷积(模 2^64)(
convolution_mod_2_64) - 卷积(大模数)(
convolution_mod_large) - 最大公约数卷积(
gcd_convolution) - 最小公倍数卷积(
lcm_convolution) - Min-Plus 卷积(凹 × 任意)(
min_plus_convolution_concave_arbitrary) - Min-Plus 卷积(凸 × 任意)(
min_plus_convolution_convex_arbitrary) - Min-Plus 卷积(凸 × 凸)(
min_plus_convolution_convex_convex) - 乘法幺半群卷积(Z/2^N Z)(
mul_mod2n_convolution) - 乘法幺半群卷积(Z/P Z)(
mul_modp_convolution) - 多维卷积(截断)(
multivariate_convolution) - 多维卷积(循环)(
multivariate_convolution_cyclic)
线性代数
- 伴随矩阵(
adjugate_matrix) - 特征多项式(
characteristic_polynomial) - 矩阵的 Hafnian(
hafnian_of_matrix) - F2 向量空间的交(
intersection_of_f2_vector_spaces) · special judge - 矩阵求逆(
inverse_matrix) - 矩阵求逆(模 2)(
inverse_matrix_mod_2) - 矩阵行列式(
matrix_det) - 矩阵行列式(任意模数)(
matrix_det_arbitrary_mod) - 矩阵行列式(模 2)(
matrix_det_mod_2) - 矩阵乘法(
matrix_product) - 矩阵乘法(模 2)(
matrix_product_mod_2) - 矩阵的秩(
matrix_rank) - 矩阵的秩(模 2)(
matrix_rank_mod_2) - 矩阵的 Pfaffian(
pfaffian_of_matrix) - 矩阵快速幂(
pow_of_matrix) - 稀疏矩阵行列式(
sparse_matrix_det) - 线性方程组(
system_of_linear_equations) · special judge - 线性方程组(模 2)(
system_of_linear_equations_mod_2) · special judge
数论
- Bernoulli 数(
bernoulli_number) - 质数计数(
counting_primes) - 无平方因子数计数(
counting_squarefrees) - 狄利克雷卷积与前缀和(
dirichlet_convolution_and_prefix_sums) - 狄利克雷逆与前缀和(
dirichlet_inverse_and_prefix_sums) - 离散对数(固定模数)(
discrete_logarithm_fixed_mod) - 离散对数(
discrete_logarithm_mod) · special judge - 枚举质数(
enumerate_primes) - 枚举整除商(
enumerate_quotients) - 分解质因数(
factorize) - 高斯整数最大公约数(
gcd_of_gaussian_integers) · special judge - 整数开 k 次方(
kth_root_integer) - 模意义下开 k 次方(
kth_root_mod) · special judge - 线性函数取模最小值(
min_of_mod_of_linear) - Nim 积(
nim_product_64) - 质数判定(
primality_test) - 原根(
primitive_root) · special judge - 有理数逼近(
rational_approximation) - 模意义下开平方(
sqrt_mod) · special judge - Stern-Brocot 树(
stern_brocot_tree) - 线性函数取整求和(
sum_of_floor_of_linear) - 积性函数前缀和(
sum_of_multiplicative_function) - 积性函数前缀和(大范围)(
sum_of_multiplicative_function_large) - 欧拉函数前缀和(
sum_of_totient_function) - 迭代幂次取模(
tetration_mod) - 平方和表示(
two_square_sum) · special judge
组合计数
- Bell 数(
bell_number) - 二项式系数(
binomial_coefficient) - 二项式系数(质数模)(
binomial_coefficient_prime_mod) - 阶乘(
factorial) - 批量阶乘(
many_factorials) - 错排数(Montmort 数)(
montmort_number_mod) - 两序列间递增序列个数(
number_of_increasing_sequences_between_two_sequences) - 子序列个数(
number_of_subsequences) - 分拆数(
partition_function) - q-二项式系数(质数模)(
q_binomial_coefficient_prime_mod) - 模 p 子集和计数(
sharp_p_subset_sum) - 第一类斯特林数(
stirling_number_of_the_first_kind) - 第一类斯特林数(固定 k)(
stirling_number_of_the_first_kind_fixed_k) - 第一类斯特林数(小 p 大 n)(
stirling_number_of_the_first_kind_small_p_large_n) - 第二类斯特林数(
stirling_number_of_the_second_kind) - 第二类斯特林数(固定 k)(
stirling_number_of_the_second_kind_fixed_k) - 第二类斯特林数(小 p 大 n)(
stirling_number_of_the_second_kind_small_p_large_n)
集合幂级数
- 集合幂级数 exp(
exp_of_set_power_series) - 集合幂级数 log(
log_of_set_power_series) - 多项式复合集合幂级数(
polynomial_composite_set_power_series) - 集合幂级数幂投影(
power_projection_of_set_power_series) - 子集卷积(
subset_convolution)
计算几何
- 凸多边形各顶点最远点(
all_furthest_neighbors) · special judge - 最近点对(
closest_pair) · special judge - 凸层(
convex_layers) - 三角形内点计数(
count_points_in_triangle) - 欧几里得最小生成树(
euclidean_mst) · special judge - 最远点对(
furthest_pair) · special judge - 曼哈顿最小生成树(
manhattanmst) · special judge - 最小圆覆盖(
minimum_enclosing_circle) - 极角排序(
sort_points_by_argument) · special judge - 静态凸包(
static_convex_hull) · special judge
高精度
- 高精度整数加法(
addition_of_big_integers) - 十六进制高精度整数加法(
addition_of_hex_big_integers) · special judge - 高精度整数除法(
division_of_big_integers) - 十六进制高精度整数除法(
division_of_hex_big_integers) · special judge - 高精度整数乘法(
multiplication_of_big_integers) - 十六进制高精度整数乘法(
multiplication_of_hex_big_integers) · special judge
其他
- 线性递推序列连续项(
consecutive_terms_of_linear_recurrent_sequence) - 求线性递推式(
find_linear_recurrence) · special judge - 线性递推第 k 项(
kth_term_of_linearly_recurrent_sequence) - 最长上升子序列(
longest_increasing_subsequence) · special judge - 指数乘多项式之和(
sum_of_exponential_times_polynomial) - 指数乘多项式无穷和(
sum_of_exponential_times_polynomial_limit) - 2-SAT(
two_sat) · special judge
入门样例
- A+B 问题(
aplusb) - 多组 A+B(
many_aplusb) - 多组 A+B(128 位)(
many_aplusb_128bit)