给出一棵基环树, 求树上简单路径条数
\(3 \leq n \leq 2 \cdot 10^5\)
将基环树看作一个环, 环上连接着一些树, 设第\(i\)棵树有\(cnt_i\)个节点.
路径分为两种情况:
通过一遍\(DFS\)求出环, 再通过一次\(DFS\)求出每个子树大小, 答案为 \[ \sum_{i \in subtree}\frac{cnt_i\cdot(cnt_i-1)}{2} + cnt_{i}\cdot(n - cnt_i) \] 复杂度\(O(n)\)
1 | //E |
给出一棵\(n\)个点的带权无根树, 给出三个点的集合. 在每个集合任取一点, 在树上寻找新的一个点使得该点到三点的路径和最短. 求路径和期望
$ 1 n ^5,1 w $
首先考虑这样一个问题: 给出树上三点\(a,b,c\), 求这三点汇聚到一点\(v\)的最短路径(设为\(f(a,b,c)\)) \[ f(a,b,c) = \min\{v\in V |dis(a,v) + dis(b,v) + dis(c,v)\} \]
如上图所示, \(a,b,c\)为\(3,4,5\). 观察易得汇合点\(v\)为\(2\), 即\(a,b,c\)的LCA中深度最深的那个. 此时\(a,b\space a,c \space b,c\)间的每条边都恰好经过一次, 即: \[ f(a,b,c) = \frac{1}{2}(dis(a,b) + dis(a,c) + dis(b,c)) \] 由期望的性质\(E(X + Y) = E(X) + E(Y)\), 我们可以分别计算两个集合\(j,k\)中各点的距离和. 通过一遍DFS来计算子树\(u\)中属于集合\(i\)的节点个数\(num[u][i]\), 再对每条边分别统计贡献\(g\). 设\(cnt_i\)为集合\(i\)的大小. \[ g(e_i,j,k) = ((cnt_i - num[u][j])*num[u][k] + (cnt_k - num[u][k])*cnt_j)*e_i.w \] 答案即为 \[ \sum_{j = 1}^3 \sum_{k = j+1}^3\frac{\sum_{i = 1}^{n-1}g(e_i,j,k)}{2\cdot cnt_j \cdot cnt_k} \]
1 | //C |
PS: 当时我这题题意转述的时候锅了, 导致队友直接一个点分治敲上去, 敲完才发现不对劲=-= 不然这题是有可能做出来的
给出一张无向带权图\(G\)和\(k\)个点对, 你可以将最多一条边的权值变为0, 求\(k\)个点对之间最短路之和的最小值
图中存在重边和自环.
\(1 \leq n \leq 1000, 1 \leq m \leq \frac{n(n-1)}{2},1 \leq k \leq 1000\)
套路题, 一开始想麻烦了.
设\(D[i][j]\)为\((i,j)\)间的最短路. 对于每条边\((f,t)\)有两种情况:
我们跑\(n\)遍Dijkstra预处理出任意点对最短路,再对于每条边枚举\(k\)个点对即可求出答案.总复杂度\(O(nm\log n + km)\)
1 | #include <bits/stdc++.h> |
给出一个长为\(n\)的数组\(\{a_i\}\), 用\(x\)异或数组中的每一个元素, 使得在新数组逆序对最少的情况下\(x\)最小.求满足题意的逆序对数和\(x\)
\(1 \le n \le 3 \cdot 10^5\)
异或让我们考虑0-1Trie.
对于每一个数, 按照从高位到低位的顺序插入Trie, 并对其经过的每个节点维护该数字的下标. 具体来说,idx[u]记录了经过节点\(u\)的数字的下标. 由于我们按下标递增的顺序插入元素, 该数组是有序的.
有了idx[]，再结合一个显然的事实: 两个数的大小只取决于其最高位, 我们就可高效计算每一位所影响的逆序对(0-1Trie中,左子树代表的值小于右子树).
具体做法: 从高位开始自上而下遍历整棵0-1Trie. 设当前节点为\(u\), 当\(u\)的两个子节点均存在时, 修改该位才能对逆序对数目产生影响. 利用前面维护的下标, 我们可以在线性时间内计算该位对逆序对数目的贡献.
1 | int ptr = 0;//右子树idx[]的游标 |
我们使用\(sum[][]\)来记录该结果.\(sum[i][0]\)表示不修改第\(i\)位所贡献的逆序对, \(sum[i][1]\)表示修改该位贡献的逆序对.容易看出修改该位后, 原本的逆序对变成了顺序对, 反之亦然.
1 | sum[dep][0] += inv; |
有了sum数组,答案便很容易统计:\(inv += \min(sum[i][0],sum[i][1])\). 而当\(sum[i][1] < sum[i][0]\)时, \(x\)的第\(i\)位为1.
1 | //E |
给出一张图, 图中有的边已确定方向(且不可更改), 另一些边尚未确定方向. 给所有未确定方向的边指定一个方向, 使得新的图不存在环. 如果无解输出NO
一张图的拓扑排序是一个DAG. 我们首先仅考虑原图的有向边, 如果其中存在环那么无解. 否则求原图的拓扑序, 按拓扑序指派边的方向即可.
1 |
|
给出一个数列\(\{a_i\}\),维护两种操作:
1 pos : 把\(a_{pos}\)加上\(10^7\)2 r k: 找到一个不小于\(k\)且不等于\(a_1,...,a_r\)的最小值\(x\)共有\(m\)组询问,强制在线.
\(1 \leq n,m \leq 10^5\),\(1 \leq a_i \leq n\). 保证\(1 \leq pos,r,k\leq n\)
建一棵权值线段树,每个点存储该数原来的位置.维护\(Set\)操作和\(minv\).
对于操作1,由限制易得等同于删除\(a_{pos}\).
对于操作2,我们搜索权值线段树里\([k,n]\)中大于\(r\)的第一个最小值,若不存在则答案为\(n+1\).
1 | //HDU6703 |
We will use lazy tag to solve this problem. Let \(upv[x]\) be the maximum bound of node \(x\), and \(lowv[x]\) be the minimum bound of node \(x\). As we only care about single point value, the leaf node's \(lowv[]\) is the answer. Now the problem is how to maintain those two arrays. Now we assume we are operating on node \(x\), and the value of operation is \(h\).
Part 1: Adding phase
In this part we maintain \(lowv[x]\). If \(lowv[x] < h\) or there's no operation on \(x\), let \(lowv[x] = h\).
Part 2: Removing phase
We maintain \(upv[x]\) just like part one. If \(upv[x] > h\),let \(upv[x] = h\). Notice if \(lowv[x] > h\), let \(lowv[x] = h\).
Part 3: Pushdown.
Just apply Part 1 and 2 on child nodes(\(y\)). If node's \(lowv[y]\) greater than \(upv[x]\), cut it off and vice versa.
1 | //P-4-E |
https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/E
或:
https://www.luogu.com.cn/problem/P4560
长度为\(n\)的序列初始为空,维护两种操作:
给出\(m\)个操作,输出操作全部完成后的序列.
\(1 \leq n \leq 2\cdot10^6,1 \leq m \leq 5\cdot10^5\)
对每个节点维护\(upv[]\)和\(lowv[]\),表示该节点值的上限和下限.查询时对每个点做一次单点查询,答案为\(lowv[x]\).
下放节点时\(upv\)和\(lowv\)的关系比较显然,细节请见代码.
dlstxdy!
杜教筛用于快速求数论函数的前缀和.当预处理了小于\(n^\frac{2}{3}\)的前缀和时,杜教筛的时间复杂度为\(O(n^\frac{2}{3})\)
给出数论函数\(f\),快速求\(S(n) = \sum_{i = 1}^nf(i)\)
引理: \[ \sum_{i = 1}^n f \ast g (i) = \sum_{i = 1}^ng(i) \cdot S(\lfloor \frac{n}{i} \rfloor) \] 证明: $$ \[\begin{align} &\sum_{i = 1}^n f \ast g (i) \\ &= \sum_{i = 1}^n \sum_{d|n}f(d)\cdot g(\frac{n}{d})\\ &= \sum_{d = 1}^ng(d)\sum_{i*d = 1,d|i}^{i*d <= n}f(\frac{i}{d})\\ &= \sum_{d = 1}^ng(d)\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}f(i)\\ &= \sum_{d = 1}^ng(d)\cdot S(\lfloor \frac{n}{d} \rfloor) \end{align}\] \[ 观察上式,我们能得到: \] \[\begin{align} &g(1) \cdot S(n) \\ &= \sum_{i = 1}^ng(i) \cdot S(\lfloor \frac{n}{i} \rfloor) -\sum_{i = 2}^ng(i) \cdot S(\lfloor \frac{n}{i} \rfloor)\\ &= \sum_{i = 1}^n f \ast g(i) - \sum_{i = 2}^ng(i) \cdot S(\lfloor \frac{n}{i} \rfloor)\\ \end{align}\] $$ 这个式子的后半部分可以用数论分块递归去求,如果我们构造的\(g\)能快速求出\(\sum_{i = 1}^nf\ast g(i)\),我们就能快速求出\(g(1)\cdot S(n)\).
我们知道\(\mu \ast 1 = \epsilon\)
因而有: \[ \begin{align} &1\cdot S(n) = S(n)\\ &= \sum_{i = 1}^n\mu \ast 1(i) - \sum_{i = 2}^n 1 \cdot S(\lfloor \frac{n}{i}\rfloor)\\ &= \sum_{i = 1}^n \epsilon - \sum_{i = 2}^n S(\lfloor \frac{n}{i}\rfloor)\\ &= 1 - \sum_{i = 2}^n S(\lfloor \frac{n}{i}\rfloor)\\ \end{align} \] 简单地把\(\mu \ast 1 = \epsilon\)带进上面的结论就行了.
代码:
(Mu为map,记忆化求过的μ.求之前先线性筛一遍小于maxn的μ.下面求φ同理)
注意\(g = 1\),减的时候别漏了(\(r-l+1\))=-=
1 | ll du_mu(int x){ |
和μ大同小异.我们有\(\varphi \ast 1 = id\),其中\(id(n) = n\) \[ \begin{align} &1\cdot S(n) = S(n)\\ &= \sum_{i = 1}^n\varphi \ast 1(i) - \sum_{i = 2}^n 1 \cdot S(\lfloor \frac{n}{i}\rfloor)\\ &= \sum_{i = 1}^n id(i) - \sum_{i = 2}^n S(\lfloor \frac{n}{i}\rfloor)\\ &= \frac{n*(n+1)}{2} - \sum_{i = 2}^n S(\lfloor \frac{n}{i}\rfloor)\\ \end{align} \] 代码:
1 | ll du_phi(int x){ |
**本文思路部分来自于这篇题解*:凄魉 题解 P2257 【YY的GCD】
多组数据,求 \[ \sum_{i = 1}^n\sum_{j = 1}^m [\gcd(i,j) == k],k \in prime \]
\(T = 10^4,1 \leq n,m \leq 10^7\)
首先我们在求 \[ \sum_{i = 1}^n\sum_{j = 1}^m [\gcd(i,j) == 1] \]
时有这么一种做法,利用了莫比乌斯函数\(\mu\)的性质: \[ \sum_{d|n}\mu(d) = [n = 1] \]
\[ \begin{align} &\sum_{i=1}^{n}\sum_{i=1}^{m}[\gcd(i,j) == 1] \\ &=\sum_{i=1}^{n}\sum_{i=1}^{m}\epsilon(\gcd(i,j))\\ &=\sum_{i=1}^{n}\sum_{i=1}^{m}\sum_{d|gcd(i,j)}\mu(d)\\ &=\sum_{d = 1}^{\min(n,m)}\mu(d)\sum_{i = 1}^n[d|i]\sum_{j = 1}^{m}[d|j]\\ &=\sum_{d=1}^{\min(n,m)}\mu(d)\lfloor \frac{n}{d}\rfloor \lfloor \frac{m}{d} \rfloor \end{align} \] 那么我们只要构造一个数论函数\(f\),使得 \[ \sum_{d|n}f(d) = [n \in prime] \]
答案就变为了 \[ \sum_{d=1}^{\min(n,m)}f(d)\lfloor \frac{n}{d}\rfloor \lfloor \frac{m}{d} \rfloor \]
形式化地,设数论函数\(g\),构造\(f\)使得\(\sum_{d|n}f(d) = g(n)\)
如此,我们有: \[ \sum_{d|n}f(d) = \sum_{d|n,d \neq n}f(d) + f(n) = g(n) \] 第二步可以采用类似埃氏筛的方法,复杂度\(O(n\ln n)\)
1 | for(int i = 1;i < maxn;i++)f[i] = g[i]; |
对于本题,我们设\(g(n) = [n \in prine]\)即可,可以在\(O(n)\)时间内筛出\(g\).
总复杂度:\(O(n + n\ln n + T \sqrt{\min(n,m)})\)
1 | //P2257 |
PS.不是我不喜欢用行间公式,是hexo渲染行间LaTex总出奇怪的bug,凑合着看吧=-=
以下均有\(k \in prime\) \[ \begin{align} &\sum_{k = 1}^n\sum_{i = 1}^n\sum_{j = 1}^n[\gcd(i,j) == k]\\ &=\sum_{k = 1}^n\sum_{i = 1}^{\frac{n}{k}}\sum_{j = 1}^{\frac{m}{k}}[\gcd(i,j) == 1]\\ &=\sum_{k = 1}^n\sum_{i = 1}^{\frac{n}{k}}\sum_{j = 1}^{\frac{m}{k}}\sum_{d|\gcd(i,j)}\varphi(d)\\ &=\sum_{k = 1}^n\sum_{d = 1}^{\frac{n}{k}}\varphi(d)\cdot \lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor\\ &设T = kd,枚举T\\ &=\sum_{k = 1}^n\sum_{d=1}^{\frac{n}{k}}\varphi(d)\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\\ &=\sum_{T = 1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{k|T}\mu(\frac{T}{k}) \end{align} \] 可以看出\(f(T) = \sum_{k|T}\mu(\frac{T}{k})\)可以预处理
复杂度:不会
1 | for(int p:prime){ |
code:
1 | //P2257_2 |