1. 题目数据 (Problem Metadata) 题目类型：传统题 题目链接：Problem - 5C - Codeforces 时间限制：2 秒 内存限制：256 MB 2. 题意简述 (Problem Summary) 给定长度为 n...

背包问题是一类经典的可以使用动态规划解决的问题。先看以下几个动态规划基本模型： 0/1 背包问题 0/1 背包问题基本模型是：给定 nnn 个物品，每个物品有一个价值和一个体积，分别记作 wiw_iwi​ 和 viv_ivi​，给定一个容量为 mm...

线段树（一） 线段树是一种维护区间信息常用的树形数据结构。在全国青少年信息学奥林匹克竞赛大纲内难度评级为 6，是提高级中开始学习的数据结构。 本篇文章讨论的内容是线段树的基本结构与操作、线段树的延迟更新。 代码模板 代码模板-线段树 基本结构 ...

线段树用完全二叉树的数组存储，节点 p 的左右儿子为 p<<1 和 p<<1|1，开 4 倍空间。每个节点维护一个区间的信息，建树/修改/查询都在 O(log⁡n)O(\log n)O(logn) 的一条树链上完成。 单点...

树状数组基于二进制拆分，用 c[i]c[i]c[i] 维护以 iii 结尾、长度为 lowbit(i)lowbit(i)lowbit(i) 的区间 [i−lowbit(i)+1, i][i-lowbit(i)+1,\,i][i−lowbit(i)+1...

并查集用森林维护集合归属，f[x] 记 x 的父亲，根节点的父亲是自身。两种优化：路径压缩（查询时把路径上的点直接挂到根，常用）与启发式合并（小树并大树，带权并查集中常用）。 基本并查集（路径压缩） 1234567891011121314cons...

动态规划可解问题的特点 如果一个问题可以通过动态规划求解，则这个问题一定（充分不必要）满足这两个特点： 最优子结构 动态规划可以解决的问题通常是求问题最优解的问题。且这种问题可被分割为多个子问题，子问题的解也是最优的。通过各个子问题的最优解可以逐...

1. 题目数据 (Problem Metadata) 题目类型：传统题 题目链接：https://www.luogu.com.cn/problem/P1048 时间限制：1.00s 内存限制：125.00MB 2. 题意简述 (Problem...

1. 题目数据 (Problem Metadata) 题目类型：传统题 题目链接：P2678 [NOIP 2015 提高组] 跳石头 - 洛谷 时间限制：1.00s 内存限制：128.00MB 2. 题意简述 (Problem Summary...

适用范围 两段性：在某个区间内，存在一个分界点，使得分界点一侧满足某性质，另一侧不满足 二分算法适用于具有“两段性”特征的问题，只要有高效的检验性质的方法，就可以在对数复杂度时间内求出分段点的位置。最基础的二分查找有对应 STL 的实现，根据处...