/tag/data-structure
data-structure
4 篇文章带着 data-structure 这个标签。
CCF考试骗分指南
正经派 关于做题 首先，看到题目之后不要急着写代码，先在草稿纸上分析完整再开始写，如果思考后没有正解，先写暴力再进行优化 可以尝试手推样例看一下有没有特殊性质，如果手推太困难可以借助程序打表找规律 遇到复杂贪心、结论题直接猜结论，再和暴力对拍 记得开long long，分析数据范围开int128 多测记得输出换行和清空数据 关于时间分配(CSP-S) *J组随便AK 1h出T1(如果理想的话)…
[CSP-S 2019 T2] 括号树
[[CSP-S 2019 T2] 括号树](https://www.luogu.com.cn/problem/P5658) 题意 给定一颗 n 个节点的树，每个节点有一个括号 ( 或者 )，现在询问 i 节点到根节点这一条链上所有括号组成的括号序列有几个子括号序列合法 对题目进行分析 观察 1 定义 f(x) 为以 x 节点结尾的合法括号序列数，很容易想到 $[1,i]$…
算法之前缀和（一）
本文为手工编写，非AI生成，请放心食用 什么是前缀和 前缀和（Prefix Sum）是一个在算法和数据结构中非常基础且重要的预处理技巧 它通过预处理一段数据的 前缀 信息，高效且简单的维护 可差分 并且具有 结合律 数据类型的区间信息 什么是可差分? 可差分就是这种数据类型所求的运算是可逆的 例如加法就是典型的可差分运算，因为可以通过减...
单调栈
什么是单调栈 单调栈是一种数据结构，可以帮助我们在 $O(n)$ 的时间复杂度内找出 $ai$ 左/右第一个大于(等于)/小于(等于) $ai$ 的数。 那具体是如何实现的呢 通过实现一个栈存储待填答案的元素，当遍历到一个元素时： (1) 将栈中所有找到答案的值弹出，记录答案； (2) 然后当前元素成为待填答案的元素，压入栈。 我们发现在上一次执行 (1) 的时候...