凡尔赛卷卷

学习笔记

做题笔记(85)

/ 注册

全部文章 / 学习笔记（共16篇）

差分约束

我的第一道差分约束 poj 3169 差分约束加b啥啥的那个找负环的算法 Bellman-Ford #include <stdio.h> #include <algorithm> #include <vector> using namespace std; /...

2020-09-15

0 771

点分治哦亲~~

例题：（板子）洛谷板子题P3806 洛谷第二个板子题p4178 说一下点分治、感觉还看的懂。经典问题：找一个树上距离为k的有多少对点。怎么找呢？分治思想：递归也就是找一个合适的根然后把问题分为跨过这个根的两个点和不过这个根的距离也就是在一个子树上的两个点和不在同一个子树上的两个点...

2020-09-15

0 536

树刨入个门？

树链刨分瞎bb会重儿子：重儿子是每个节点的儿子节点中子树节点数最大的那一个。树链刨分，把一个树砍成好多份变成一个数组p，p数组里存的是点的访问到的顺序，但是点的顺序是根据什么来的？先访问重儿子，因为这样可以尽可能多的一下找好长的链。经典问题：1.给树上两个节点之间的最短边上加上val...

2020-09-15

0 553

线段树区间合并

区间合并说一道例题：poj3667 题意: 两种操作： 1 s 查询有没有连续为s的区间有的话输出最左端的那个位置并把那个区间里的值都减了 2 a s 左端为a长度为s的房间退房也就是a~a+s-1这个区间值都加一考虑怎么做。。可以给线段树里放一个lnum，rnum，num分别代表左边连...

2020-09-15

0 554

扫描线~

突然发现自己好菜~这都不会。。。来记录一下我学的扫描线扫描线可以解决矩形面积的问题,如:给出n个矩阵有重叠部分，问你面积（各种面积）。然后，原理：画的歪歪扭扭好歪好扭黄线就是扫描线了。然后线段树里一般维护的是矩形所在当前扫描线上的长度。（说的不太清）就是好歪好扭凑合吧画括号...

2020-09-15

0 648

有向无环图最小路径覆盖

最小路径覆盖？概念：最小路径覆盖就是找出最小的路径条数，使之成为P的一个路径覆盖．前置知识：匈牙利算法为什么要用匈牙利算法？首先每个点都可以代表一个简单路径答案是n 但是要求最小的路径覆盖用匈牙利匹配他的下一个节点（他的下一个节点只能有一个,因为是有向无环图）。意思是把这...

2020-09-15

0 1054

曼哈顿距离、切尔雪夫距离

读大佬的博客附上链接，，图也是人家的对不起 QAQ 曼哈顿距离曼哈顿距离：d(i,j)=|X1-X2|+|Y1-Y2|. 也就是横纵坐标差的绝对值的和。切比雪夫距离切比雪夫距离：二个点之间的距离定义是其各坐标数值差绝对值的最大值一个是和、一个是最大值。废话曼哈顿距离的图 ...

2020-09-15

0 1307

可持久化并查集

可持久化并查集简单来说就是两颗主席树一颗维护父亲节点是谁一颗维护深度为什么要维护深度？降低时间复杂度并查集如果不优化的查询的话是这样: int findx(int x) { return x == fa[x]?x : findx(fa[x]); } void heb...

2020-09-15

0 602

分块简单的

分块分块是啥？暴力？以前看分块看了一半，放在那里了，，今天想起来了，就又看了一下分块的思想：把n分成根号n块然后暴力，这也没啥，主要是记录一下大段: 被分成的块一大块假设要维护的区间是 l~r 把在这个区间里的大段区间暴力维护一下，把两旁的不是一整段的小段暴力维护就好。时间复杂度...

2020-09-15

0 367

替罪羊树学习笔记哦

替罪羊树替罪羊树是啥？就是一个平衡树，只不过没有旋转操作那遇到不平衡的咋办呢？重构。怎么重构？先求出不平衡子树的中序遍历（这个中序遍历肯定是有序的递增的）于是就可以分治建树，取中间那个点当根左边的当左子树、右边的当右子树……递归下去于是就把不平衡的子树变成平衡的子树。例题：洛谷模板...

2020-09-15

0 428