BelowLuminous : eoj1301
6 年，6 月前
无人过题除草计划
eoj1301AC
做法,将图转化成三角剖分树,然后就是三点之间最长路径问题,dfs随便搞搞就好了.
...查看全文
BelowLuminous
BelowLuminous : 分享一个理论上是NlogN时间复杂度的LCS(最长公共子串)算法
7 年，2 月前
在这里提一下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种习惯
7 年，4 月前
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)：二分图问题常见模型
7 年，4 月前
zoj1654
题意：有一个N*M(N,M<=50)的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。
分析：本题也是二分图匹配的一个经典题目。我们将每一行，每一列被墙隔开，且包含空地的连续区域称作“块”。显然，在一个块之中，最多只能放一个机器人，我们把这些块编上号。同样，把竖直方向的块也编上号，把每个横向块看作X部的点，竖向块看作Y部的点，若两个块
...查看全文
BelowLuminous : 二分图问题资料整合处理(2)：一般图的最大匹配问题求解
7 年，4 月前
增广轨方法
增广轨的定义(也称增广路或交错轨)： 若P是图G中一条连通两个未匹配顶点的路径，并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广轨（举例来说，有A、B集合，增广路由A中一个点通向B中一个点，再由B中这个点通向A中一个点……交替进行）。
由增广轨的定义可以推出下述三个结论：
1－P的路径长度必定为奇数，第一条边和最后一条边都不属于M。
2－不断寻找增广轨可以得到一个更大的匹配M’，直到找不到更多的增广轨。
3－M为G的最大匹配当且仅当不
...查看全文
BelowLuminous : 二分图问题资料整合处理(1)：“支配集覆盖集与独立集”
7 年，4 月前
各种定义:
一、点支配
【支配】
对于图G中顶点集合V中的某一个点A与另一个点B有边链接，叫做点A支配B。
【点支配集】
对于图G中顶点集合V中的某个顶点子集V’，可以支配V-V’中的其他点，这个点集V’就是点支配集。
【极小支配集】
对于支配集V，他的任何真子集都不是支配集，就称为V是极小支配集。
【最小支配集】
顶点数最小的支配集就是最小支配集。
注意：极小支配集和最小支配集不是一个含义。
【点支配数】
最小点支配集中点的个数被称为点支配数。
点支配集性质：当一个图没有孤立顶点
...查看全文
BelowLuminous : Miller Rabin算法的改进
7 年，4 月前
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
7 年，4 月前
题目描述:
在N行M列的棋盘上，放若干个炮可以是0个，使得没有任何一个炮可以攻击另一个炮。 请问有多少种放置方法.输出所有的方案数，由于值比较大，输出其mod 9999973.
这是一道非常有意思的dp题目，f[i][j][k]为前i行，保证m列中j列只有一个数字，k列有两个数字。
就做完了233333
...查看全文
BelowLuminous : Pollard_rho算法与Miller Rabin算法
7 年，4 月前
适用范围：给你一个大数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次)，计
...查看全文
关于我们
团队: @ultmaster, @zerol, @kblack.
联系方式: acmsupport@admin.ecnu.edu.cn