BelowLuminous

BelowLuminous : eoj1301
2 年,5 月前

无人过题除草计划 eoj1301AC 做法,将图转化成三角剖分树,然后就是三点之间最长路径问题,dfs随便搞搞就好了. ...查看全文
BelowLuminous : 分享一个理论上是NlogN时间复杂度的LCS(最长公共子串)算法
3 年前

在这里提一下O(n log n)的算法 假设有两个序列 s1[ 1~6 ] = { a, b, c , a, d, c }, s2[ 1~7 ] = { c, a, b, e, d, a, b }。 记录s1中每个元素在s2中出现的位置, 再将位置按降序排列, 则上面的例子可表示为: loc( a)= { 6, 2 }, loc( b ) = { 7, 3 }, loc( c ) = { 1 }, loc( d ) = { 5 }。 将s1中每个元素的位置按s1中元素的顺序排列成一个序列s3 ...查看全文
BelowLuminous : 女生让男生厌恶的10种习惯
3 年,2 月前

1.不温柔; 2.用FFT计算逆DFT后不将各项系数除以阶数;3.维护splay树时偷懒用单旋代替双旋; 4.对Link-Cut-Tree进行换根操作时不打翻转标记; 5.应用Pólya定理时不将单位元计入置换群; 6.计算SG函数时忽略判定规则而使用错误的边界值; 7.维护无根树点分治结构时不维护上一层分治重心邻接点的信息; 8.连续调用Push-Relabel算法时不重新初始化标签; 9.利用CRT求解一元模线性方程组时忽略模数不互质的情况直接套用公式; 10.运用Matrix-Tree ...查看全文
BelowLuminous : 二分图问题资料整合处理(3):二分图问题常见模型
3 年,2 月前

zoj1654 题意:有一个N*M(N,M<=50)的棋盘,棋盘的每一格是三种类型之一:空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人,若它们之间没有墙,则它们可以互相攻击。问给定的棋盘,最多可以放置多少个机器人,使它们不能互相攻击。 分析:本题也是二分图匹配的一个经典题目。我们将每一行,每一列被墙隔开,且包含空地的连续区域称作“块”。显然,在一个块之中,最多只能放一个机器人,我们把这些块编上号。同样,把竖直方向的块也编上号,把每个横向块看作X部的点,竖向块看作Y部的点,若两个块 ...查看全文
BelowLuminous : 二分图问题资料整合处理(2):一般图的最大匹配问题求解
3 年,2 月前

增广轨方法 增广轨的定义(也称增广路或交错轨): 若P是图G中一条连通两个未匹配顶点的路径,并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现,则称P为相对于M的一条增广轨(举例来说,有A、B集合,增广路由A中一个点通向B中一个点,再由B中这个点通向A中一个点……交替进行)。 由增广轨的定义可以推出下述三个结论:  1-P的路径长度必定为奇数,第一条边和最后一条边都不属于M。  2-不断寻找增广轨可以得到一个更大的匹配M’,直到找不到更多的增广轨。  3-M为G的最大匹配当且仅当不 ...查看全文
BelowLuminous : 二分图问题资料整合处理(1):“支配集覆盖集与独立集”
3 年,2 月前

各种定义: 一、点支配 【支配】 对于图G中顶点集合V中的某一个点A与另一个点B有边链接,叫做点A支配B。 【点支配集】 对于图G中顶点集合V中的某个顶点子集V’,可以支配V-V’中的其他点,这个点集V’就是点支配集。 【极小支配集】 对于支配集V,他的任何真子集都不是支配集,就称为V是极小支配集。 【最小支配集】 顶点数最小的支配集就是最小支配集。 注意:极小支配集和最小支配集不是一个含义。 【点支配数】 最小点支配集中点的个数被称为点支配数。 点支配集性质:当一个图没有孤立顶点 ...查看全文
BelowLuminous : Miller Rabin算法的改进
3 年,2 月前

Millar-Rabin质数检验方法: 根据费马小定理,如果p是素数,a<p,那么有a^(p-1) mod p = 1。 直观想法我们直接取若干个a,如果都有一个不满足,那么p就是合数。 遗憾的是,存在Carmichael数:你无论取多少个a,有一个不满足,算我输。 比如:561 = 11X51就是一个Carmichael数。 那么就很江了啊。。我们需要改进算法。 首先有:如果p是素数,x是小于p的正整数,且x^2 mod p = 1,那么要么x=1,要么x=p-1 (这个废话,x=p-1模意 ...查看全文
BelowLuminous : bzoj 1801/4806
3 年,2 月前

题目描述: 在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮。 请问有多少种放置方法.输出所有的方案数,由于值比较大,输出其mod 9999973. 这是一道非常有意思的dp题目,f[i][j][k]为前i行,保证m列中j列只有一个数字,k列有两个数字。 就做完了233333 ...查看全文
BelowLuminous : Pollard_rho算法与Miller Rabin算法
3 年,2 月前

适用范围:给你一个大数n,将它分解它的质因子的乘积的形式。 Miller-Rabin测试 费马小定理:对于素数p和任意整数a,有a^p ≡ a(mod p)(同余)。反过来,满足a^p ≡ a(mod p),p也几乎一定是素数。 伪素数:如果n是一个正整数,如果存在和n互素的正整数a满足 a^n-1 ≡ 1(mod n),我们说n是基于a的伪素数。如果一个数是伪素数,那么它几乎肯定是素数。 Miller-Rabin测试:不断选取不超过n-1的基b(s次),计 ...查看全文
BelowLuminous : 考试不嫌没事做了
3 年,5 月前