线性基学习笔记

发表于 2023-07-26 更新于 2023-08-07 分类于学习笔记

线性基在 OI 中大部分时候是一种基于贪心的数据结构，主要用于解决异或有关的问题，其正确性证明需要基于向量等线性代数内容。

免责声明

本文仅介绍其在 OI 中的常见应用，内容将尽量基于实用性与浅显易懂的感性理解进行讲解，不会对其原理做出任何详细说明，请酌情阅读。如需详细讲解与证明请出门左转 OI-Wiki。

发表于 2023-07-26 分类于题解

求区间最大异或和。

发表于 2023-07-13 分类于题解

给定一张个点条边的无向连通图，每条边的边权是它的编号。

次询问，每次询问给定，表示询问从出发，恰好经过个点后经过边权最大值的最小值。

发表于 2023-07-13 更新于 2023-07-29 分类于题解

设表示竞赛图中的强连通分量数量。计算所有下列条件的的之和：

答案对取模。

。

发表于 2023-07-13 分类于题解

你有个程序在同一棵调用树上，每个程序有所需内存大小和调用树上的父亲。

你需要把所有的程序放到内存里，可以把内存分段，对于大小为的段，它能放下所有所需内存大小不大于的程序。

现在要求对任何一个程序它不能和任何在调用树上与它有祖先关系的程序放到同一个段里。

求最小的总内存大小使得存在一种分段并放置所有程序的方式。

。