传送门 题目理解与强调 给定一个有向图，共有 $n$ 个点和 $m$ 条边，存在自环的情况，每条边的长度都为 $1$ 。与一般题目不同的是，每走一步会走过 $2^k$ 个单位长度（ $k$ 为任意自然数），我们要找的是从点 $1$ 到点 $n$ 中所有路径中需要步数最少的一条。 题解 排除错误算法 第一个想到的方法一定是找到从 $1$ 到 $n$ …

倍增简介 倍增，顾名思义就是成倍总价。若问题状态的空间特别大，则一步步地推的算法复杂度太高，可以通过倍增的思想，只考察2的整数次幂的位置，快速缩小求解范围，直到找到解。 倍增原理 任意整数可以被表示成若干个$2$的次幂项之和。例如整数$5$，其二进制表示为$(101)_2$，该二进制数从右往左第$0$、$2$位均为$1$，则$5=2^2+2^0$；…

ST表简介 主要作用 ST 表是用于解决 可重复贡献问题 的数据结构。 可重复贡献问题：是指对于运算$ opt $，满足$ x $ $ opt $ $ x $ = $ x $，则对应的区间询问就是一个可重复贡献问题。例如，最大值有$ max(x,x) $，gcd有$ \gcd(x,x)=x $，所以RMQ和区间GCD就是一个可重…