【笔记/模板】无向图的双连通分量
边双连通分量
定义
在一张联通的无向图中,对于任意两点 uuu 和 vvv,删去两点之间任意一条边,都无法使其不连通(即连通数不变),我们就说这两点是边双连通。
对于一个无向图中的 极大 边双连通的子图,我们称这个子图为一个 边双连通分量。
根据 【笔记 / 模板】割点和桥 中可知,如果一张图是一个边双连通分量,那么这张图中必然不存在桥(割边),我们可以使用 Tarjan 求解割边的方法得到一张图的所有边双连通分量。
解法一
先用 Tarjan 预处理出图中所有的桥,再用 DFS 跑一边即可。
12345678910111213141516171819202122232425262728293031int id[N], dcc_cnt;vector<vector<int>> vec;void tarjan(int ver, int edge){ dfn[ver] = low[ver] = ++ timestamp; for (int i = h[ver]; ~i; i = ne[i]) { int to ...
【笔记/模板】割点和桥
割点
对于一张无向图 G=(V,E)G=(V,E)G=(V,E),使得 H 是 G 的连通子图,且不存在 FFF 满足 H⊊F∈GH \subsetneq F \in GH⊊F∈G 且 FFF 为连通图,则称 HHH 是 GGG 的一个连通块/连通分量(connected component),又叫极大连通子图。
由此,我们可以对割点做出如下定义:
对于一个无向图,如果把一个点删除后这个图的极大连通分量数增加了,那么这个点就是这个图的割点(又称割顶)。
Tarjan
处理过程
与有向图的强连通分量相似,我们定义如下两个重要数组:
dfn[]:表示深度优先遍历图时节点 uuu 被遍历到的次序,即时间戳。
low[]:节点 uuu 在不通过父亲走过的路的情况下可以到达节点的最小时间戳。
根据割点的定义可知,如果一个节点 ververver 是割点,那么必然有一个处于其 DFS 序子树内的节点 tototo 使得:
lowto≥dfnverlow_{to} \ge dfn_{ver}
lowto≥dfnver
这个意思指的是无论如何走,tototo 都无法到达 ververver ...
【题解】[COCI2017-2018#4] Automobil
Description
给定一个 n×mn \times mn×m 的矩阵,一共 kkk 次操作,在相应的行或者列上乘上一个数,求这 kkk 次操作后的和,答案对 109+710^9 + 7109+7 取模。
这里给出一种复杂度仅为 O(k)O(k)O(k) 的做法。
Solution
我们令 rowirow_irowi 表示矩阵第 iii 行被乘上的系数,colicol_icoli 表示矩阵第 iii 列被乘上的系数,显然一开始均为 111。
根据题意不难发现,矩阵中的权值 Ai,jA_{i, j}Ai,j 最后的值将为这一行被乘的总积再乘上这一列被乘的总积。由此可以得出答案:
ans=∑i=1n∑j=1mAi,j×rowi×colj\begin{align*}
ans &= \sum_{i = 1}^{n}\sum_{j = 1}^{m} A_{i, j} \times row_i \times col_j
\end{align*}
ans=i=1∑nj=1∑mAi,j×rowi×colj
由于 Ai,jA_{i, j}Ai,j 的初值与其位置有关, ...
【笔记/模板】树链剖分
树链剖分
树链剖分的基本思想
通过将树分割成链的形式,从而把树形变为线性结构,减少处理难度。
树链剖分(树剖/链剖)有多种形式,如 重链剖分,长链剖分 和用于 Link/cut Tree 的剖分(有时被称作「实链剖分」),大多数情况下(没有特别说明时),「树链剖分」都指「重链剖分」。
树链有如下几个特征:
一棵树上的任意一条链的长度不超过 log2n\log_2 nlog2n,且一条链上的各个节点深度互不相同(相对于根节点而言)。
通过特殊的遍历方式,树链剖分可以保证一条链上的 DFS 序连续,从而更加方便地使用线段树或树状数组维护树上的区间信息。
重链剖分
重链剖分的基本定义
重链剖分,顾名思义,是一种通过子节点大小进行剖分的形式,我们给出以下定义:
重子节点:一个非叶子节点中子树最大的子节点,如果存在多个则取其一。
轻子节点:除了重子节点以外的所有子节点。
重边:连接任意两个重儿子的边。
轻边:除了重边的其他所有树边。
重链:若干条重边首尾相连而成的一条链。
我们将落单的叶子节点本身看做重子节点,不难发现,整棵树就被剖分成了一条条重链。
需要注意 ...
【题解】CF1983C Have Your Cake and Eat It Too
这里是一份不怎么优雅的暴力模拟。
Solution
由于只有三个人参与了分配,通过排列原理可知可能的顺序有 3!3!3! 种可能,通过定义函数对每种可能模拟即可,一旦合法输出相应方案。
AC Code
123456789101112131415161718void solve(){ sum = 0, aver = 0; // 记录总数和平均值 cin >> n; for (int i = 1; i <= 3; i ++) for (int j = 1; j <= n; j ++) cin >> f[i][j]; // 使用二维数组方便后面的函数分讨 for (int i = 1; i <= n; i ++) sum += f[1][i]; aver = (sum + 2) / 3; for (int a = 1; a <= 3; a ++) for (int b = 1; b <= 3; b ++) f ...
【题解】CF1985G D-Function
Before
由于数的位数很大,我们用 ∑i=0nai×10i{\textstyle \sum_{i = 0}^{n} a_i \times 10^i}∑i=0nai×10i 来表示一个 n+1n + 1n+1 位的数,那么 D(num)=∑i=0naiD(num) = {\textstyle \sum_{i = 0}^{n} a_i}D(num)=∑i=0nai 就是这个数的数位之和。
Solution
敲份暴力代码不难发现以下结论:
对于任意的 num∈[10l,10r)num \in \left [ 10^l, 10^r \right )num∈[10l,10r),当且仅当 num×knum \times knum×k 的任意一位上没有发生进位,满足 D(k×num)=k×D(num)D(k \times num) = k \times D(num)D(k×num)=k×D(num)。
证明:因为 D(num)=∑i=0naiD(num) = {\textstyle \sum_{i = 0}^{n} a_i}D(num)=∑i=0nai,k×D(num)=∑i= ...
【题解】CF1322B Present
Statement
给定一个长度为 nnn 的数列 aaa,求
⊕i=1n⊕j=i+1n(ai+aj)\oplus_{i = 1}^{n} \oplus_{j = i + 1}^{n} (a_i + a_j)
⊕i=1n⊕j=i+1n(ai+aj)
其中 1≤n≤4×1051 \le n \le 4 \times 10^51≤n≤4×105,∀i,1≤i≤n,1≤ai≤107\forall i,1 \le i \le n,1 \le a_i \le 10^7∀i,1≤i≤n,1≤ai≤107。
Solution
简单的双重暴力显然是会超时的,问题的关键在于如何将两重循环减少一层。
对于异或等位运算操作,其特殊的性质在于按位运算,即每一位的影响不会改变下一层。
因此不难想到将答案二进制后的每一位进行讨论,最后统计答案。
对于第 kkk 位:
讨论两个数之和的二进制表示在第 kkk 位上是否为 111,根据加法的性质,我们只需要得知这两个数的前 kkk 位是多少。
定义数组 bbb,对于 ∀bi\forall b_i∀bi,都有 bi←ai∧(2k+1−1)b_i \ge ...
【题解】CF1972B Coin Games
Solution
一道博弈题,从操作的性质方面入手。
对于依次操作的位置,受到影响的就是其两边的硬币,无非分为以下几种情况:
两边都是 U,删去元素后两边都变成 D,U 的个数少了 333个(包括操作的那一个)。
一边是 U,一边是 D,操作后 U 的个数少了 111 个。
两边都是 D,操作后 U 的个数增加了 111 个。
不难发现无论怎么操作,U 的个数的奇偶性始终不会改变。对于最后一种操作,如果 U 的个数便为 000,那么游戏结束。
我们可以统计出初始状态 U 的个数,如果 U 为奇数,则 Alice 获胜,否则 Bob 获胜。
AC Code
12345678void solve(){ int res = 0; cin >> n >> s + 1; for (int i = 1; i <= n; i ++) res += s[i] == 'U'; cout <<( (res & 1) ? "YES\n" : "NO\n&qu ...
【题解】P10412 钟声远带斜阳
题目大意
给定一个长度为 nnn 的序列 aaa,花费不同代价进行一下若干操作:
选择其中一个元素 aia_iai(0≤i<n0 \le i \lt n0≤i<n) 增加一,花费 ppp 的代价。
选择其中一个元素 aia_iai(0≤i<n0 \le i \lt n0≤i<n) 删除,花费 qqq 的代价(序列长度不可为 000)。
选择其中两个元素 ai,aja_i,a_jai,aj(0≤i<j<n0 \le i \lt j \lt n0≤i<j<n)进行交换,花费 rrr 的代价。
最小化代价,使得 ∃k0(0≤k0<n)\exists k_0(0 \le k_0 \lt n)∃k0(0≤k0<n),将子序列 a0∼ak0−1a_0 \sim a_{k_0 - 1}a0∼ak0−1 拼接在原序列后端,当前序列任意前缀和非负。
Solution
定义 sumsumsum 表示整个序列元素之和,不难看出,对于任意一个序列,若 sum≥0sum \ge 0sum≥0,必然至少存在一个 k0k_0k0 使 ...
【笔记/模板】Tarjan 算法与有向图的强连通分量
有向图的强连通分量
定义
对于一张有向图 G=(V,E)G = (V, E)G=(V,E),对于两点 u,v∈Vu,v \in Vu,v∈V,都存在一条路径可以使得 uuu 达到 vvv,vvv 也可以达到 uuu,则称该两个点是互相可达的。
如果一张有向图上的任意两个节点之间可以互相可达,则称这张图是 强连通的(Strongly Connected)。
对于一张子图 H∈GH \in GH∈G,并且不存在其他的连通图 FFF 使得 H∉F∈GH \notin F \in GH∈/F∈G,则称子图 HHH 是有向图 GGG 的一个 强连通分量(Strongly Connected Component,SCC),叫做极大的连通分量。
应用
对于一个较为复杂的图论问题中,利用强连通分量的缩点技巧,将每一个强连通分量中的所有点看作一个点,最终使得图转化为 有向无环图(DAG),大大的减少了时间复杂度和解题难度。
Tarjan 算法
DFS 生成树
对于一张图的深度优先遍历,根据节点的先后遍历顺序,我们可以生成出一棵树,这棵树即为 DFS生成树,它的性质有如下几点:
深度优先遍历的第一个点 ...