Loading...
Preface 随机跳题。 我现在真的暴怒。leetcode 这勾八 OJ 每组数据每次不会重新编译，而是会反复调用一个方法 😅。导致我的全局数组从来不清零。😅 题面 https://leetcode-cn.com/problems/longest-arithmetic-subsequence/ 题解 先推个朴素的方程。设 $f[i][d]$ 为以 $i$ 为结尾，以 $d$ 为公差的数列的...
Preface 随机跳题做到了这道。 题目 https://www.luogu.com.cn/problem/P2899 题解 其实就是交叉染色。我们考虑每棵子树的情况。设 $f[u]$ 表示以 $u$ 为根的最小答案。三种子情况： $f[u][0]$: $u$ 自己本身被染色 $f[u][1]$: $u$ 的某个儿子染色了，使之被覆盖进了范围 $f[u][2]$: $u$ 的父亲染色了，...
Preface Leetcode 随机 hard 题计划。来看看 hard 到底 hard 不 hard。反正好像是没看出 hard 来。 题目 https://leetcode-cn.com/problems/minimum-skips-to-arrive-at-meeting-on-time/ 题解 直接推方程。设 $f[i][j]$ 为前 $i$ 段路跳过 $j$ 个点的最少耗时乘上速...
题面 题目： https://oi.edu.pl/static/attachment/20110713/ceoi-2011.pdf http://ceoi.inf.elte.hu/tasks-archive/ 测试传送门： https://www.luogu.com.cn/problem/P4700 题解 首先分析复杂度，我们需要在 $O(n)$ 的时间内搞定。不难得出，暴力非常简单...
Preface BST 的问题 解决方案之一——Splay 右旋 (Zig)、左旋 (Zag) 如何判断是要左旋还是右旋？ Splay 操作【上旋 (旋转到根)】 代码层面的数据结构维护 一些辅助函数 旋转的代码实现 Splay 的代码实现 插入操作 两种查询寻 删除操作、寻找前继、寻找后继 代码 Reference Preface 昨天写了最普通的 BST，今天来写一下 Splay。注...
引言 二叉搜索树其实非常常用，但是......我好像从来没写过，一直用的 STL 的模板。为一手写过的二叉树可能就是堆了吧。趁着可靠大先辈学的时候稍微看了一下，大致理解了。（这么晚看这个真的该自裁） Reference 由于内容...十分基础，所以直接放链接了，我觉得写的比较好的教程： https://oi-wiki.org/ds/bst/ 模板题：洛谷 P5076 传送门: https...