「洛谷 P4341」锯木厂选址 - 斜率优化 DP
题意描述
从山顶上到山底下沿着一条直线种植了 \(n\) 棵老树。当地的政府决定把他们砍下来。为了不浪费任何一棵木材，树被砍倒后要运送到锯木厂。
木材只能朝山下运。山脚下有一个锯木厂。另外两个锯木厂将新修建在山路上。你必须决定在哪里修建这两个锯木厂，使得运输的费用总和最小。假定运输每公斤木材每米需要一分钱。
你的任务是编写一个程序，从输入文件中读入树的个数和他们的重量与位置，计算最小运输费用。
数据范围：\(n \le 20000\)。
0%
「Codeforces 1747D」Yet Another Problem - 构造 + 二分
题意描述
你有一个长度为 \(n (1 \le n \le 2 \times 10^5)\) 的整数序列 \(a\)。
你需要回答 \(q (1 \le q \le 2 \times 10^5)\) 个独立的问题，每次询问如下：
给定 \(l\) 和 \(r\)，你可以对序列做若干次操作（也可以不做），每次操作，你需要选择两个数 \(L\) 与 \(R\)，其中必须满足 \(l\le L\le R\le r\) 且 \(R-L+1\) 为奇数。然后将 \(a_L\sim a_R\) 的所有数改为 \(a_L\sim a_R\) 的异或和，即 \(a_L\oplus a_{L+1}\oplus \sim \oplus a_R\)。
你的目标是将 \(a_l\sim a_r\) 的所有数变为 \(0\)。每次询问完后，序列复原。
询问的答案即为最小操作数。如果总是不能达到目标，则答案为 \(-1\)。
「Codeforces 808G」Anthem of Berland - KMP + DP
题意描述
给定 \(s\) 串和 \(t\) 串，其中 \(s\) 串包含小写字母和问号，\(t\) 串只包含小写字母。
假设共有 \(k\) 个问号。
你需要给把每个问号变成一个小写字母，共有 \(26^k\) 种可能。
对于每种可能，设 \(t\) 匹配 \(s\) 的次数为 \(f_i\)，请输出 \(\max(f_i)\) 。
\(1\leq |s|,|t|\leq 10^5,|s|\cdot |t|\leq 10^7\)
Splay 学习笔记
一文概括 Splay
长文预警
平衡树
Splay 是一种平衡树，可以解决很多序列问题。而平衡树是一种二叉搜索树。
二叉搜索树则是一种数据结构，对于每一个节点，权值满足左儿子小于根节点小于右儿子，且整棵树的中序遍历是排序后的序列。这样二叉搜索树就可以解决很多问题，其时间复杂度取决于树的深度。
于是这里可以引出一种调试平衡树的常见方法：输出这棵树的中序遍历，看中序遍历是否为排序后序列。
然而在特殊数据下，二叉搜索树很容易退化成一颗链，于是就有了一种优化版本：平衡树。平衡树可以让二叉搜索树随时变化，以求深度保持相对较小，即“平衡”。而 Splay 就是一种平衡树。
「POJ 3691」DNA repair - AC 自动机 + DP
题意描述
生物学家终于发明了修复 DNA 的技术，能够将包含各种遗传疾病的DNA片段进行修复。
为了简单起见，DNA 看作是一个由
A、G、C、T
构成的字符串。
修复技术就是通过改变字符串中的一些字符，从而消除字符串中包含的致病片段。
例如，我们可以通过改变两个字符，将 DNA 片段 AAGCAG 变为
AGGCAC，从而使得 DNA 片段中不再包含致病片段
AAG、AGC、CAG，以达到修复该DNA片段的目的。
需注意，被修复的 DNA 片段中，仍然只能包含字符
A、G、C、T。
请你帮助生物学家修复给定的 DNA 片段，并且修复过程中改变的字符数量要尽可能的少。
「NOI 2015」软件包管理器 - 树链剖分
题意描述
你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包 \(A\) 依赖软件包 \(B\)，那么安装软件包 \(A\) 以前，必须先安装软件包 \(B\)。同时，如果想要卸载软件包 \(B\)，则必须卸载软件包 \(A\)。现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除 \(0\) 号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而 \(0\) 号软件包不依赖任何一个软件包。依赖关系不存在环（若有 \(m \ (m \geq 2)\) 个软件包\(A_1, A_2, A_3, \ldots ,A_m\)，其中 \(A_1\) 依赖 \(A_2\)，\(A_2\) 依赖 \(A_3\)，\(A_3\) 依赖 \(A_4\)，……，\(A_{m−1}\) 依赖 \(A_m\)，而 \(A_m\) 依赖 \(A_1\)，则称这 \(m\) 个软件包的依赖关系构成环），当然也不会有一个软件包依赖自己。
现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为 \(0\)。
对于所有数据，\(n \leq 100000, \ q \leq 100000\)。
树链剖分学习笔记
树链剖分是一个很常见的处理树上问题的算法，但之前一直没学 /kk，现在终于把这个坑补了。
这里只讲了重链剖分，不涉及其他剖分方式。
概念
树链剖分是一种把树上问题转化为序列问题的算法。它可以将树上的一条路径所经过的点用序列中的若干条区间表示。
首先我们需要知道几个概念：重儿子、轻儿子、重边、轻边。我们定义对于一个节点 \(u\) 的儿子为 \(v\)，我们定义以 \(v\) 为根的子树中节点最多的子树所对应的 \(v\) 为重儿子，其余的 \(v\) 为轻儿子。父亲连向重儿子的边为重边，父亲连向轻儿子的边为轻边。如果同时有多个以 \(v\) 为根的子树节点数相同且最大，则选取任意一个 \(v\) 为重儿子，其余为轻儿子。这样对于每个非叶节点，我们都有一个重儿子和一个重边。