肥城一中FOI 2019级宣传 OI是什么?信息学奥林匹克竞赛(OI,Olympiad in Informatics)。 与大家熟知的数学、物理、化学、生物竞赛合称为高中五大学科竞赛。 肥城一中FOI为学校官方组织,也是唯一的官方社团,又名信息学奥赛小组。 OI学什么?通 2019-09-20 Life in OI 宣传
【笔记】基于链式前向星的图论算法(三) 拓扑排序 有向无环图(DAG)可用来表示各种事物的顺序。比如以各项工作为顶点,用有向边来表示工作顺序。 如果对这种表示顺序关系的DAG进行拓扑排序, 我们便能得到一个恰当的工作顺序。 拓扑排序不是用于将n个数从小到大排序,而是对于一个DAG,对图上的 2019-09-13 Life in OI 图论
【笔记】基于链式前向星的图论算法(二) 最短路 Part 1 单源最短路(SSSP)DijkstraDijkstra只能用于无负权边的图。 设图$G=(V,E)$所有顶点的集合为$V$,起点为$s$,最短路径树中包含的顶点集合为$S$。 在各计算步骤中,我们将选岀最短路径树的边和顶点并将 2019-09-13 Life in OI 图论
【笔记】基于链式前向星的图论算法(一) 搜索 Part 0 缘起近日整理笔记时发现,初学时的图论算法都是基于邻接矩阵储存的,使用时非常不方便。所以就写了这篇博文,聊作图论学习的回顾。 Part 1 图的链式前向星表示链式前向星又称为邻接表的静态建表方式,其最开始确实是基于前向星,是以提 2019-09-08 Life in OI 图论
【笔记】C++的常数优化技巧 Part 0 时间复杂度常数优化的意义在科学研究意义上,时间复杂度的常数优化并不是十分重要的。 但在信息学竞赛中,同样的复杂度为$O(n^2)$的程序,对于一组 $n=5000$ 的数据,有的可能常数为20,需要运行1000ms,有的可能常 2019-09-08 Life in OI 思想方法