Category Archives: BeforeBuild

重拾WQS二分

Cptraser/ 十月 24, 2018/ BeforeBuild/ 0 comments

重拾WQS二分 前置SKILL:·初等函数 ·二分 对于一个单调的函数,我们可以二分一个斜率,使其增大的同时限制来求得我们所求的答案。 BZOJ2654 tree 我们二分边权增量,令每条白边加上该增量,最后答案减去即可。 该想法可以视为将白边被最小生成树选中的概率减小。 #include <cstdio&

Read More

虚树相关

Cptraser/ 十月 24, 2018/ BeforeBuild/ 0 comments

虚树相关 前置技能: 欧拉序:就是从根结点出发,按dfs的顺序在绕回原点所经过所有点的顺序。 LCA:最近公共祖先。 栈:不会就去面壁。 相关概念: 虚树就是将原问题中的树形结构选取关键点,建成的这棵新树。 通过选取关键点可以降低复杂度(优化暴力)。 虚树有效地保留了原树的主要特征,精简了原树结构,所以称其优化暴

Read More

数论分块与莫比乌斯反演1

Cptraser/ 十月 24, 2018/ BeforeBuild/ 0 comments

数论分块与莫比乌斯反演(一) 数论分块 对于类似这样的式子,它的值有连续相等的区间,可以对值分块,将值相等的放在一起统计,复杂度达到 引理:对于一段值相等的区间的左端点,其右端点为。(以为例)。 求解 解释一下,莫比乌斯函数满足这样的性质,。 考虑枚举因子 这两个东西可以数论分块。 #include <cs

Read More

牛客练习赛23赛后感悟

Cptraser/ 十月 24, 2018/ BeforeBuild/ 0 comments

牛客练习赛23题解及赛后感悟 A:托米的赌球 水题一道,不停的除和膜就好了。(基本上复制粘贴) #include <cstdio> #include <cstring> using namespace std; int T,a,b,A[10],B[10]; int main() { sca

Read More

可持久化并查集

Cptraser/ 十月 24, 2018/ BeforeBuild/ 0 comments

深夜闲谈可持久化(1)-可持久化并查集 可持久化并查集,名字听起来非常高大上,其实就是将并查集的数组可持久化。 所以可持久化并查集又称可持久化数组。 但是由于数组的可持久化实现如果使用链表的话,会非常难实现,而且还会爆时间复杂度。 这时我们可以将数组的结构改为树状的结构,同时借用主席树的思想,这时可持久化并查集就

Read More

计算几何初步-凸包

Cptraser/ 十月 24, 2018/ BeforeBuild/ 0 comments

计算几何初步-凸包Graham扫描法 概要知识 向量 在数学中,向量(也称为欧几里得向量、几何向量、矢量),指具有大小(magnitude)和方向的量。它可以形象化地表示为带箭头的线段。箭头所指:代表向量的方向;线段长度:代表向量的大小。与向量对应的只有大小,没有方向的量叫做数量(物理学中称标量)。 叉积 向量积

Read More

关于Mex问题的整理

Cptraser/ 十月 24, 2018/ BeforeBuild/ 0 comments

关于区间Mex问题的算法整理 给你一个长度为n的数列,元素编号1到n,第i个元素值为Ai。现在有m个形如(L,R)的提问,你需要回答出区间[L,R]的mex值。即求出区间[L,R]中没有出现过的最小的非负整数。 该问题被称为区间Mex问题,这个问题的解法多种多样,下面给出3种不同解法。 离线+线段树维护 由于没有

Read More

打开CDQ的大门&BZOJ3262

Cptraser/ 十月 24, 2018/ BeforeBuild/ 0 comments

打开CDQ的大门&BZOJ3262 题目传送门 第一次接触CDQ分治,感谢YZ大佬的教导。 CDQ分治就是一种奇特的分治方法,它用左区间的区间信息来更新右区间。 设CDQ(L,R,l,r)表示递归到区间[L,R],区间的值为[l,r]。 mid=(l+r)/2; 将L~R区间按<=mid和>mid的

Read More