凡尔赛卷卷

分类

做题笔记(85) 学习笔记(16)

/ 注册

全部文章（共101篇）

差分约束

我的第一道差分约束 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 1055

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

读大佬的博客附上链接，，图也是人家的对不起 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

CF E69 D dp

Educational Codeforces Round 69 (Rated for Div. 2) D 题目链接题目大意：输入一个数组 n m k 求在数组中找一段连续的数求 ∑ai − k * ⌈(r−l+1)/m⌉ 的最大值显然 r - l + 1 是找的连续的数的长度；这个题m...

2020-09-15

0 607

牛客练习赛56 E 图

牛客练习赛 56 E 题目链接这道题其实并不难，为什么要写他呢？因为被他坑了题目：给一个图，自己加上一条边后，问随机删去一条边后让图不连通的最小概率。很明显缩点建图然后跑个树的直径设直径为 d 缩点图上共 m 条边原先图*** s 条边答案就是 (m-d)/(s+1) 但...

2020-09-15

0 507