Llf's blog

2018年2月

Llf in 题解
February 8, 2018

题解-洛谷P1309 瑞士轮

原题链接 洛谷博客该题解链接 题目内容 题目背景 在双人对决的竞技性比赛,如乒乓球、羽毛球、国际象棋中,最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少,每场都紧张刺激,但偶然性较高。后者的特点是较为公平,偶然性较低,但比赛过程往往十分冗长。 本题中介绍的瑞士轮赛制,因最早使用于1895年在瑞士举办的国际象棋比赛而得名。它可以看作是淘汰赛与循环赛的折中,既保证了比赛的稳定性,又能使赛程不...
February 7, 2018

几种排序方法总结

冒泡排序 方法 第一次将每一个元素和它的后一个元素比较大小,如果不满足顺序则交换,这样即可确定最后一个数的位置。然后再从头开始,可以确定倒数第二个数的位置。循环n次后即可完成排序。因为每一轮排完序后都会确定一个,即“冒”出来一个,故被称作冒泡排序。 时间效率:$O(n^{2})$ 代码 以 洛谷 P1116 车厢重组 为例 #include<bits/stdc++.h> usi...
February 6, 2018

拓扑排序

概念 拓扑排序是一种可以将有先决条件(即必须将a、b排在前面后再排c,缺一不可)的数据变得有序的一种排序方法。拓扑排序仅可在有向无环图中使用,同时可以判断图中是否有环。因为顺序不同,拓扑排序得到的答案可能不同。 思路 因为排序是有先决条件的,所以可以将要有先决条件的个数(在图中即为入度)记录下来,每满足一个就减一,直到个数为0便可以将其放入序列中。 手动实现 如果我们有如下的一个有向无环图,...
February 6, 2018

最小生成树

概念 最小生成树即为无向图中结点构成的树中各边权值之和最小的树,可以有多种情况。一般用Kruskal(克鲁斯卡尔)算法或Prim(普里姆)算法求出。 Kruskal算法 方法 可以将Kruskal算法理解成对边的贪心算法。 1.将路径用邻接表存储,存储的值为起点、终点和权值; 2.将邻接表按照权值为关键字排序; 3.从最小权值的边开始循环,每连接起两个结点就把它们并到同一个集合(并查集实现)...