金晖のBlog

拓扑排序例题： 模板题1：P4017 传送 题意： 给你一个食物网，你要求出这个食物网中最大食物链的数量。 （这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。） Delia 非常急，所以你只有 111 秒的时间。 由于这个结果可能过大，你只需要输出总数模上 801120028011200280112002 的结果。 输入： 第一行，两个正整数 n,mn,mn,m，表示生物种类 nnn 和吃与被吃的关系数 mmm 。 接下来 mmm 行，每行两个正整数，表示被吃的生物A和吃A的生物B。 输出： 一行一个整数，为最大食物链数量模上 801120028011200280112002 的结果。 思路： 记录下所有入度数为0的节点，将他们的初始状态 dp[i]dp[i]dp[i] 定义为1.之后对于 xxx 的所有后继节点 yyy 定义出度数为0的节点个数为m。 状态转移方程为：dp[y]=max(dp[x]+1,dp[y])dp[y]=max(dp[x]+1,dp[y])dp[y]=max(dp[x]+1,dp[y] ...

带权并查集的一些拙见 路径压缩 这是一个普通的并查集。如果我们对 CCC 执行find操作，最终会得到 AAA ，但是过程中会经过B。如果C的父亲特别多，这步就会消耗相当的时间，我们可以让 CCC 直接指向 AAA ，省去中间的操作进行优化，下图就是希望得到的结果 操作方法就是 将每个节点直接与其find操作最终得到的节点连接一条边 。在 findfindfind 方法中实现 12345678int findx(int x){ if(x!=f[x]) { f[x]=findx(f[x]); } return f[x];} 带权并查集 这就是基于路径压缩的带权并查集的样子。可以看到，在普通并查集的基础上，带权并查集在边中添加了一些额外的信息可以更好的处理问题。在 边上记录额外的信息 的并查集就是 带权并查集 每一条边都记录了节点到根节点的一个权值。基于路径压缩就会产生两个问题： 我们希望得到的是 节点与根节点 的权值。但是在路径压缩之前，每个节点都是与 父节点 连接的，这个权值自然也是和其 父节点 ...

玄学优化&其他算法 个人用到的一些优化/调试技巧，和一些杂七杂八的算法 玄学启发 指数级别, dfs+剪枝，状态压缩dp n≤100→O(n3)n≤100 \rightarrow O(n^3)n≤100→O(n3)，floyd，dp，高斯消元 n≤1000→O(n2),O(n2logn)n≤1000 \rightarrow O(n^2), O(n^2logn)n≤1000→O(n2),O(n2logn)，dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford n≤10000→O(n×n)n\leq 10000 \rightarrow O(n\times \sqrt{n})n≤10000→O(n×n​) ，块状链表、分块、莫队 n≤100000→O(nlogn)n\leq 100000 \rightarrow O(nlogn)n≤100000→O(nlogn)，各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap， prim+heap、spfa、求凸包 ...

图论模板 包括了一些简单的图论内容,不含网络流 树与图的存储 邻接矩阵：mp[a][b]mp[a][b]mp[a][b] 存储边 a→ba \rightarrow ba→b 邻接表： 123456789101112int head[MAXN];//表头int tot;//边的总数struct EDGE { int to, next, val;}edge[MAXM];void add_edge(int from,int to,int val) { //添加一条边 edge[++tot].to = to; edge[tot].val = val; edge[tot].next = head[from]; head[from] = tot;} //初始化tot = 0;memset(head, 0, sizeof head); 树与图的遍历 时间复杂度 O(n+m)O(n+m)O(n+m) nnn 表示点数 ，mmm 表示边数 深度优先遍历： 12345678int vis[MAXN];//标记某个点有没有被遍历过void ...

搜索模板 基本包括了DFS和BFS的所有类型 BFS 常用于求最小值 基于迭代，相较于 DFSDFSDFS 不容易爆栈。 Flood Fill 模型 顾名思义洪水覆盖问题。 可以在 线性 时间复杂度内找到矩阵内某个点所在的连通块。 可以维护所有矩阵内连通块的个数 123456789101112131415161718192021222324252627282930313233343536373839typedef pair<int, int> pii;int n, m; //矩阵的长和宽int vis[MAXN][MAXN]; //标记每个点属于哪一个连通块，0表示还问访问过int mp[MAXN][MAXN]; //每个点的权值int dx[4] = {0, 0, -1, 1};int dy[4] = {-1, 1, 0, 0};int cnt = 0; //连通块个数int size[MAXN]; //连通块内部元素个数void bfs(int x, int y) { que ...

数学提高 此部分由我前队友完成。浏览体验可能会有所不同因为水平比我强 有些地方无法正常浏览，可能是因为我队友有些用的LateX语法，markdown渲染不出来 常用数学技巧和公式 1. 常用公式 完全立方公式 (a+b)3=a3+3a2b+3ab2+b3=a3+b3+3ab(a+b)(a+b)^3=a^3+3a^2b+3ab^2+b^3=a^3+b^3+3ab(a+b)(a+b)3=a3+3a2b+3ab2+b3=a3+b3+3ab(a+b) a3+b3=(a+b)3−3ab(a+b)=(a+b)(a2+b2−ab)a^3+b^3=(a+b)^3-3ab(a+b)=(a+b)(a^2+b^2-ab)a3+b3=(a+b)3−3ab(a+b)=(a+b)(a2+b2−ab) (a−b)3=a3−3a2b+3ab2−b3=a3−b3+3ab(b−a)(a-b)^3=a^3-3a^2b+3ab^2-b^3=a^3-b^3+3ab(b-a)(a−b)3=a3−3a2b+3ab2−b3=a3−b3+3ab(b−a) a3−b3=(a−b)3+3ab(a−b)=(a−b)(a2+b2+a ...

数学基础 此部分由我前队友完成。浏览体验可能会有所不同因为水平比我强 有些地方无法正常浏览，可能是因为我队友有些用的LateX语法，markdown渲染不出来 组合数 1. 求组合数 根据不同的数据范围，求组合数也可以运用不同的方法。总的式子： Cab=a!b!(a−b)!C_a^b=\frac{a!}{b!(a-b)!}Cab​=b!(a−b)!a!​ 表示从aaa个物品中选出bbb个的方案数。 (1) 递推法 使用递推式Cab=Ca−1b+Ca−1b−1C_a^b=C_{a-1}^b+C_{a-1}^{b-1}Cab​=Ca−1b​+Ca−1b−1​ 证明：考虑已经得知了Ca−1k,k∈[0,b]C_{a-1}^k,k\in[0,b]Ca−1k​,k∈[0,b]的结果，那么当前有aaa个物品时，第aaa个物品要么被选，要么不被选中。若被选中，则方案一共有Ca−1b−1C_{a-1}^{b-1}Ca−1b−1​个，若不被选中，则方案有Ca−1bC_{a-1}^bCa−1b​个，方案累加，得证。 时间复杂度O(n2)O(n^2)O(n2) 12345678910void in ...

数据结构模板 包含了ACM里面常用的基本数据结构 链表 单链表 1234567891011121314151617181920212223242526272829303132333435// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点// MAXN表示最大点数int head = 0, e[MAXN], ne[MAXN], idx;void init() { //初始化链表 idx = 0, head = 0;}void insert(int val) { // 在链表头部插入一个数val e[++ idx] = val, ne[idx] = head, head = idx;}void insert_after(int k, int val) { // 在下标为k的节点后插入一个数val e[++idx] = val; ne[idx] = ne[k]; ne[k] = idx;}void remove_head() ...

计算几何模板 此部分由我前队友完成。浏览体验可能会有所不同因为水平比我强 有些地方无法正常浏览，可能是因为我队友有些用的LateX语法，markdown渲染不出来 基础模板及常用小函数 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#define Vector Point#define PI acos(-1)/*判断double x 的正负 1:正 0:0 -1:负*/int sgn(double x){ if (fabs(x) < ZERO) return 0; else if (x > 0) return 1; else return -1;}/** 封装点 重载 + - * / < == 运算符*/struct Point{ double x, y; Point(d ...

动态规划模板 包含了ACM一些常用的动态规划模型 思维导图： 数字三角形模型 每次只能向下走或者向右走。从起点走到终点。 题目给定一个 n×nn \times nn×n 的矩阵，矩阵中的每个格子上有一个价值为 www 的物品。给定起点 (1,1)(1,1)(1,1) 和终点 (n,n)(n, n)(n,n) ，规定只能向下或者向右走。从起点出发两次，但同一个格子在两次路径中都经过的话，他的物品价值只会被累加一次。问两次路线，途径格子的物品的总价值最大是多少。 注意到每次走一步，横纵坐标的和都会加1.且知道横坐标，纵坐标，和两个坐标的和的任意两个就能知道另外一个。这就启示我们可以状态压缩。 另外两次行动可以看成一起同步行动。通过这样的想法就定义出 dp[i][j][k]dp[i][j][k]dp[i][j][k] 表示 aaa 路线当前横坐标为 iii ，bbb 路线当前横坐标为 jjj ，横纵坐标和为 kkk 时的最大总价值。 状态只能由 dp[i−1][j][k−1],dp[i][j−1][k−1],dp[i][j][k−1],dp[i−1][j−1][k−1]dp[i - ...