算法

DFS 众所周知,搜索和DP是不分家的,几乎所有的DP都可以转化为搜索。当想不出正解时,DFS也是骗分的好手段。 主要的搜索手段有: DFS/BFS爆搜 双向BF
0001-01-01
4分钟阅读时长
扩展欧几里得 求不定 $ax+by=c$ 的所有整数解。 判断该方程是否有解 裴蜀定理:设 $\gcd(a, b) = d$,则对任意整数x, y,有d|(ax + by) 成立; 特别地,一定存在x, y 满足ax +
0001-01-01
2分钟阅读时长
一、旋转(Zig - Zag) 1. 右旋(Right Rotation) 观察每个节点的变化,其中每个节点都有指向其父节点的指针没有画出。 ①②③处节点连接有变化。
0001-01-01
3分钟阅读时长
P1020 导弹拦截 #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; const int N = 100010; int n = 0; int a[N], b[N], s[N], ls[N]; void add(int x, int v) { for(; x<=n; x+=x&(-x)) s[x] = max(s[x], v); } int query(int x) { int ans = 0; for(; x>0; x-=x&(-x)) ans = max(ans, s[x]); return ans; } int main() { //freopen("p1020_1.in", "r", stdin); for(; scanf("%d", a+n+1) != EOF; ++n, b[n]
0001-01-01
5分钟阅读时长
简单数论 一点都不简单 欧几里得算法 又称辗转相除法 迭代求两数 gcd 的做法 由 $(a, b) = (a, ka + b)$ 的性质:$\gcd(a, b) = \gcd(b, a\bmod b)$ 容易证明这么做的复杂度是 $O(\log n)$ 注意:$
0001-01-01
3分钟阅读时长
网络流:Dijkstra 求费用流 注:下文中的边权 $w$ 均表示费用 $f$。 Dijkstra 不能求有负权边的最短路,所以我们可以对网络 $G$ 中的每一个点设置一个势函数 $h(u)
0001-01-01
2分钟阅读时长
网络流:最大流 EK 增广路方法是很多网络流算法的基础。其思路是每次找出一条从源到汇的能够增加流的路径,调整流值和残留网络 ,直到没有增广路为止。 EK 算法就是不
0001-01-01
3分钟阅读时长
网络流:最小割 将图 $G$ 分为 $A$ 和 $B$ 两个点集,$A$ 和 $B$ 之间的边的集合称为无向图的割集。带权图的割 (Cut) 就是割集中的边权之和。 S - T 最小割 特别地,对于一个网络,
0001-01-01
6分钟阅读时长
网络流:模板 P3376 网络最大流(Dinic) #include <stdio.h> #include <string.h> #include <iostream> #include <queue> using namespace std; const int N = 11000, M = 110000; const int INF = 0x7fffffff; struct node { int u, v, w, next; } e[M << 1]; int cur[N], h[N], tot; int dfn[N], ans, n, m, s, t; void add(int u, int v, int w) { e[tot]
0001-01-01
4分钟阅读时长
网络流:消圈算法 注:下文中的权均表示费用。 消圈定理 在某个流 $f$ 中,如果其残余网络中没有负圈(剩余流量为 $0$ 的边视为不存在),那它一定是当前流量下的最小费用
0001-01-01
3分钟阅读时长