thyzzs' Blog
正在加载今日诗词...
【笔记】基于链式前向星的图论算法(三) 拓扑排序 【笔记】基于链式前向星的图论算法(三) 拓扑排序
有向无环图(DAG)可用来表示各种事物的顺序。比如以各项工作为顶点,用有向边来表示工作顺序。 如果对这种表示顺序关系的DAG进行拓扑排序, 我们便能得到一个恰当的工作顺序。 拓扑排序不是用于将n个数从小到大排序,而是对于一个DAG,对图上的
2019-09-13
【笔记】基于链式前向星的图论算法(一) 搜索 【笔记】基于链式前向星的图论算法(一) 搜索
Part 0 缘起近日整理笔记时发现,初学时的图论算法都是基于邻接矩阵储存的,使用时非常不方便。所以就写了这篇博文,聊作图论学习的回顾。 Part 1 图的链式前向星表示链式前向星又称为邻接表的静态建表方式,其最开始确实是基于前向星,是以提
2019-09-08
【笔记】C++的常数优化技巧 【笔记】C++的常数优化技巧
Part 0 时间复杂度常数优化的意义在科学研究意义上,时间复杂度的常数优化并不是十分重要的。 但在信息学竞赛中,同样的复杂度为$O(n^2)$的程序,对于一组 $n=5000$ 的数据,有的可能常数为20,需要运行1000ms,有的可能常
2019-09-08
题解 T93279 【最长上升子树链】 题解 T93279 【最长上升子树链】
传送门 30%的题解: 这棵树是一个链,所以直接做一遍LIS和LDS,经典DP算法,不多赘述。 60%的题解: $N<=1000$,可以直接$n^2$地做满分题解所说的DP。 满分题解: $F1[i]$表示以从以$i$为根节点的子
2019-08-22
题解 T93270 【轰炸城市】 题解 T93270 【轰炸城市】
传送门 30%的题解: 直接每次询问枚举所有点。 60%的题解: 坐标值很小,可以尝试用链表,可以做到$O(n)$的时间复杂度 100%的题解: $map$套$multiset$ $X$坐标开个$mapx$,里面存的是每个$X$坐标的
2019-08-20
题解 T93222 【生成树】 题解 T93222 【生成树】
传送门 30%的题解: 是一棵树,所以只要枚举根,然后计算代价即可 100%的题解: $vals[S]$表示集合$S$的权值和 设计状态$F[S][h]$, 表示现在已经选择了的点的集合是$S$,$h$表示当前深度 枚举S的补集的子集
2019-08-20
题解 T93336 【最短路】 题解 T93336 【最短路】
传送门 30%的做法 floyd预处理出每两点间的最短路,每次询问$O(1)$回答 复杂度$O(n^3+q)$ 另外20%的做法 树的情况 对于$u,v$的最短路,求出他们的LCA为$k$,$ans=d[u]+d[v]-2*d[k
2019-08-20
题解 T93284 【最大公因数】 题解 T93284 【最大公因数】
传送门 30%的做法 暴力枚举删掉哪些数即可,复杂度$O(n \log (\max(a_i)) \times 2^n)$ 另外20%的做法 枚举删掉一些数后的最大公因数$g$,那么不能被$g$整除的数的个数即为要删的数的个数,对结果取$\
2019-08-18
题解 T93283 【集合】 题解 T93283 【集合】
传送门 考虑如何将s中的每种数分到$a$和$b$集中假设一个数$x$有$k$个,可以对$a$和$b$集“好的”数的个数差产生什么影响?$k=1$ 让一个集合“好的”数个数++,另一集合的个数不变 $k=2$ 让两个集合“好的”数个数都++
2019-08-18
2 / 2