A fresh start.

April 24, 2018

洛谷4092 [HEOI2016/TJOI2016]树

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

树链剖分总结

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

最小生成树

概念最小生成树即为无向图中结点构成的树中各边权值之和最小的树,可以有多种情况。一般用Kruskal(克鲁斯卡尔)算法或Prim(普里姆)算法求出。Kruskal算法方法可以将Kruskal算法理解成对边的贪心算法。1.将路径用邻接表存储,存储的值为起点、终点和权值;2.将邻接表按照权值为关键字排序;3.从最小权值的边开始循环,每连接起两个结点就把它们并到同一个集合(并查集实现),连接之前判断...
December 2, 2017

NOIp2017爆炸记

Day -N去年只参加PJ,凑巧拿了个一。今年第一次参加TG,还有在徐妈的逼迫下又参加了PJ,还想拿个高分(事实上死的很惨)Day 0就复习了点简单的东西(毕竟考前三天才学会c++的文件,P转C的痛苦),中午大半时间在颓2048,感觉什么都没干Day 1上午TG。妈的我第一题找了大半个小时都没找出规律就打了个暴力了事;第二题纯种模拟,二十多个变量,样例都过了,当时感觉应该没有问题;第三题直接...