GoldenPotato137的小屋
  • 留言板
  • PCB信仰尺
  • IP签名图
学习笔记
图论

最小树形图构造(朱刘算法)学习笔记

什么是最小树形图 最小树形图就是给定一个$n$个点的有向图,我们钦定一个根,现在要找$n-1$条边,在根能到达其他所有点的前提条件下,使得$n-1$条边的总长度尽可能小。 怎么找最小树形图 这里就得用到朱刘算法了。朱刘算法是一个$O(n \cdot m)$的算法。当然,还有Tarjan巨神的$O(nlogn)$的算法。但我太菜了,并学不会 图出自这里 上面这张图很好的诠释了朱刘算法的主要内容: 我们算法主要有以下几个步骤: 1. 找到到达每个点的长度最小的入边(根节点不找) 2. 这些边如果连成一颗树则结束; 3.…

2019年04月09日 2条评论 1228点热度 1人点赞 阅读全文
Kruskal重构树

Kruskal重构树学习笔记

为什么要学Kruskal重构树 有时候,题目让我们多次求一个图的两点路径上最小值最大/最大值最小是多少。这种时候,根据一个比较显然的结论,我们可以把问题搬到一颗最小/最大生成树里面去做。 这个时候,我们当然可以倍增来搞这个问题。但在这里,我想向大家引入一种新的数据结构,它是基于kruskal求生成树的算法改来的,因此被称为Kruskal重构树。 什么是Kruskal重构树 这张图可以一目了然的介绍Kruskal重构树: 图出自https://blog.csdn.net/wu_tongtong/article/det…

2019年03月07日 0条评论 424点热度 1人点赞 阅读全文
学习笔记

可并堆(左偏树)学习笔记

为什么要学左偏树 有时候,某些题目要求我们合并两个堆。 合并两个堆,大家都知道可以用splay暴力启发式合并处理。很不幸的是,这玩意的复杂度是$O(nlog^2n)$的,在一些毒瘤题目专门考可并堆的题目中,是注定要被卡的。 可并堆系列算法可以很优雅的解决这系列的算法,她们可以在$O(nlogn)$的时间内处理两个堆合并的问题。而我现在要讲的左偏树就是可并堆中的一种。 什么是左偏树 正如她字面意思一样,是一颗向左“偏”的树。什么叫“向左偏”呢?我们知道,平衡树的时间复杂度比二叉查找树优秀,是因为平衡树的左右子树深度尽…

2019年03月05日 0条评论 459点热度 0人点赞 阅读全文
FFT/NTT

快速傅里叶变换学习笔记(FFT)

什么是FFT FFT是用来快速计算两个多项式相乘的一种算法。 如果我们暴力计算两个多项式相乘,复杂度必然是$O(n^2)$的,而FFT可以将复杂度降至$O(nlogn)$ 如何FFT 要学习FFT,我们得先了解它的思想。 首先,我们得先了解如何表示一个多项式。显然,我们最传统的方法表示多项式就是表示它的系数就好。但是,如果我们用系数来计算两个多项式相乘,复杂度无论如何都是$O(n^2)$的。因此,我们引入点值表示法。 补充资料:什么是点值表示 设A(x)是一个n−1次多项式,那么把n个不同的x代入,会得到n个y。这…

2019年03月01日 0条评论 418点热度 0人点赞 阅读全文
学习笔记

第二类斯特林数学习笔记

本菜鸡尚未学会第二类斯特林数,请各位dalao不要相信本文的任何一个字 什么是第二类斯特林数 在组合数学,Stirling数可指两类数,第一类Stirling数和第二类Stirling数,都是由18世纪数学家James Stirling提出的。 Stirling数有两种,第一类和第二类Stirling数,它们自18世纪以来一直吸引许多数学家的兴趣,如欧拉、柯西、西尔沃斯特和凯莱等。后来哥本哈根(Copenhagen)大学的尼尔森(Niels Nielsen,1865-1931)提出了"Stirlingschen Z…

2019年02月25日 0条评论 441点热度 0人点赞 阅读全文
同余

[POJ 2891] Strange Way to Express Integers

题面 传送门:POJ Solution 就是裸的扩展中国剩余定理嘛qwq 注意几点:一定要时时刻刻去膜取模,否则一定会爆long long,尤其是算出来的$k_0$ 这里给出几组易锅数据:(第三组容易爆long long) input: 4 18373 16147 8614 14948 8440 17480 22751 21618 6 19576 8109 18992 24177 9667 17726 16743 19533 16358 12524 8280 22731 4 9397 38490 22001 250…

2019年02月25日 0条评论 331点热度 0人点赞 阅读全文
同余

扩展中国剩余定理学习笔记

为什么要扩展中国剩余定理? 建议学习前置芝士:中国剩余定理(不学也不要紧,因为并没有啥关系) 我们知道,中国剩余定理是用来解线性同余方程组的算法,类似下面这个: $x \equiv a_0 (p_0)$ $x \equiv a_1 (p_1)$ $x \equiv a_2 (p_2)$ 很不幸,这里要求$p_0,p_1,p_2$两两互质 . 如果不互质怎么办?当然是把出题者拖出去吊起来打啊。这时候就得有请我们的扩展中国剩余定理了。 什么是扩展中国剩余定理? 如上说述,就是用来求线性同余方程组的定理,但不要求p两两互…

2019年02月25日 0条评论 442点热度 0人点赞 阅读全文
LCT

LCT学习笔记

为啥要学LCT啊 在开坑之间,我们来先看一段对话: Q:给你一颗森林,现在不断的连接森林中的两棵树,保证不连出环,多次问你某两个点的连通性? A(dalao&蒟蒻):这不是SB题吗?显然并查集水过啊。 Q:说的好,但是如果我要删除某些边呢? A(dalao):那就可持久化并查集啊,你的问题怎么那么水。 A(蒟蒻):........(发出gg的声音) 这时候,如果我们并不想写可持久化并查集的话,就得请出我们大名鼎鼎的林特卡特树了。 啥是林特卡特树啊 LCT实质上就是用splay+树剖思想维护的动态森林。 用人…

2019年02月25日 0条评论 388点热度 2人点赞 阅读全文
学习笔记

淀粉质(点分治) 学习笔记

什么是淀粉质点分治? 就是把分治搬到树上,以某个点为根,分别分治处理子树的答案,再计算子树与子树间的答案的玄学算法。 举个例子: 如何求出一颗树上距离为K且所经过的点最少的点对? 对于这种题,我们可以把某个点(一般为重心)作为根,然后对左右子树递归处理,先分别得出左右子树的答案,再求出横跨两个子树之间的点对的答案。 为什么要学淀粉质 对于上面那道题,如果我们用传统的暴力做法,最优的复杂度只能得到O(n2)的暴力枚举,但是如果我们用淀粉质来搞,我们就可以做到O(n∗logn)的复杂度(如果K很大的话,我们可能还得套个…

2019年02月25日 0条评论 283点热度 0人点赞 阅读全文
学习笔记

裴蜀定理学习笔记

什么是裴蜀定理 裴蜀定理(或贝祖定理,Bézout's identity)得名于法国数学家艾蒂安·裴蜀,说明了对任何整数a、b和它们的最大公约 数d,关于未知数x和y的线性不定方程(称为裴蜀等式):若a,b是整数,且(a,b)=d,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立。 ——百度百科 用人话来说就是: $\sum a_i*x_i=b$ 上面的x有解当且仅当 $gcd(ai)|b$ 例题 luogu P4549 【模板】裴蜀定理 //Luogu P45…

2019年02月25日 0条评论 332点热度 0人点赞 阅读全文
12

GoldenPotato

HITer/ACMer/永远的OIer/数院/LLer/睿智的群星玩家+1000

NNEZ的Friends呢
  • %%%hzq dalao
  • 单向%%%神仙Maxwei_wzj
  • 可爱(?)的ComputerEngine 学弟
  • 安心退役的(?)wpy dalao
  • 把我按在地上锤的lizbaka julao
外校的Friends呢
  • %%% OItby
  • %%%神仙 冒泡ioa
  • %%%神仙attack204
  • allenyou
  • ChenHacker's Blog
  • Chhokmah姐姐() 的博客
  • CpZhao
  • stO神仙 gzy Orz
  • Woshiluo's Notebook
  • 可爱的suqingnian dalao
文章归档
  • 68
  • 30
  • 83,345
  • 24,708

COPYRIGHT © 2020 GoldenPotato137的小屋. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

桂ICP备20002051号