3 GMFTBY

尚未进行身份认证

for all

等级
TA的排名 1w+

POJ 3295 - 位运算 + 模拟 +递归

1.Question:本题是用枚举的思路来判断一个规定的逻辑表达式是不是永真式首先题目意思是最多不会有超过5个逻辑变量,有五种运算DefinitionsofK,A,N,C,andE     w  x Kwx Awx  Nw Cwx Ewx 1 1 1 1  

2016-12-04 16:47:49

NYOJ 118 次小生成树

1.Question:描述南将军率领着许多部队,它们分别驻扎在N个不同的城市里,这些城市分别编号1~N,由于交通不太便利,南将军准备修路。现在已经知道哪些城市之间可以修路,如果修路,花费是多少。现在,军师小工已经找到了一种修路的方案,能够使各个城市都联通起来,而且花费最少。但是,南将军说,这个修路方案所拼成的图案很不吉利,想让小工计算一下是否存在另外一种方案

2016-12-03 14:38:23

胜者树 败者树 K-路最佳归并树 高效外部排序

外部排序外部排序和内部排序还是有非常的的不同的,我们的外部排序主要针对的优化目标也是不同的,这里我先从外部排序的物理基础开始进行讲解1.外存:外部存储设备,相对于我们的内部存储设备而言具有一些特点1.优点:永久存储能力,便携性,存储空间大2.缺点:访问速度相对于内存的访问速度来说极其低下(相差约5~6个数量级)因此对于外存来说,我们要遵守的基本操作原则就是:尽

2016-12-02 16:33:21

POJ 1062 - 昂贵的聘礼 - 经典题

1.Question:中文题不说什么了2.Solution:本题的难点有两个1.建图2.限制建图:首先,我们需要明确本图G是一个有向图,我们的顶点代表庙我们的物品的编号,图采用邻接矩阵存储,我们的图中的邻接矩阵中存储我们的便宜价格这样的话,我们每个点只要在限制条件下都可以找到1点,那么我们就取到达1点的最小值当作我们的答案限制:本体的限制说的很明

2016-11-30 17:57:26

POJ 1860 - SPFA - 正权回路

1.Question:我们的城市有几个货币兑换点。让我们假设每一个点都只能兑换专门的两种货币。可以有几个点,专门从事相同货币兑换。每个点都有自己的汇率,外汇汇率的A到B是B的数量你1A。同时各交换点有一些佣金,你要为你的交换操作的总和。在来源货币中总是收取佣金。例如,如果你想换100美元到俄罗斯卢布兑换点,那里的汇率是29.75,而佣金是0.39,你会得到(100-0.39

2016-11-29 17:58:26

POJ 2240 - SPFA - 正权环(最大路)

1.Question:输入n代表有n个国家之后的n行代表n个国家的名称输入m代表有向边的个数之后的代表我们国家货币之间的汇率现在求,是否存在一条回路是的我们的交换货币之后原本的货币量增多2.Solution:本题是标准的判断回路的问题,我们需要将最短路的标准思路转变一下,首先,本题我们需要找到的是正权回路不是负权回路,我们只需要改变一下松弛策略就好,我们只要将松

2016-11-29 09:22:01

关于快速排序算法本质的重要说明 - 考试考了不会就不要怪我

说明,本文章的针对已经大致的理解了快速排序的同学双向扫描VS单向扫描我们都知道,快速排序算法存在两种实现机制,一种是单向扫描法,一种是优化后的双向扫描法单向扫描:首先,我们需要知道,单向扫描是最正规的《算法导论》上给出的基本实现的过程伪代码如下data-arraywaittosortn-thecountofthearrayi-headpo

2016-11-28 21:47:26

Shell-Sort 增量排序算法 总结

1.Shell-Sort希尔排序(ShellSort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。我们都知道直接插入排序算法是相对来说比较低效的算法,但是正是插入排序算法的特性决定了我们在数据量小的时候,数据基本有序的时候的排序效果往往比一些高级排序算法构架行之有效,更加快速在我们开始了解Shell-Sor

2016-11-27 23:49:19

NYOJ 99 - 欧拉图 单词拼接

1.Question:描述给你一些单词,请你判断能否把它们首尾串起来串成一串。前一个单词的结尾应该与下一个单词的道字母相同。如alohadogarachnidgophertigerrat 可以拼接成:aloha.arachnid.dog.gopher.rat.tiger

2016-11-26 16:35:51

POJ 3259 - SPFA负权回路 < Floyed

1.Question:POJ3259农夫约翰在探索他的许多农场,发现了一些惊人的虫洞。虫洞是很奇特的,因为它是一个单向通道,可让你进入虫洞的前达到目的地!他的N(1≤N≤500)个农场被编号为1..N,之间有M(1≤M≤2500)条路径,W(1≤W≤200)个虫洞。FJ作为一个狂热的时间旅行的爱好者,他要做到以下几点:开始在一个区域,通过一些路径和虫洞旅行,他要回到最开时出发

2016-11-26 11:54:15

POJ 1847 - Shortest Path Dijstra>SPFA

1.Question:又一个火车网络系统输入第一行:n,a,b分别代表网络中节点的个数,初始节点,终止节点接下来n行分别代表第i个节点的有向边的终点每一行第一个代表的是有向边的个数,之后的第一个有向边的权值是0,之后的权值都是1现在请给出从a到b的最短的路径权值和2.Solution:本题是标准的最短路径的问题并且数据量比较水,所以说,我们的很多的最短路径

2016-11-24 14:42:00

NYOJ - 42 - 并查集+半欧拉图

1.Question:描述zyc从小就比较喜欢玩一些小游戏,其中就包括画一笔画,他想请你帮他写一个程序,判断一个图是否能够用一笔画下来。规定,所有的边都只能画一次,不能重复画。 输入第一行只有一个正整数N(N每组测试数据的第一行有两个正整数P,Q(P随后的Q行,每行有两个正整数A,B(0输出如果存在符合条件的连线,则输出"Yes",如果不存在符合条件的连线,输

2016-11-23 23:15:51

POJ 3268 - Shortest Path Dijstra+ SPFA

1.Question:题意:输入第一行n,m,t三个数代表的含义分别是图中的n个点,m条有向边,t为初始定点之后的m行代表我们图中的m条有向边在题目要求从t初始点到所有的点点额单源最短路径和将所有的有向边反向之后,我们再求一次单源最短路径求两次的最短路径之和的最大值2.Solution:单元最短路径问题本题因为牵扯到有向边的反向问题,所以我们最好选用矩阵的数据结构来

2016-11-23 19:54:04

AVL - 自平衡二叉树 - 详解

1.AVL说到AVL,我们就必须先要了解一下BSTLantian的BST总结在了解了有关BST的性质之后,我们现在就明白了因为在我们的插入的节点有序的情况下,我们的BST会出现偏树的情况,这会导致我们的ASL(平均查找长度)大大增加从而降低我们的查找效率因此,我们就需要一种BST的优化版本取克服这种输入造成的弊端(现在证明,在平均情况下,出现偏树的概率大致在45.6%),所以说,我

2016-11-23 16:26:18

POJ 2253 - 最短路变形 SPFA+Dijstra

1.Question:题意:题意:给出青蛙A,B和若干石头的坐标,现青蛙A想到青蛙B那,A可通过任意石头到达B,   问从A到B多条路径中的 最长边 中的 最短距离2.Solution:分析:这题是最短路的变形,以前求的是路径总长的最小值,而此题是通路中最长边的最小值,每条边的权值可以通过坐标算出,因为是单源起点,直接用SPFA算法或dijkstra算法就

2016-11-22 19:50:11

POJ 1502 - Shortest Path - SPFA+Dijstra

1.Question:题意:MPI微处理器求解1号MPI到其他的所有的MPI的最短的路径中的最长的一条ShortestPath版题2.Solution:本题我用了两种思路去求解SPFA+Dijstra在同为邻接表的情况下,运行的时间效率相当但是,我通过左本题发现,我对SPFA的算法的本质理解存在有很大的漏洞3.Code:SPFA/*Problem:

2016-11-21 10:47:02

Euler Graph - 欧拉图 详解

1.从哥尼斯堡七桥问题到欧拉图哥尼斯堡七桥问题:18世纪中叶在欧洲普鲁士的哥尼斯堡城内有一条贯穿全市的和河中有两个小岛,现在四块陆地有七座桥连接,引入问题,如何规划线路才能保证我们可以走过所有的边但是却保证不会重复呢这就是著名的哥尼斯堡七桥问题,现在通过图论证明哥尼斯堡问题是不存在解的,第一个发表论文证明了这个事实的人就是欧拉,该论文也是目前为止发现的最早的关于图论的论文,当然,这种问

2016-11-19 19:18:34

POJ 1287 MST Prim+Krustral

1.Code:Prim:/*Problem:1287 User:lantianheyeqiMemory:4132K Time:63MSLanguage:C++ Result:Accepted*/#include"iostream"#include"cstdio"#include"cstring"#include"cstdlib"#defineN100

2016-11-17 16:23:03

POJ 2349 MST Prim

1.Question:抽象概括题意:现在给你一个些点的坐标,每个坐标都是正整数,现在每个点之间都有一个连边(稠密图)现在求最小生成树MST的第n-s/n-1条边的长度,具体选哪个,我们根据s代销来判断,在程序中我已经写明了2.Solution:标准的稠密图,我们最好用Prim,如果用Krustral的话,最坏的情况500*500的边,很容易超时3.Code:#inclu

2016-11-16 20:00:25

DAG - AOV - AOE - CPM - Topological-Sort 详解

1.DAG(Directedacyclinegraph)DAG图,又称有向无环图,简称为DAG,DAG是相对更像是有向树一样的数据结构,用处十分的广泛1.表达式树:DAG可以模拟表达式树,按照数据结构老师的话来说,在操作系统方面的用处更加的广泛2.检查图的环路:我们都知道检查一个无向图是否存在回路是非常的简单的,我们只需要DFS遍历一遍就能判断出来但是我们检查一个有向图

2016-11-16 12:17:38

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!