前言 在OI学习过程中,我们常常会发现一些题目(尤其数据结构题)中,一些数据的范围很大,但是涉及的数值的个数却很少,同时我们想用一个数组的下标与这些数据建立一一对应关系,这时我们就需要离散化 大致思路 对于一个大小为$N$不含重复数字的数组$a[N] (a[i]<=10^9)$,我们可以将$a[]$中的N个整数与$1$ ~ $N$这$N$构成一一映射关系,也就是说把$a[i]$用一个$1$~

前言 图论中联通性相关问题往往会牵扯到无向图的割点与桥或是下一篇博客会讲的强连通分量,强有力的$Tarjan$算法能在$O(n)$的时间找到割点与桥 定义 若您是第一次了解$Tarjan$算法,建议您反复阅读定义,借助图像来理解 桥与割边 对于无向连通图中点集的一个节点$x$,删去节点$x$及其关联的边之后,存在一对不联通的点对$(a,b)$,则称$x$是这个无向图的割点 对于无向联通图中边集的一

题目链接https://www.luogu.org/problemnew/show/P2860 https://www.lydsy.com/JudgeOnline/problem.php?id=1718 分析首先这题目的意思就是让任意两点之间至少有两条没有重复道路的路径,很显然,如果这个图不存在桥,就一定满足上述条件。 于是我们就是要求使这个图不存在桥需要连接的最小边数 如果把桥从图中去掉,很显然

前言 在做一些树上路径修改&查询相关题目时,有时我们用不着树链剖分,类比于序列上的差分,我们可以进行树上差分,不过情况稍有些不同,分为点值上的差分和边权上的差分两种 点值差分 对树上路径$path(x,y)$进行点值差分方法: $tag[x]++,tag[y]++,tag[lca(x,y)]-=2$ 询问$x$被多少个标记覆盖时进行$dfs$,将$x$所有子树节点$tag[]$之和加上$t

前言 树链剖分是一个很好用的处理树上统计信息的方法,大致思想就是把树上路径分成$log N$条链,再用线段树之类的数据结构维护一下,所以时间复杂度得到了保障 怎么做 个人认为这篇讲的很好: https://www.cnblogs.com/George1994/p/7821357.html 注意 debug树链剖分对于我来说真是个痛苦的过程,初学时一个错误查了近一个小时才查出来. 首先你要知道线段树

inf值要设大但不要溢出 vis之类的数组使用前都memset一下 memset一些除0外的奇怪的数字时,最好老老实实写for循环(谁叫我脸黑) edge数组不要设小了 C++ 11 不要用register int 手写堆中$heap[]$最好不用结构体,若用,手写swap函数 $bool$ $flag$一定要赋初值!!!! 树链剖分注意https://www.cnblogs.com/Rye-Ca

Day 0 上了下测试系统,发现居然是毛子的题(貌似系统也是,只给了英文和俄语两个选项),话说T1 A+B什么鬼。 然后向教父请假,教父一脸严肃好吓人,但是我能逃掉期中考hhhhhhhhh 在火车站等车居然看到两个师大的? Day 1 早上五点多就被吵醒了,到了西客站后等了好久,然后又在宾馆等了好久,然后又背着大包走了好久,然后终于等到了房卡进了房间,话说房间真心不错(然而花的钱也很多) 下午模拟

—Update5.2 成绩出了,见后文 听说省选VAN写游记是传统,本蒟蒻也来发一篇吧。 DAY 0 本来以为省选不在JKFZ举行的结果又是在JKFZ,本校作战感觉终究会是好一些吧,和jyh一起向教父申请停了一天的课,没想到教父居然笑眯眯地答应了,有点出乎意料。 上午和jyh一起打了yjw学长Yali集训时的模拟赛,T1线段树,T2。。。 T3。。。然后愉快地打了线段树,结果。。。爆0。 中午吃完

Hello World 第一篇博客纪念 $ \mathcal{Enjoy Reading Here} $