回归梦想

算法

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2) 题解(271)

/ 注册

全部文章 / 算法（共76篇）

点分治（树分治）

@[toc] 介绍：将原问题分解成若干相同形式，相互独立的子问题，各个击破一般用来解决有关树上路径的统计和询问题目： P4178 Tree给定一棵 n 个节点的树，每条边有边权，求出树上两点距离小于等于 k 的点对数量。做法：暴力做法；(O(n^2^))点分治做法：选择一个点作为分治中心，令...

点分治

2021-02-23

0 419

失配树（border树）

4和6没有border关系举例子：当i = 3时，j = fa[i-1] = fa[2] = 0s[j+1] = s[1] = a = s[3]所以把i = 3点的父亲设为j+1 = 1P5829 [模板]失配树

失配树

2021-02-18

0 478

树链剖分

@[toc]源自oi-wiki树链剖分思想及能解决的问题树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。具体的说：将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。树链剖分有重链剖分，长链剖分和用于Link/cut Tree的剖分，大多数情况下（没有特别说明...

树链剖分

2021-02-18

0 452

线性基

线性基概念 B成为线性基这个过程其实相当于将S压缩成B 构造线性基线性基满足特殊性质：若a[i]!=0（即主元i存在），则线性基中只有a[i]的第i位是1；且此时a[i]的最高位就是第i位为了实现这个性质需要用特殊的insert方法：（为了确保有主元的一列只有一个1）如果第j位是主元不是自...

** 线性基

2021-02-16

0 354

P3389 【模板】高斯消元法来自专栏

P3389 【模板】高斯消元法题目：给定一个线性方程组，对其求解题解：还没接触高斯消元时以为是什么神仙算法，接触后发现。。。就是把我们手算线性方程组的方法，写成了代码emm。。。比如： x-2y+3z=6 4x-5y+6z=12 7x-8y+10z=21 化为矩阵 1 -2 3 6 4 -5...

高斯消元

2021-01-25

0 497

P3803 【模板】多项式乘法（FFT）

P3803 【模板】多项式乘法（FFT）题目描述给定一个 n 次多项式 F(x)，和一个 m 次多项式 G(x)。请求出 F(x)和 G(x)的卷积。从低到高输出F(x)*G(x)的系数另一种问法：如果有两个无限序列a和b，那么它们卷积的结果是：求出yn值题解：模板题建议背过模板讲的非常不错...

模板题 FFT 数论

2021-01-23

0 556

P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包

P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包题目：给定一些点，问围住所有点所用的围栏的长度题解：凸包模板题凸包详细代码： #include<iostream> #include<algorithm> #include&l...

** 凸包计算几何

2021-01-23

0 674

（神奇的）虚树（初步了解）

参考文献：博文1博文2博文3 引入在一类树上动态规划问题中,题目给出的询问往往包含树上的很多各节点,并保证总的点数规模小于某个值. 如果我们直接在整颗树上进行dp的话,时间复杂度与询问的次数有关,这显然是不可接受的,如果我们可以找到一种动态规划的方法,使其时间复杂度与询问中点的实际规模相关就好了...

虚树 ***

2021-01-21

0 410

带花树算法

对于一般的二分图匹配我们肯定会想到匈牙利算法，但是如果图中出现奇环怎么办？此时匈牙利算法就不可以了，就需要另一个算法：带花树算法主要就是为了解决奇环的问题我们匹配时会发现，如果存在奇环，传统的匈牙利算法在一个奇环里至少有一个点不能匹配，那么干脆就把这个奇环缩成一个点（也叫开花，这就是算法名字的由来）...

带花树算法 ***

2021-01-20

0 1276

计算几何基础-1

@[toc] 基本概念点：平面上一点，用坐标(x,y)来表示 struct Point{ double x,y; }; 向量：同时具有大小和方向的量。把向量从原点出发到达的点的坐标作为该向量的坐标 typedef Point Vector; 点与向量的运算点 + 向量 = 点向量 +...

计算几何

2021-01-17

0 498