Llf's blog

February 6, 2018

拓扑排序

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

最小生成树

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

前缀和差分

前缀和差分用于在多次求数据中选取一部分的和,可分为一维前缀和和二维前缀和 一维前缀和 运用递推,将数组每一个元素替换为到这个元素的所有元素之和,如 1 3 4 3 2 5 在处理后变为 1 4 8 11 13 18 如何需要求出数组第X位到第Y位的和,直接用f[y]-f[x-1]即可 二维前缀和 与一维前缀和同理,只是f[a][b]的值变为从s[1][1]到这个点的矩阵内所有数的和,如s...
Llf in 游记
December 2, 2017

NOIp2017爆炸记

Day -N 去年只参加PJ,凑巧拿了个一。今年第一次参加TG,还有在徐妈的逼迫下又参加了PJ,还想拿个高分(事实上死的很惨) Day 0 就复习了点简单的东西(毕竟考前三天才学会c++的文件,P转C的痛苦),中午大半时间在颓2048,感觉什么都没干 Day 1 上午TG。妈的我第一题找了大半个小时都没找出规律就打了个暴力了事;第二题纯种模拟,二十多个变量,样例都过了,当时感觉应该没有问题;...
Llf in 题解
September 18, 2017

题解-洛谷P1045 麦森数

原题链接 洛谷博客该题解链接 题目内容 题目描述 形如$2^{P}-1$的素数称为麦森数,这时P一定也是个素数。但反过来不一定,即如果P是个素数,$2^{P}-1$不一定也是素数。到1998年底,人们已找到了37个麦森数。最大的一个是P=3021377,它有909526位。麦森数有许多重要应用,它与完全数密切相关。 任务:从文件中输入P(1000<P<3100000),计算$2...
Llf in 题解
September 18, 2017

题解-洛谷P1015 回文数

原题链接 洛谷博客该题解链接 题目内容 题目描述 若一个数(首位不为零)从左向右读与从右向左读都一样,我们就将其称之为回文数。 例如:给定一个10进制数56,将56加65(即把56从右向左读),得到121是一个回文数。 又如:对于10进制数87: STEP1:87+78 = 165 STEP2:165+561 = 726 STEP3:726+627 = 1353 STEP4:1353+35...