-
P9019 [USACO23JAN] Tractor Paths P
一个点跑到一个区间+两点最短距离，直接倍增一直跑就行了 找到每个点向左最远的区间 $f_{0,i}$，向右最优的区间 $g_{0,i}$ 直接大力倍增跑路 注意倍增跑路一定是 $\lt$ 不要取 $\leq$，最后再 +1 即可 考虑第二问，设第一问... -
Kru重构树
Kru 重构树 https://www.luogu.com.cn/blog/me-immortal/kruskal-chong-gou-shu https://www.luogu.com.cn/blog/mywd-ylyy/kruskal-zhon... -
Borůvka
?Borůvka $O(m\log n)$ 求 $MST$，一般用于求完全图 $Borůvka$ 其实是一种多路增广的 $prim$ $Prim$ 算法由一个点开始，往外不断贪心地找最短边，然后不断扩大连通块，直到形成一棵树 而 $Borůvka$ ... -
Hash
Hash 123456789101112131415ull get(int l,int r){ return h[r]-h[l-1]*p[r-l+1]; //这步其实是将h[l-1]左移} ... -
2-SAT
2-SAT ?SAT 给定变量 $x_1,x_2,…x_n$，$x_i=0/1$ 若 $x_i$ 为真则 $x_i=1$，否则 $\lnot x_i=1$ 给定约束条件 $x_i=1$，$x_i=0$ $x_i \oplus x_j \oplus x... -
ABC277 G
考虑暴力 $dp$，$f_{x,j,k}$ 当前在 $x$，移动了 $j$ 次，等级为 $k$ 的期望 考虑把 $k$ 融入 $dp$ 状态 我们考虑 $X_i^2 \to X_{i+1}^2$ 显然有 $E(X_{i+1})=E(X_{i}+A)=... -
P6148 [USACO20FEB] Swapity Swapity Swap S
$Sol1$ 考虑倍增，我们跑一次是 $O(nm)$ 的，直接倍增跑路即可 首先强行记录一次，记录每个点到了哪个位置，倍增转移一下即可 123456789101112131415161718192021222324252627282930313233... -
P2331 [SCOI2005] 最大子矩阵
$m=1$，序列最大的 $k$ 个字段和 1234567891011121314151617181920212223struct Solve1{ int s[N],f[N][12]; void init() { ... -
浅谈随机化
Here’s something encrypted, password is required to continue reading.
-
P8817 [CSP-S 2022] 假期计划
首先把 $k \operatorname{++}$， 转换成两点距离 考虑到枚举四个点不行，但是 $O(n^2)$ 可以，我们考虑枚举两个点，然后 $O(1)$ 找出剩下两个点 首先 $O(n^2)$ 预处理每个点 $d \leq k$ 之内的点，并...