浅析差分、树上差分的思路和实现

  • 昨日题目引发的思考,如何快速地处理“将树从 x到 y结点最短路径上所有节点的值都加上 z”的问题,发现通过树上差分的方法可以较为快速的解决该类问题,且由于近些年年赛多次涉及有关树上差分的知识,故在此浅析该问题的思路与实现。

  • 参考blog:https://www.cnblogs.com/ice-wing/p/7709311.html

继续阅读浅析差分、树上差分的思路和实现

BZOJ3631 [JLOI2014]松鼠的新家

BZOJ3631

树链剖分or树上差分 这里是树上差分的做法

考虑链上的差分,对于数组f,要对一段区间[a, b]区间+x,即f[a] += x, f[b + 1] -= x;

同理考虑树上差分,类似可得,对a到b路径上的所有点权+x,即f[a] += x, f[b] += x, f[lca(a, b)] -= x,  f[fa[lca(a, b)] -= x; 其中lca(a, b)为a, b的最近公共祖先,fa[x]为x的父节点。

最后只需dfs上传标记即可。 继续阅读BZOJ3631 [JLOI2014]松鼠的新家

Day7

【最长上升子序列】
题意:对一个序列进行操作,可以在序列最后加上一个数,可以回到k时的序列,求每次操作后序列的最长上升子序列长度。
【LIS求法】:通常求最长上升子序列都是n^2动规,当n较大时便要考虑nlogn的算法。
设f[k]表示长度为k的LIS最末尾的元素,易知f是单调递增的,对于新加入的x,如果f[k] < x, 意味着最长上升子序列的长度可以加1。如果f[k] > x,那么 对于f[i] > x > f[i - 1]考虑f第i位的值哪个更优?显然要取x。求i可以用二分优化,LIS便能在nlongn的时间内求出。
这题需要回到第k时的序列,由上述算法可知,对于操作j、j - 1,f数组的变化只有一个数,于是用可持久化线段树来维护这个数组,使修改和查询的时间变成logn, 时间复杂度是O(nlog^2n)。
由于时间复杂度和空间复杂度与题目要求十分相近,要考虑常数与每个结点的线段树子节点数量。
正解对于每个回到k序列的操作建一棵树,直接在这棵树上跑LIS,时间复杂度O(nlogn)。
【图的X匹配】
题意:对于一个多边形,使取出的边没有交点(即没有相邻的边)的方案数。
打表可以发现答案的规律类似斐波那契数列, 由于没有取模, 需要用高精度完成加法操作, n的值最大为10000, 最好用滚动数组。
证明:
【努力】
题意:使n个点形成一棵树的连边方法。
由prufer数列可得n个点的无向图有n^(n-2)种, n个点的树有n-1条边,答案便是n^(n-2)*(n-1)!。

代码如下:

继续阅读Day7

Day1:A+组

【元素】
题意:将n个整数分组,使组数最少且元素最多的组的元素个数尽量少。
数据范围给出提示,n<=15,符合这个范围的算法有深搜、状压DP。这里考虑深搜,枚举组数N,对于每一个数枚举其所在的组。时间复杂度为O(刚好能过)。
状压DP时间复杂度较为严谨,为O(2 ^ n * n ^ 2)。 令f[i]为状态i时最少需要的组数,对于两个状态opt、nav。若能合并,则f[opt ^ nav] = min(f[opt], f[nav])。若不能合并,则需讨论。

【反击】
题意:在n个数中找出最多满足条件的完美对数。
n <= 1000,可以暴力判断每两个数是否能符合条件,由于不能重复选取,联想到二分图。二分图求最大匹配方法有许多,这里使用网络流求二分图。将每个点拆成两点,每个点与另一边能与自己匹配的点连一条流量上限为1的边。源点s与一半的点连边,流量上限为正无穷。汇点t与另一半的点连边,流量上限为正无穷。
时间复杂度为O(nlogn).

【最小】
题意:将n点m边图中的点分为白点和黑点。 删除一些边,使剩下的边代价尽量小,且白点与最近的黑点仍按原先的最短路连接。
答案要求按最短路连接,于是先删除不在最短路上的边,再求最小生成树。最短路用spfa求解,由于有多个源点,先将所有黑点入队再求最短路。删边后只需满足白点与黑点由最短路连接,因此可能出现删边后成为森林的现象,在求最小生成树是将所有黑点先行合并。

主要代码如下

继续阅读Day1:A+组

树上点分治

这几天一直想完成之前的点分治,但都在写其他题,今天终于写完了点分治,怕忘,就写一下博客。

【引言】

由于树具有一般的图没有的特点,所以在竞赛中的应用更广。

在一些树上路径问题中,暴力求解时间复杂度过高,往往需要一些更为高效的算法,点分治就是其中之一。

【思想】

在树上,取一个点,对于询问计算所有经过这个点的情况,再递归下去处理每一棵子树的情况。因为是递归处理,为了使递归的次数更少,一般都是要取使以其为根,所有子树中节点最多的子树拥有的节点最少,称这个点为“重心”。

重心求法如下:

(1)任取一个根,dfs一次求出每个节点的子树大小。

(2)记录每一个点最大子树的节点数。

(3)最大子树的节点最少的点便是重心

代码如下:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
[cce_cpp]
void Getroot(int x, int fa)  {
    son[x] = 1;
    Max[x] = 0;
    int next;
    for (int i = last[x]; i ;i = e[i].last)
        if (!use[next = e[i].t] && next != fa)  {
            Getroot(next, x);
            son[x] += son[next];
            Max[x] = max(Max[x], son[next]);
        }
    Max[x] = max(Max[x], Son - son[x]);//因为这个点不一定是根,要计算它上的节点数,用树的大小减去(它的子节点数+1)即可
    if (Max[x] < Max[root]) root = x;
}
[/cce_cpp]

时间复杂度O(n)。

求出重心接下来就要解决问题了
(1)关于询问,以重心为根,求出所有经过当前重心的情况(即子节点1-->重心-->子节点2)。因为为了节省时间,是把所有子节点的情况一起算,如果两个子节点来自同一棵子树,那肯定是不行的,所以还要减去所以来自同一棵子树的子节点的情况。
(2)标记重心
(3)递归用相同的方法处理每一棵子树。
代码如下:


1
2
3
4
5
6
7
8
9
10
11
12
13
void sol(int x)  {
    root = 0;
    Getroot(x, 0);
    use[root] = 1;
    ans += Cal(root, 0);
    int next;
    for (int i = last[root]; i ;i = e[i].last)
        if (!use[next = e[i].t])  {
            ans -= Cal(next, e[i].val);
            Son = son[next];
            sol(next);
        }
}

点分治的思想基本上如上所述。

【例题】

继续阅读树上点分治

BZOJ2588 Spoj 10628. Count on a tree

BZOJ2588

求树上路径上节点权值k小。

可以发现树上两点u,v之间的第k小点权等价于(root <-> u) + (root <-> v) - (root <-> lca(u, v)) - (root <-> father[lca(u, v)])上的第k小点权,其中root为根节点,lca(u, v)为u和v的最近公共祖先,father[lca(u, v)]为lca(u, v)的父节点。

那么可以维护root到所有节点的权值,显然root到某个点x的权值和root到x父节点的权值只有点x这个点权的差别,那么可以用主席树维护这个东西了。

继续阅读BZOJ2588 Spoj 10628. Count on a tree