A #include<bits/stdc++.h> using namespace std; #define ll long long #define uint unsigned long long #define PII pair<int,int> #define MP make_pair #define fi first…

贪心的基本思路是抹除后效性。 luogu9378 [THUPC 2023 决赛] 物理实验 尽可能保留编号小的实验一定是最优的。 考虑维护一个集合 $S$ 表示当前已经确定可以保留的实验集合，枚举实验 $i$ 尝试加入，这样原问题就转化为了 $n$ 轮判定问题。 考虑如何 check。由于确定了 $S$ 并且做 $S$ 以外的实验没有意义，所以我们…

树上差分 从抽象代数的角度讲，树上差分可以维护所有群上信息。 换句话说，满足结合律，存在「可减性」。 通过差分我们能将一个高纬问题以常数代价转化为低维问题，而问题低一维往往会简单非常多 —— lxl 太 $\textit{Trivial}$ 的我们就不提了。 下文成「前缀」为根到节点的路径。 luogu8201 [yLOI2021] 生活在树上（h…

并查集是一个森林，每棵树表示一个集合，并且这个集合根据某种具有传递性的关系构建起来。 普通并查集关心的信息只有 $x$ 所在集合的根，$fa_x$ 表示的仅仅是一个传递性关系，即 $fa_x$ 与 $x$ 所在集合的根相同。从任意节点往上跳，都能找到它所在集合的根。 使用路径压缩优化，在向上访问节点时，把路径上所有节点的 $fa$ 都改为根，那么就…

多项式哈希 把元素看作数字，把哈希对象看作关于 $P$ 的多项式，得到多项式哈希，亦称为进制哈希。 主要用于有序对象的哈希。 一般使用unsigned long long自然溢出，相当于对 $2^{64}$ 取模。 关于 $P$ 的选取，尽量避免常用的大质数。下文统一使用1610612741，其在 $[2^{30},2^{31}]$ 中。 void…

Trie luogu2922 [USACO08DEC]Secret Message G 给定两个字符串序列 $a$ 与 $b$，对于 $b$ 中每个字符串 $t$，求 $a$ 中有多少个字符串 $s$，满足以下两个条件之一 $s$ 是 $t$ 的前缀。 $t$ 是 $s$ 的前缀。 两个字符串序列中所有字符串长度之和不超过 $500000$。 把 …