Llf's blog

2018年4月

April 26, 2018

点分治总结

我自己感觉点分治是一种比较玄学神奇的算法,感觉自己也只是理解了一点皮毛而已。这里就谈谈点分治的实现方法和一些运用。 方法 点分治其实是将一棵树的点不断分为多棵子树,分别得到子树节点到子树根的距离来进行处理。 既然要有一个点为根节点,那么应该选取哪一个点呢? 既然要向下分治,如果把一个原来的叶节点作为分治的根节点,那么遍历每一个点的时间开销是非常大的。然而如果这个点的左右子树都达到最大,那么...
Llf in 题解
April 24, 2018

题解-洛谷P4092 [HEOI2016/TJOI2016]树

第一次写树剖没看题解A题,发现题解洛谷题解区大佬里竟然没有一个做法一样的,实在是太激动了 树剖学习:https://llf0703.com/p/shu-lian-pou-fen.html 题目链接 洛谷 P4092 BZOJ P4551 方法 裸树剖 ,直接用线段树维护每一段区间中被标记的最深的节点就行了。先全部赋值为-1,然后向上传递时直接取两段中的最大值即可(因为越深的点d...
April 21, 2018

二分图匹配

我是看这篇学懂的,真的写得很好,所以我就不在这里总结了,只发个模板 https://blog.csdn.net/dark_scope/article/details/8880547 模板题:洛谷 P3386【模板】二分图匹配 #include<bits/stdc++.h> using namespace std; bool edge[1005][1005]; bool used[...
Llf in 题解
April 19, 2018

题解-洛谷P2486 [SDOI2011]染色

题目链接: 洛谷 P2486 BZOJ P2243 方法 可以想到,颜色段的个数也是具有可加性的,但是如果两段连接处(即线段树中左子树的最右边的点和右子树的最左端的点)的颜色是相同的话,中间就只能算作一段,需要将颜色段个数-1。 所以我们在线段树里多加两个变量,分别为这一段最左端的点颜色和最右端的颜色,合并时和查询时判断一下即可。 注意的是查询链上时也需要判断。每次查询时记录一下左端点...
April 16, 2018

树链剖分总结

作为一个上个月刚学完线段树的蒟蒻,看Splay又看不懂,便直接跳着来学树剖了。又在一个博客上看到说学树剖之前最好还要把LCA给学了,便去花了一天学了一个Tarjan求LCA(然而后来发现并不怎么需要),然后是几乎照着别人的代码把树剖抄懂的。在这里我就讲一下我理解的树剖。 准备工作 链表/链式前向星 线段树/树状数组/Splay等可以维护一段数据的数据结构 LCA (其实只涉及到一些思想,...
April 10, 2018

LCA问题总结

概述 最近公共祖先(LCA)问题指的是在一棵树中,求出任意两个点的最近的公共祖先。如在下图中: 2号节点和1号节点的LCA是4,3号和2号的LCA也是4. 求LCA的方法主要有:暴力,倍增,RMQ和Tarjan。 这篇文章以洛谷P3379 【模板】最近公共祖先(LCA)为例。 Tarjan算法 Tarjan算法能够通过dfs将树上节点信息和查询的信息一次性解决,但是无法应对存在修改的情况,...
April 9, 2018

RMQ问题_ST表总结

RMQ问题 RMQ问题是指多次询问一个区间中最小或最大值的问题。但是因为不包括修改,只涉及离线操作,所以线段树或者树状数组显得有一些多余了。而且数列中的元素个数可能非常大,像线段树开四倍空间肯定是要MLE的。这里介绍一种高效的ST表来解决这种问题。 ST表 我的理解:ST表运用动态规划和二分的思想来完成。 ST表查询问题包含初始化和查询操作,其中初始化的时间复杂度为$O(n\times \l...