上篇博客我们重点讲解了tarjan算法的实现以及它最重要的用法——求解强连通分量。这篇博客我们就继续学习一下tarjan的其他经典用法。 运用tarjan求割点 什么是割点 在无向连通图中,如果将其中一个点以及所有连接该点的边去掉,图就不再连通,那么这个点就叫做割点(cut vertex / articulation point) 例如,在下图中,0、3是割点,因为将0和3中任意一个去掉...
终于到图论部分了,图论我是真心弱啊QwQ。今天复习了一下tarjan,总结了一下其基本用法,希望对你有帮助吧。 什么是tarjan? tarjan算法又称“塔尖”算法,是解决图联通问题的一种神奇算法。换句话说,tarjan就是基于DFS算法,对每个点进行标记处理的一种基本图论算法。 tarjan有什么用? 由于tarjan是解决图联通的一种算法(:з」∠),所以我们很自然的可以想到可以用...
我们都知道,一种波长的可见光会对应一种固定的颜色。你是否会好奇,波长为X的可见光所对应的颜色的RGB值为多少呢?这篇博客就是要告诉你如何实现光的波长和RGB值的转换。 原理部分 说到波长与颜色的转换,第一反应便是色度图,而我采用的就是1931CIE-XYZ标准色度系统。 所谓1931CIE-XYZ系统,就是在RGB系统的基础上,用数学方法,选用三个理想的原色来代替实际的三原色,从而将CI...
咳咳咳,又是新的一年,在这里就祝大家在新的一年万事如意,天天打程序;财源广进,IOI夺金。这一小段时间,我抽空研究了一下脚本,今天就简单的介绍一点皮毛吧(我才不会告诉你是因为难的我不会咧。:laughing:) 编程工具 俗话说:工欲善其事必先利其器,所以好的编程软件非常重要。今天我们介绍的语言是Microsoft Visual Basic Script Editio(简称vbs),它的...
这次我们要介绍一个很高大上的东西FFT!,看完这篇博客,希望你能学会FFT,让多项式乘法成为你眼中的一道水题!:smile: :smile: 多项式乘法 顾名思义,就是两个多项式相乘。而我们要求的,就是相乘后各个项的系数,例如: 很显然我们可以通过手动暴力模拟来计算后各个项的系数,但复杂度却已经达到了O(n^2),在n到达10^5级别时就已经完美TLE了。 这就引导我们要在O(nlog...