图论习题

Created2020-12-03|Updated2026-01-20|算法图论

|Post Views:

拓扑排序

Directing Edges

此题很巧妙，先用拓扑排序排出来，再利用拓扑序构造解

Author: Fyind

Link: http://fyind.de/2020/12/03/%E5%9B%BE%E8%AE%BA%E4%B9%A0%E9%A2%98/

Copyright Notice: All articles on this blog are licensed under CC BY-NC-SA 4.0 unless otherwise stated.

算法图论习题题解

Related Articles

前缀和和差分 https://ac.nowcoder.com/acm/contest/19483 普通前缀和前缀和数组对于数组 \(A\) 的前缀和数组 \(s\) 是 \[ s[x]=\sum_{i=0}^{x}A[i] \] 递推公式 \[ s[x]=s[x-1]+A[x] \\ s[0]=0 \] 广义前缀和把求和看成某种操作的累加。维护dp矩阵 DP转移用矩阵表示，然后可以用前缀和维护求 \[ dp(l,r) = dp(1,r)-dp(1,l) \] 设初始列向量为 \(\textbf{v}\), 转移矩阵为 \(mat[i]\) 然后 \[ dp(l,r) = mat[r] \cdot mat[r-1] \cdot mat[r-2]...mat[l+1] \cdot \textbf{v} \] 所以我们维护一个左乘矩阵前缀和 \[ sum[i] = mat[i] \cdot mat[i-1] ... mat[2] \cdot mat[1]\\ sum[i]=mat[i] \cdot sum[i-1] \] 维护好之后计算的时候： \[ dp(l,r) = su...

基础知识求和符号 \[ \sum_{i=1}^{n}=a_1+a_2+a_3+...+a_n \] 求和符号的性质结合律 \[ \sum_{i=1}^{n} \sum_{j=1}^{n} a_i b_j = \sum_{j=1}^{n} \sum_{i=1}^{n} a_i b_j \] 分配率 \[ \sum_{i=1}^{n} a_i \cdot k = (\sum_{i=1}^{n}a_i) \cdot k= k\sum_{i=1}^{n}a_i \\ \sum_{i=1}^{n}\sum_{j=1}^{n}a_i b_j = \sum_{i=1}^n (a_i\sum_{j=1}^n b_j) = (\sum_{j=1}^{n}b_j)\cdot(\sum_{i=1}^{n}a_i) = (\sum_{i=1}^{n}a_i)\cdot(\sum_{j=1}^{n}b_j) \] 改变枚举对象令 \(z=x+y\) \[ \sum_{x=0}^a\sum_{y=0}^b f(x,y) = \sum_{z=0}^{a+b}\sum_{y=0}^zf(z-y,y) \...

AtCoder Grand Contest 047 AtCoder Grand Contest 047 A. Integer Product 给定 \(n\) 个浮点数，计算有多少个 \((i, j)\) 使得 \(A_{i} \cdot A_{j}\) 是整数 \(2\leq N \leq 200 \ 000\) , $ 0 < A_{i} ^{4}$ , \(A_{i}\) 最多 \(9\) 为小数. 思路通过题设条件缩小范围，枚举由于数据比较大，不能直接暴力做。判断是整数这个条件不太好集体维护。所以要找出题目中的特性，看看有没有机会让范围缩小。最好是可以先考虑 \(A_{i} \cdot A_{j}\) 什么情况下是整数。发现，对于任意有限小数 \(x\), 可以在乘上 \(10^{n}\) 后肯定会变成整数。所以每个数必然是 \(k\cdot 2^{m}\cdot 5^{n}\) 的形式, 通过乘 \(10^{n}\) 把分母上的 \(2^{m}\cdot 5^{n}\) 约去. 而之前的 \(k\) 不影响答案。所以我们只要考虑 \(2^{m}\cd...

三行写完高斯消元，这就是Python!!!

三行写完高斯消元，这就是Python!!! 洛谷评测链接先给大家看一眼核心代码核心代码 123for i in range(len(a)): row = [j for j in range(len(a)) if a[j][i] != 0 and sum(a[j][:i]) < 1e-8][0] a[:] = [r + a[row]*(-r[i]/a[row][i]) if j != row else r/a[row][i] for (j,r) in enumerate(a)] 没错，就只有三行，完成了高斯消元最核心的操作，把矩阵消元成主对角线为1，其余除了常数项全是0的形式。我只用了Python中的切片操作，列表解析式，还有numpy中array的性质。为了方便大家理解，我先来介绍一些这些python中的语法 python语法介绍切片语法格式是 [开始:结束] 可以取出列表中的一段区间,如果不填写就是默认开始位置是0，结束位置是列表最后一个元素位置。注意这里的区间是左闭右开区间。并且支持倒着数，也就是使用负号比如： 12345l = [0,2,3,4...

线段树线段树是一种用来维护区间性质的数据结构，此篇不讲解基础，而是讲解在算法竞赛中的应用。读者需要至少会写线段树懒标记维护区间求和操作。目前使用的模板我的懒标记的定义是：已经维护好了当前节点，但子节点还没维护好. 普通版本 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950const int maxn = 1e5 + 5;int n, m;typedef long long typec;#define lson (o<<1)#define rson (o<<1|1)#define mid ((l+r)>>1)#define len(x,y) ((y)-(x)+1)typec sumv[maxn*4], addv[maxn*4];typec A[maxn], qans, v;int ql, qr;void build(int o, int l, int r) { addv[o] = 0; ...

几何习题二分 ABC181F Silver Woods 题意有 \(n \le 100\) 个木桩在 \(-100\le y \le100\) 的范围里。你有一个圆，圆的半径你可以选择的。求可以把圆从最左边移动到最右边的最大半径。思路首先题目具有单调性：如果一个半径可以移动，那么更小的也可以。如果一个半径不能移动，那么更大的肯定不行。所以我们考虑二分。那给定一个 \(r\) 怎么检查呢。对于两个点\(x,y\)，如果 \(r\) 不能从他们之间通过，那么我们就将这两个点连起来。对于上下界\((y=\pm 100)\) 如果不能这个线和这个点之间穿过去，那么我们就连上他们。我们枚举把所有的点都连线完。如果存在一条由上界连向下界的边，那么这个半径就被 “拦住了”不能通过。如果没有就一定存在一条路径可以通过。所以我们用并查集连接就好了，最后检查一下上下界有没有连起来即可。代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455...