Transient~

分类

Android(14) c语言基础算法(2) dfs(1) dp(6) Java学习(1) 图论(5) 数据结构(4) 数论(7) 未归档(1) 贪心(1)

/ 注册

全部文章（共42篇）

【矩阵快速幂】- 洛谷 p3390 模板题（补一道斐波那契数列）

矩阵快速幂大意：就是对矩阵求快速幂，将快速幂中res=1换成单位阵，而取模运算完全在我们定义的乘法运算中进行，即Mul，其他的跟快速幂没有区别，当然我现在只掌握了基础，所以做了一道模板题。题目描述：题目链接：洛谷-p3390 题目背景矩阵快速幂题目描述给定n*n的矩阵A，求A^k...

2020-01-02

0 812

HDU-1874【最短路的算法Dijkstra和SPFA（链式前向星）】

最短路径问题引言：最短路大家都不陌生吧，他可以是两点之间的最短路（Floyd），也可以是单源最短路，即一个点到其他点的最短距离（Dijkstra和SPFA）。Floyd对于n个顶点（n>100）的图，就会T，所以我们经常用后面两种算法。相关题目： HDU-1874:畅通工程续这道...

2020-01-02

0 666

图论 -【拓扑排序】

拓扑定义：对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的...

2020-01-02

0 644

HDU - 1863【图论】- 最小生成树 Kruskal+Prim

题目： HDU-1863 Kruskal算法： int f[maxn]; struct node{ int u,v; int w; bool operator < (const node &s) const{ return w<s.w;...

2020-01-02

0 474

poj - 2142 超详细解释数论【扩展欧几里得】

扩展欧几里得题目链接：The Balance 题目描述： Description Ms. Iyo Kiffa-Australis has a balance and only two kinds of weights to measure a dose of medicine. For exa...

2020-01-02

0 541

HDU 2063 图论 -【匈牙利算法】

匈牙利算法什么是匈牙利算法：其实就是找二分图(离散数学一般叫二部图)的最大匹配，是一个递归的过程。直接给题目上板子吧。题目链接：过山车题目描述： Problem Description RPG girls今天和大家一起去游乐场玩，终于可以坐上梦寐以求的过山车了。可是，过山车的每一排...

2020-01-02

0 474

poj 3624 Balanced Lineup -【数据结构】- ST表

ST算法应用：假如我给你n个数，然后有m次询问，每次询问求一段区间，[l，r]上得极差。循环暴力跑一遍，很简单得对吧，但是我们稍微让n的值大一点，m的值也大一点，很容易就让你Time limit exceed。所以，本算法就是专门解决此类问题的，求一段区间上的最大值和最小值，其实也可以用线段树...

2020-01-02

0 461

线段树总结及例题 - 【数据结构】

线段树最近在学线段树，这个东西真的是有点难度，看了我整整两天才理解他的意思，其中最难的我觉得就是对懒惰标记的理解吧。引言：有一些题目，总是跟区间相关，比如求区间上的最大值与最小值，但是我们要的是n次询问，每次求最大值最小值，暴力就会t，不解释，可以用RMQ，也可以用线段树做。再比如说，每次...

2020-01-02

0 482

字典树 01字典树【数据结构】

题目1：字典树 HDU 1251 统计难题 Problem Description Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀). Input 输入数据的第一部分是一张单词表...

2020-01-02

0 492

PAT (Advanced Level) Practice 1030 Travel Plan 最短路径满足最小花费

题目： PAT 1030 Travel Plan A traveler’s map gives the distances between cities along the highways, together with the cost of each highway. Now you are s...

2020-01-02

0 419